TY - JOUR

T1 - The price of anarchy in routing games as a function of the demand

AU - Cominetti, Roberto

AU - Dose, Valerio

AU - Scarsini, Marco

N1 - Funding Information:
Open access funding provided by Luiss University within the CRUI-CARE Agreement. Funding is provided by Ministero dell’Istruzione, dell’Universitá e della Ricerca (Grant No. ALGADIMAR), Gruppo Nazionale per l’Analisi Matematica, la Probabilitá e le loro Applicazioni, Ministerio de Educación, Gobierno de Chile (Grant No. FONDECYT 1171501, Grant No. ANID/PIA/ACT192094), European Cooperation in Science and Technology.
Funding Information:
Marco Scarsini and Valerio Dose are members of INdAM-GNAMPA. Roberto Cominetti gratefully acknowledges the support of Luiss University during a visit in which this research was initiated, as well as the support of Proyecto Anillo ANID/PIA/ACT192094. This research project received partial support from the COST action GAMENET, the INdAM-GNAMPA Project 2020 “Random Walks on Random Games,” and the Italian MIUR PRIN 2017 Project ALGADIMAR (Algorithms, Games, and Digital Markets)
Publisher Copyright:
© 2021, The Author(s).

PY - 2021

Y1 - 2021

N2 - The price of anarchy has become a standard measure of the efficiency of equilibria in games. Most of the literature in this area has focused on establishing worst-case bounds for specific classes of games, such as routing games or more general congestion games. Recently, the price of anarchy in routing games has been studied as a function of the traffic demand, providing asymptotic results in light and heavy traffic. The aim of this paper is to study the price of anarchy in nonatomic routing games in the intermediate region of the demand. To achieve this goal, we begin by establishing some smoothness properties of Wardrop equilibria and social optima for general smooth costs. In the case of affine costs we show that the equilibrium is piecewise linear, with break points at the demand levels at which the set of active paths changes. We prove that the number of such break points is finite, although it can be exponential in the size of the network. Exploiting a scaling law between the equilibrium and the social optimum, we derive a similar behavior for the optimal flows. We then prove that in any interval between break points the price of anarchy is smooth and it is either monotone (decreasing or increasing) over the full interval, or it decreases up to a certain minimum point in the interior of the interval and increases afterwards. We deduce that for affine costs the maximum of the price of anarchy can only occur at the break points. For general costs we provide counterexamples showing that the set of break points is not always finite.

AB - The price of anarchy has become a standard measure of the efficiency of equilibria in games. Most of the literature in this area has focused on establishing worst-case bounds for specific classes of games, such as routing games or more general congestion games. Recently, the price of anarchy in routing games has been studied as a function of the traffic demand, providing asymptotic results in light and heavy traffic. The aim of this paper is to study the price of anarchy in nonatomic routing games in the intermediate region of the demand. To achieve this goal, we begin by establishing some smoothness properties of Wardrop equilibria and social optima for general smooth costs. In the case of affine costs we show that the equilibrium is piecewise linear, with break points at the demand levels at which the set of active paths changes. We prove that the number of such break points is finite, although it can be exponential in the size of the network. Exploiting a scaling law between the equilibrium and the social optimum, we derive a similar behavior for the optimal flows. We then prove that in any interval between break points the price of anarchy is smooth and it is either monotone (decreasing or increasing) over the full interval, or it decreases up to a certain minimum point in the interior of the interval and increases afterwards. We deduce that for affine costs the maximum of the price of anarchy can only occur at the break points. For general costs we provide counterexamples showing that the set of break points is not always finite.

KW - Affine cost functions

KW - Nonatomic routing games

KW - Price of anarchy

KW - Variable demand

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

U2 - 10.1007/s10107-021-01701-7

DO - 10.1007/s10107-021-01701-7

M3 - Article

AN - SCOPUS:85114390311

SN - 0025-5610

JO - Mathematical Programming

JF - Mathematical Programming

ER -