Phase Transitions of the Price-of-Anarchy Function in Multi-Commodity Routing Games
Fuente:
arXiv
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2023
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866914716328132608 |
|---|---|
| author | Cominetti, Roberto Dose, Valerio Scarsini, Marco |
| author_facet | Cominetti, Roberto Dose, Valerio Scarsini, Marco |
| contents | 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, \ie 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2305_03459 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | Phase Transitions of the Price-of-Anarchy Function in Multi-Commodity Routing Games Cominetti, Roberto Dose, Valerio Scarsini, Marco Computer Science and Game Theory Optimization and Control 91A14, 91A07, 91A43, 90C25 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, \ie 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. |
| title | Phase Transitions of the Price-of-Anarchy Function in Multi-Commodity Routing Games |
| topic | Computer Science and Game Theory Optimization and Control 91A14, 91A07, 91A43, 90C25 |
| url | https://arxiv.org/abs/2305.03459 |