This Article Full Text (PDF) References Alert me when this article is cited Alert me if a correction is posted Services Email this article to a friend Similar articles in this journal Alert me to new issues of the journal Download to citation manager Citing Articles Citing Articles via HighWire Citing Articles via Google Scholar Google Scholar Articles by Correa, J. R. Articles by Stier-Moses, N. E. Search for Related Content

Selfish Routing in Capacitated Networks

Departamento de Ciencias de la Computacion, Universidad de Chile, Avenida Blanco Encalada 2120, Santiago, Chile C.P. 837-0459
Sloan School of Management, Massachusetts Institute of Technology, Office E53-36, 77 Massachusetts Avenue, Cambridge, Massachusetts 02139-4307
Columbia Business School, Uris Hall, Room 418, 3022 Broadway, New York, New York 10027-6902
jcorrea{at}dcc.uchile.cl
schulz{at}mit.edu
nicolas.stier{at}columbia.edu

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.

Key Words: selfish routing; price of anarchy; traffic assignment; system optimum; Nash equilibrium; performance guarantee; multicommodity flow
History: Received: June 23, 2003; revision received: February 10, 2004;

This article has been cited by other articles:

				P. Maille and N. E. Stier-Moses Eliciting Coordination with Rebates Transportation Science, November 1, 2009; 43(4): 473 - 492. [Abstract] [PDF]

				R. Johari and J. N. Tsitsiklis Efficiency of Scalar-Parameterized Mechanisms Operations Research, July 1, 2009; 57(4): 823 - 839. [Abstract] [PDF]

				G. Perakis The "Price of Anarchy" Under Nonlinear and Asymmetric Costs Mathematics of Operations Research, August 1, 2007; 32(3): 614 - 628. [Abstract] [PDF]

				G. Perakis and G. Roels The Price of Anarchy in Supply Chains: Quantifying the Efficiency of Price-Only Contracts Management Science, August 1, 2007; 53(8): 1249 - 1268. [Abstract] [PDF]

				J. R. Correa, A. S. Schulz, and N. E. Stier-Moses Fast, Fair, and Efficient Flows in Networks Operations Research, March 1, 2007; 55(2): 215 - 225. [Abstract] [PDF]

				R. Borndorfer, M. Grotschel, and M. E. Pfetsch A Column-Generation Approach to Line Planning in Public Transport Transportation Science, February 1, 2007; 41(1): 123 - 132. [Abstract] [PDF]