TY - JOUR

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

AU - Colini-Baldeschi, Riccardo

AU - Cominetti, Roberto

AU - Mertikopoulos, Panayotis

AU - Scarsini, Marco

N1 - Funding Information:
This research was supported by COST [Action CA16228 "European Network for Game Theory" (GAMENET)]; the Fondation Mathématique Jacques Hadamard program PGMOcofunded by EDF, Thales, and Orange [Grant HEAVY.NET]; the National Fund for Scientific and Technological Development of Chile [Grants 1171501 and 1130564]; Núcleo Milenio [ICM/FIC RC130003 "Información y Coordinación en Redes"]; ECOS/CONICYT [Grant C15E03]; the Huawei HIRP Flagship project ULTRON; and the Gruppo Nazionale per l'Analisi Matematica, la Probabilità e le loro Applicazioni-INdAM project 2019 "Markov chains and games on networks."
Funding Information:
Funding: This research was supported by COST [Action CA16228 “European Network for Game Theory” (GAMENET)]; the Fondation Mathématique Jacques Hadamard program PGMO cofunded by EDF, Thales, and Orange [Grant HEAVY.NET]; the National Fund for Scientific and Techno-logical Development of Chile [Grants 1171501 and 1130564]; Núcleo Milenio [ICM/FIC RC130003 “Información y Coordinación en Redes”]; ECOS/CONICYT [Grant C15E03]; the Huawei HIRP Flagship project ULTRON; and the Gruppo Nazionale per l’Analisi Matematica, la Probabilità e le loro Applicazioni–INdAM project 2019 “Markov chains and games on networks.”
Publisher Copyright:
© 2020 INFORMS.

PY - 2020/3

Y1 - 2020/3

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

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

KW - Heavy traffic

KW - Light traffic

KW - Nonatomic congestion games

KW - Price of anarchy

KW - Regular variation

UR - http://www.scopus.com/inward/record.url?scp=85091645867&partnerID=8YFLogxK

U2 - 10.1287/opre.2019.1894

DO - 10.1287/opre.2019.1894

M3 - Article

AN - SCOPUS:85091645867

VL - 68

SP - 411

EP - 434

JO - Operations Research

JF - Operations Research

SN - 0030-364X

IS - 2

ER -