When is selfish routing bad? The price of anarchy in light and heavy traffic

Riccardo Colini-Baldeschi, Roberto Cominetti, Panayotis Mertikopoulos, Marco Scarsini

Research output: Contribution to journalArticlepeer-review

27 Scopus citations

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.

Original languageEnglish
Pages (from-to)411-434
Number of pages24
JournalOperations Research
Volume68
Issue number2
DOIs
StatePublished - Mar 2020
Externally publishedYes

Keywords

  • Heavy traffic
  • Light traffic
  • Nonatomic congestion games
  • Price of anarchy
  • Regular variation

Fingerprint

Dive into the research topics of 'When is selfish routing bad? The price of anarchy in light and heavy traffic'. Together they form a unique fingerprint.

Cite this