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.
Phase transitions of the price-of-anarchy function in multi-commodity routing games / Cominetti, Roberto; Dose, Valerio; Scarsini, Marco. - In: TRANSPORTATION RESEARCH PART B-METHODOLOGICAL. - ISSN 0191-2615. - 182:April 2024(2024). [10.1016/j.trb.2024.102922]
Phase transitions of the price-of-anarchy function in multi-commodity routing games
Dose, Valerio
;Scarsini, Marco
2024
Abstract
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.File | Dimensione | Formato | |
---|---|---|---|
Cominetti_Phase_2024.pdf
accesso aperto
Note: https://doi.org/10.1016/j.trb.2024.102922
Tipologia:
Versione editoriale (versione pubblicata con il layout dell'editore)
Licenza:
Creative commons
Dimensione
766.15 kB
Formato
Adobe PDF
|
766.15 kB | Adobe PDF |
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.