TY - JOUR

T1 - Phase transitions of the price-of-anarchy function in multi-commodity routing games

AU - Cominetti, Roberto

AU - Dose, Valerio

AU - Scarsini, Marco

N1 - Publisher Copyright:
© 2024 The Authors

PY - 2024/4

Y1 - 2024/4

N2 - We consider the behavior of the price of anarchy and equilibrium flows in nonatomic multi-commodity routing games as a function of the traffic demand. We analyze their smoothness with a special attention to specific values of the demand at which the support of the Wardrop equilibrium exhibits a phase transition with an abrupt change in the set of optimal routes. Typically, when such a phase transition occurs, the price of anarchy function has a breakpoint, i.e., is not differentiable. We prove that, if the demand varies proportionally across all commodities, then, at a breakpoint, the largest left or right derivatives of the price of anarchy and of the social cost at equilibrium, are associated with the smaller equilibrium support. This proves – under the assumption of proportional demand – a conjecture of O'Hare et al. (2016), who observed this behavior in simulations. We also provide counterexamples showing that this monotonicity of the one-sided derivatives may fail when the demand does not vary proportionally, even if it moves along a straight line not passing through the origin.

AB - We consider the behavior of the price of anarchy and equilibrium flows in nonatomic multi-commodity routing games as a function of the traffic demand. We analyze their smoothness with a special attention to specific values of the demand at which the support of the Wardrop equilibrium exhibits a phase transition with an abrupt change in the set of optimal routes. Typically, when such a phase transition occurs, the price of anarchy function has a breakpoint, i.e., is not differentiable. We prove that, if the demand varies proportionally across all commodities, then, at a breakpoint, the largest left or right derivatives of the price of anarchy and of the social cost at equilibrium, are associated with the smaller equilibrium support. This proves – under the assumption of proportional demand – a conjecture of O'Hare et al. (2016), who observed this behavior in simulations. We also provide counterexamples showing that this monotonicity of the one-sided derivatives may fail when the demand does not vary proportionally, even if it moves along a straight line not passing through the origin.

KW - Network flows

KW - Traffic demand

KW - Wardrop equilibrium

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

U2 - 10.1016/j.trb.2024.102922

DO - 10.1016/j.trb.2024.102922

M3 - Article

AN - SCOPUS:85187963340

SN - 0191-2615

VL - 182

JO - Transportation Research Part B: Methodological

JF - Transportation Research Part B: Methodological

M1 - 102922

ER -