An Exact Counterexample to Affine-Like Price-of-Anarchy Shape in Quartic BPR Routing
Abstract
We give an exact computer-assisted counterexample to a direct common-degree quartic extension of the affine active-network shape theorem for demand-dependent Price of Anarchy. The instance is a directed network with five vertices, six edges, and three origin--destination paths, all with positive rational costs ce(x)=ae+bex4. Exact rational interval certificates show that all three paths carry positive Wardrop flow throughout the demand interval [17,24], while PoA(21)>PoA(17), PoA(21)>PoA(24). Continuity therefore forces an interior local maximum despite a constant equilibrium active network. Krawczyk inclusions isolate the Wardrop and social-optimum KKT solutions, elementary boundary inequalities certify constant support, and interval social costs certify both strict comparisons. At differentiability points, we also derive a serial-edge identity explaining how a common quartic edge can alter the derivative of PoA without changing either route split. The proof and certificate use exact rational arithmetic for every interval and sign decision.
Related
- Regularity of the Price of Anarchy in Routing Games over the Multivariate Demand Space
- The local-to-global minimum problem of Calvert and Vamanamurthy: a quartic counterexample in three variables and the cubic case in all dimensions
- Exact counting of unlabeled quartic graphs by permutation-cycle aggregation
- Exact Hessian Cancellation and Quartic Nondegeneracy at the Round Circle
- The Exact Boundary of Linear Optimality in Witsenhausen's Counterexample
BibTeX
@misc{dambrosio2026exact,
title = {{An Exact Counterexample to Affine-Like Price-of-Anarchy Shape in Quartic BPR Routing}},
author = {Ian D'Ambrosio},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.26179},
eprint = {2609.26179},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.26179},
}
RIS
TY - UNPB
TI - An Exact Counterexample to Affine-Like Price-of-Anarchy Shape in Quartic BPR Routing
AU - Ian D'Ambrosio
PY - 2026
DA - 2026/09/01
PB - arXiv
DO - 10.48550/arxiv.2609.26179
UR - https://arxiv.org/abs/2609.26179
AB - We give an exact computer-assisted counterexample to a direct common-degree quartic extension of the affine active-network shape theorem for demand-dependent Price of Anarchy. The instance is a directed network with five vertices, six edges, and three origin--destination paths, all with positive rational costs c_e(x)=a_e+b_ex^4. Exact rational interval certificates show that all three paths carry positive Wardrop flow throughout the demand interval [17,24], while PoA(21)>PoA(17), PoA(21)>PoA(24). Continuity therefore forces an interior local maximum despite a constant equilibrium active network. Krawczyk inclusions isolate the Wardrop and social-optimum KKT solutions, elementary boundary inequalities certify constant support, and interval social costs certify both strict comparisons. At differentiability points, we also derive a serial-edge identity explaining how a common quartic edge can alter the derivative of PoA without changing either route split. The proof and certificate use exact rational arithmetic for every interval and sign decision.
ER -