Selfish Routing in Capacitated Networks

By José R. Correa, Andreas S. Schulz, Nicolás E. Stier Moses. Mathematics of Operations Research, 2004

302 citations recorded by the source corpus.

According to Wardrop's first principle, agents in a congested network choose their routes selfishly, a behavior that is captured by the Nash equilibrium of the underlying noncooperative game. A Nash equilibrium does not optimize any global criterion per se, and so there is no apparent reason why it should be close to a solution of minimal total travel time, i.e., the system optimum. In this paper, we offer positive results on the efficiency of Nash equilibria in traffic networks. In contrast to prior work, we present results for networks with capacities and for latency functions that are nonconvex, nondifferentiable, and even discontinuous.The inclusion of upper bounds on arc flows has early been recognized as an important means to provide a more accurate description of traffic flows. In this more general model, multiple Nash equilibria may exist and an arbitrary equilibrium does not need to be nearly efficient. Nonetheless, our main result shows that the best equilibrium is as efficient as in the model without capacities. Moreover, this holds true for broader classes of travel cost functions than considered hitherto.

Subfields: Control and Systems Engineering, Economics and Econometrics, Transportation

View Paper: https://www.semanticscholar.org/paper/d08fae743cfba50828c6f78435bd370cd564b5cd

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Control and Systems Engineering

In Economics and Econometrics

In Transportation

Citations in the corpus

The price of stability for network design with fair cost allocation (2004, background): “the quality at a centrally enforced optimum? Questions of this genre have received considerable attention in recent years, for problems including routing [24, 25, 4], load balancing [5, 6, 16, 23], and facility location [26].”
A Column-Generation Approach to Line Planning in Public Transport (2007, background): “However, in our case, with a linear objective function and linear capacities, it can be shown that the resulting system optimum is also a user equilibrium, namely, the so-called Beckmann user equilibrium, see Correa, Schulz, and Stier Moses (2004).”
Bounding the efficiency gain of differentiable road pricing for EVs and GVs to manage congestion and emissions (2020, result): “[25] proved the bound of POA through a geometric method, and the results are consistent with those in [24].”
Network games (2004, background): “Work in price of stability has focused on network design [1, 2] and routing [5, 2].”
Selfish routing and the price of anarchy (2005, background): “17 given above is taken from [22].”