Exploring trust region method for the solution of logit-based stochastic user equilibrium problem

In this research paper, we explored using the trust region method to solve the logit-based SUE problem. We proposed a modified trust region Newton (MTRN) algorithm for this problem. When solving the trust region SUE subproblem, we showed that applying the well-known Steihaug-Toint method is inappropriate, since it may make the convergence rate of the major iteration very slow in the early stage of the computation. To overcome this drawback, a modified Steihaug-Toint method was proposed. We proved the convergence of our MTRN algorithm and showed its convergence rate is superlinear.     

Solving the logit-based stochastic user equilibrium problem with elastic demand based on the extended traffic network model

This paper proposes a novel extended traffic network model to solve the logit-based stochastic user equilibrium (SUE) problem with elastic demand. In this model, an extended traffic network is established by properly adding dummy nodes and links to the original traffic network. Based on the extended traffic network, the logit-based SUE problem with elastic demand is transformed to the SUE problem with fixed demand. Such problem is then further converted to a linearly constrained convex programming and addressed by a predictor–corrector interior point algorithm with polynomial complexity. A numerical example is provided to compare the proposed model with the method of successive averages (MSA). The numerical results indicate that the proposed model is more efficient and has a better convergence than the MSA.     

A rank-dependent bi-criterion equilibrium model for stochastic transportation environment

The paper proposes a rank-dependent bi-criterion (travel time & monetary travel cost) equilibrium model for route choice problems, stochasticities in both the criteria measurements and the subjective preferences are considered simultaneously. Travelers rank all the choices, according to the generalized travel dis-utility, then choose from the first several (see K  ) best ranked ones. By searching inversely the supporting preference sets for each alternative in each rank, the overall choice probability of a path is determined. The equilibrium model is formulated and transformed into a fixed-point problem. The existence of the equilibrium is given out for a simple two-link network, however may not be guaranteed for more complex network topologies. When K=1$K=1$, the proposed model reduces to the optimal user equilibrium that allows for the stochasticities of criteria measurements and the arbitrarily distributed preferences. Some remarks about the selection of some parameters in the new model are discussed and also the solution algorithms. Two numerical examples are presented to illustrate the implementation of the model, and also the capability and flexibility of the new model in handling the heterogeneity in traveler preferences and requirements. The paper concludes with discussions about the assumptions and limitations of the new model and possible future research opportunities as well.     

A multiclass,multicriteria logit-based traffic equilibrium assignment model under ATIS

This paper presents a multiclass, multicriteria (cost versus time) logit-based traffic equilibrium assignment model in road networks served by advanced traveler information systems (ATIS). All users are differentiated by their own value of time (VOT) that follows some probability distribution. Users of each class, having their own VOT, are further divided into two groups, equipped and unequipped with ATIS respectively. The travel disutility received by each user is defined as a linear bi-criteria combination of travel time and monetary travel cost. It is assumed that all users make their route choices in a logit-based stochastic manner, but the equipped users have lower perception variation on the travel disutility than the unequipped due to the ATIS service. The model is formulated as a fixed-point problem and solved by the method of successive averages in conjunction with logit assignment. Numerical results show that the traditional single-class and/or single-criterion models may overestimate or underestimate the benefit from ATIS services.     

An approximate dynamic programming approach for the vehicle routing problem with stochastic demands

This paper examines approximate dynamic programming algorithms for the single-vehicle routing problem with stochastic demands from a dynamic or reoptimization perspective. The methods extend the rollout algorithm by implementing different base sequences (i.e. a priori solutions), look-ahead policies, and pruning schemes. The paper also considers computing the cost-to-go with Monte Carlo simulation in addition to direct approaches. The best new method found is a two-step lookahead rollout started with a stochastic base sequence. The routing cost is about 4.8% less than the one-step rollout algorithm started with a deterministic sequence. Results also show that Monte Carlo cost-to-go estimation reduces computation time 65% in large instances with little or no loss in solution quality. Moreover, the paper compares results to the perfect information case from solving exact a posteriori solutions for sampled vehicle routing problems. The confidence interval for the overall mean difference is (3.56%, 4.11%).     

Bounding multi-stage stochastic programs from above

The purpose of this paper is to present general approaches for bounding some multi-stage stochastic programs from above. The results are based on restricting the solution set, such that the remaining multi-stage stochastic program is easy to solve. An example where the methods can be applied is presented.Supported in part by NATO Collaborative Research Grant No. 0785/87.     

On nash equilibrium solutions in nonzero-sum stochastic games with complete information

Two-person nonzero-sum stochastic games with complete information are considered. It is shown that it is sufficient to search the equilibrium solutions in a class of deterministic strategy pairs — the so-calledintimidation strategy pairs. Furthermore, properties of the set of all equilibrium losses of such strategy pairs are proved.     

EXISTENCE OF STOCHASTIC EQUILIBRIUM WITH INCOMPLETE FINANCIAL MARKETS

This paper analyzes the aritrage-tree security markets and the general equilibrium ex-istence problem for a stochastic economy with incomplete financial markets. Information structure is given by an event tree. This paper restricts attention to puraly financial securities. It isassume that trading takes place in the sequence of spot markets and futures markets for securi-ties payable in units of account. Unlimited short-selling in securities is allowed. Financial markets may be incomplete, some consumption streams may be impossible to obtain by any tradingstrategy. Securities may be individually precluded from trade at arbitrary states and dates. Thesecurity price process is arbitrage-free the dividend process if and only if there exists a stochaticstate price (present value) process : the present value of the security prices at every vertex isthe present value of their dividend and capital values over the set of immediate successors ; thecurrent value of each security at every vertex is the present value of its future dividend streamover all succeeding vertices. The existence of such an equilibrium is proved under the followingcondition: continuous, weakly convex, strictly monotone and complete preferences, strictlypositive endowmenta and dividends processes.     

Ensuring service levels in routing problems with time windows and stochastic travel times

In the stochastic variant of the vehicle routing problem with time windows, known as the SVRPTW, travel times are assumed to be stochastic. In our chance-constrained approach to the problem, restrictions are placed on the probability that individual time window constraints are violated, while the objective remains based on traditional routing costs. In this paper, we propose a way to offer this probability, or service level, for all customers. Our approach carefully considers how to compute the start-service time and arrival time distributions for each customer. These distributions are used to create a feasibility check that can be “plugged” into any algorithm for the VRPTW and thus be used to solve large problems fairly quickly. Our computational experiments show how the solutions change for some well-known data sets across different levels of customer service, two travel time distributions, and several parameter settings.     

A BSDE approach to Nash equilibrium payoffs for stochastic differential games with nonlinear cost functionals

In this paper, we study Nash equilibrium payoffs for two-player nonzero-sum stochastic differential games via the theory of backward stochastic differential equations. We obtain an existence theorem and a characterization theorem of Nash equilibrium payoffs for two-player nonzero-sum stochastic differential games with nonlinear cost functionals defined with the help of doubly controlled backward stochastic differential equations. Our results extend former ones by Buckdahn et al. (2004) [3] and are based on a backward stochastic differential equation approach.     

On risk averse competitive equilibrium

We discuss risked competitive partial equilibrium in a setting in which agents are endowed with coherent risk measures. In contrast to social planning models, we show by example that risked equilibria are not unique, even when agents’ objective functions are strictly concave. We also show that standard computational methods find only a subset of the equilibria, even with multiple starting points.     

Equilibria for networks with malicious users

We consider the problem of characterizing user equilibria and optimal solutions for selfish routing in a given network. We extend the known models by considering malicious behavior. While selfish users follow a strategy that minimizes their individual cost, a malicious user will use his flow through the network in an effort to cause the maximum possible damage to the overall cost. We define a generalized model, present characterizations of flows at equilibrium and prove bounds for the ratio of the social cost of a flow at equilibrium over the cost when centralized coordination among users is allowed. An extended abstract of this work appeared in the Proceedings of the 14th Annual International Symposium on Algorithms and Computation (ISAAC) 2003. G. Karakostas’ research was supported by an NSERC Discovery research grant and MITACS. Part of this research was done when Viglas was a postdoctoral fellow at the University of Toronto, Canada.     

Bounding the inefficiency of Nash equilibria in games with finitely many players

This paper derives bounds on the gap between optimal performance and the performance of Nash equilibria in n-person games with continuous action sets. Specific interesting expressions are obtained for the average efficiency per player in congestion games.     

A stochastic Nash equilibrium portfolio game between two DC pension funds

In this paper, we study the stochastic Nash equilibrium portfolio game between two pension funds under inflation risks. The financial market consists of cash, bond and two stocks. It is assumed that the price index is derived through a generalized Fisher equation while the bond is related to the price index to hedge the risk of inflation. Besides, these two pension managers can invest in their familiar stocks. The goal of the pension managers is to maximize the utility of the weighted terminal wealth and relative wealth. Dynamic programming method is employed to derive the Nash equilibrium strategies. In the end, a numerical analysis is presented to reveal the economic behaviors of the two DC pension funds.     

Existence of stationary equilibrium strategies in non-zero sum discounted stochastic games with uncountable state space and state-independent transitions

Non-zero sum discounted stochastic games with uncountable state space and state in-dependent transitions have stationary equilibrium strategies.     

Monte Carlo and quasi-Monte Carlo sampling methods for a class of stochastic mathematical programs with equilibrium constraints

In this paper, we consider a class of stochastic mathematical programs with equilibrium constraints introduced by Birbil et al. (Math Oper Res 31:739–760, 2006). Firstly, by means of a Monte Carlo method, we obtain a nonsmooth discrete approximation of the original problem. Then, we propose a smoothing method together with a penalty technique to get a standard nonlinear programming problem. Some convergence results are established. Moreover, since quasi-Monte Carlo methods are generally faster than Monte Carlo methods, we discuss a quasi-Monte Carlo sampling approach as well. Furthermore, we give an example in economics to illustrate the model and show some numerical results with this example. The first author’s work was supported in part by the Scientific Research Grant-in-Aid from Japan Society for the Promotion of Science and SRF for ROCS, SEM. The second author’s work was supported in part by the United Kingdom Engineering and Physical Sciences Research Council grant. The third author’s work was supported in part by the Scientific Research Grant-in-Aid from Japan Society for the Promotion of Science.     

The complexity of branch-and-price algorithms for the capacitated vehicle routing problem with stochastic demands

The capacitated vehicle routing problem with stochastic demands (CVRPSD) is a variant of the deterministic capacitated vehicle routing problem where customer demands are random variables. While the most successful formulations for several deterministic vehicle-routing problem variants are based on a set-partitioning formulation, adapting such formulations for the CVRPSD under mild assumptions on the demands remains challenging. In this work we provide an explanation to such challenge, by proving that when demands are given as a finite set of scenarios, solving the LP relaxation of such formulation is strongly NP-Hard. We also prove a hardness result for the case of independent normal demands.     

Transportation inequalities for stochastic differential equations with jumps

For stochastic differential equations with jumps, we prove that _W1H$W_{1}H$ transportation inequalities hold for their invariant probability measures and for their process-level laws on the right-continuous path space w.r.t. the L¹$L^1$-metric and uniform metric, under dissipative conditions, via Malliavin calculus. Several applications to concentration inequalities are given.     

Two-stage stochastic equilibrium problems with equilibrium constraints: modeling and numerical schemes

This article presents a two-stage stochastic equilibrium problem with equilibrium constraints (SEPEC) model. Some source problems which motivate the model are discussed. Monte Carlo sampling method is applied to solve the SEPEC. Convergence analysis on the statistical estimators of Nash equilibria and Nash stationary points are presented.     

Markovian traffic equilibrium

We analyze an equilibrium model for traffic networks based on stochastic dynamic programming. In this model passengers move towards their destinations by a sequential process of arc selection based on a discrete choice model at every intermediate node in their trip. Route selection is the outcome of this sequential process while network flows correspond to the invariant measures of the underlying Markov chains. The approach may handle different discrete choice models at every node, including the possibility of mixing deterministic and stochastic distribution rules. It can also be used over a multi-modal network in order to model the simultaneous selection of mode and route, as well as to treat the case of elastic demands. We establish the existence of a unique equilibrium, which is characterized as the solution of an unconstrained strictly convex minimization problem of low dimension. We report some numerical experiences comparing the performance of the method of successive averages (MSA) and Newton’s method on one small and one large network, providing a formal convergence proof for MSA. Dedicated to Clovis Gonzaga on the occassion of his 60th birthday.