Selfish Routing in Capacitated Networks

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 wh...

Full description

Saved in:
Bibliographic Details
Published in:Mathematics of operations research 2004-11, Vol.29 (4), p.961-976
Main Authors: Correa, Jose R, Schulz, Andreas S, Stier-Moses, Nicolas E
Format: Article
Language:English
Subjects:
Analysis
Anarchy
Equilibrium (Economics)
Game theory
Mathematical analysis
Mathematical functions
Mathematical theorems
Mathematics
multicommodity flow
Nash equilibrium
Operations research
performance guarantee
price of anarchy
selfish routing
Studies
system optimum
Traffic assignment
Traffic models
Transportation
Travel expenses
Travel time
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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.
ISSN:0364-765X
1526-5471
DOI:10.1287/moor.1040.0098