When Is Selfish Routing Bad? The Price of Anarchy in Light and Heavy Traffic

Riccardo Colini-Baldeschi (), Roberto Cominetti (), Panayotis Mertikopoulos () and Marco Scarsini
Additional contact information
Riccardo Colini-Baldeschi: Core Data Science Group, Facebook, Inc., London W1T 1FB, United Kingdom
Roberto Cominetti: Facultad de Ingeniería y Ciencias, Universidad Adolfo Ibáñez, 7941169 Santiago, Chile
Panayotis Mertikopoulos: Université Grenoble Alpes, CNRS, Inria, Grenoble INP, LIG, 38000 Grenoble, France

Operations Research, 2020, vol. 68, issue 2, 411-434

Abstract: This paper examines the behavior of the price of anarchy as a function of the traffic inflow in nonatomic congestion games with multiple origin/destination (O/D) pairs. Empirical studies in real-world networks show that the price of anarchy is close to 1 in both light and heavy traffic, thus raising the following question: can these observations be justified theoretically? We first show that this is not always the case: the price of anarchy may remain a positive distance away from 1 for all values of the traffic inflow, even in simple three-link networks with a single O/D pair and smooth, convex costs. On the other hand, for a large class of cost functions (including all polynomials) and inflow patterns, the price of anarchy does converge to 1 in both heavy and light traffic, irrespective of the network topology and the number of O/D pairs in the network. We also examine the rate of convergence of the price of anarchy, and we show that it follows a power law whose degree can be computed explicitly when the network’s cost functions are polynomials.

Keywords: nonatomic congestion games; price of anarchy; light traffic; heavy traffic; regular variation (search for similar items in EconPapers)
Date: 2020
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (8)

Downloads: (external link)
https://doi.org/10.1287/opre.2019.1894 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:oropre:v:68:y:2020:i:2:p:411-434

Access Statistics for this article

More articles in Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().