Regularity of the Price of Anarchy in Routing Games over the Multivariate Demand Space
Abstract
We study the price of anarchy (PoA) in nonatomic routing games as a function of the full vector of origin--destination demands. We show that the Beckmann value function is continuously differentiable on the positive demand cone, with gradient equal to the equilibrium origin--destination cost vector; hence the PoA is continuously differentiable on the regular demand region. We prove that the nondifferentiability set has Lebesgue measure zero and, when every edge cost is strictly increasing or constant, is covered by countably many codimension-one submanifolds. Under the same cost structure, all equilibrium objects are cellwise as smooth as the edge costs. For affine costs, the exceptional sets become finite unions of lower-dimensional polyhedral cells linked by an exact scaling law, and the maximum of the PoA over a cell closure is attained on the cell boundary, generalizing the one-dimensional endpoint result. The theory is illustrated on the Sioux Falls benchmark network.
Related
- An Exact Counterexample to Affine-Like Price-of-Anarchy Shape in Quartic BPR Routing
- Policy Iteration Is Not Strongly Polynomial for Deterministic Markov Decision Processes: The Price of Algorithmic Anarchy
- Deriving the Pure Price of Anarchy for Networked Resource Allocation Games
- Learning to Price Electricity for Optimal Demand Response
- Routing Optimality for Demand Graphs of Matching Number at Most Two
BibTeX
@misc{wang2026regularity,
title = {{Regularity of the Price of Anarchy in Routing Games over the Multivariate Demand Space}},
author = {Jiawen Wang and Hu Shao and Ting Wu},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.16185},
eprint = {2610.16185},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.16185},
}
RIS
TY - UNPB
TI - Regularity of the Price of Anarchy in Routing Games over the Multivariate Demand Space
AU - Jiawen Wang
AU - Hu Shao
AU - Ting Wu
PY - 2026
DA - 2026/10/12
PB - arXiv
DO - 10.48550/arxiv.2610.16185
UR - https://arxiv.org/abs/2610.16185
AB - We study the price of anarchy (PoA) in nonatomic routing games as a function of the full vector of origin--destination demands. We show that the Beckmann value function is continuously differentiable on the positive demand cone, with gradient equal to the equilibrium origin--destination cost vector; hence the PoA is continuously differentiable on the regular demand region. We prove that the nondifferentiability set has Lebesgue measure zero and, when every edge cost is strictly increasing or constant, is covered by countably many codimension-one submanifolds. Under the same cost structure, all equilibrium objects are cellwise as smooth as the edge costs. For affine costs, the exceptional sets become finite unions of lower-dimensional polyhedral cells linked by an exact scaling law, and the maximum of the PoA over a cell closure is attained on the cell boundary, generalizing the one-dimensional endpoint result. The theory is illustrated on the Sioux Falls benchmark network.
ER -