How Much Can Approximate Equilibria Change the Social Cost of Selfish Routing?

Abstract

We study approximate Nash equilibria in nonatomic congestion games, with the goal of understanding how much the social cost can change when the equilibrium condition is relaxed. We consider ε-approximate Nash equilibria (ε-NE), in which each player uses a strategy whose cost is at most 1 + ε times the minimum available cost. We compare the social costs of ε-NE and exact Nash equilibria. This lets us quantify, for example, how much a navigation app can reduce total travel time when drivers tolerate routes slightly slower than the fastest available route. For degree-d polynomial latencies in both general nonatomic congestion games and single-commodity routing games on series-parallel networks, we give tight lower and upper bounds on the relative change in social cost from an exact Nash equilibrium to any ε-NE, with matching instances for every ε. For small ε, the largest possible relative reduction and increase in general congestion games are both Θ(√(dε)), independently of the number of resources and populations. In contrast, on series-parallel networks of depth h, the largest possible relative reduction is Θ(hε), while the largest possible relative increase is known to be ε. For the classes of games we study, these results give a tight and quantitative characterization of the possible changes in social cost and establish a separation between general and series-parallel networks.

Bayesian Equilibria of Heterogeneous Non-Atomic Routing Games With Private Information
Alexia Ambrogio, Leonardo Cianfanelli, Giacomo Como +1
IEEE Control Systems Letters25 Jun 2026Peer-reviewedPublisher termsFull textGeneral mathematicsHAL
EquiPartition: Learning Player-Adaptive Deviation Certificates for Complete Enclosure of Approximate Nash Equilibria in Strategic Financial Markets
Jinjia Chen, Kun Yang, Danhua Liu +2
Mathematics4 Nov 2026Peer-reviewedCC BY 4.0General mathematicsCrossref
The Road to Liberation is Paved with Threats: A Biopsychosocial Perspective on Minoritized Individuals’ Responses to Hierarchy-Disruptive Social Change
Marty Colombo, Daan Scheepers, Félice van Nunspeet
PsyArXiv22 Oct 2026PreprintCC BY 4.0Full textStatistics PhysiologyOSF
Seifert type magnetohydrostatic equilibria in rotationally symmetric toroidal domains
Daniel Peralta-Salas, Radu Slobodeanu
arXiv6 Oct 2026PreprintarXiv licenceFull textAnalysis & PDEs Mathematical physicsarXiv
On the density of Lyapunov unstable elliptic equilibria
Bassam Fayad, Jaime Paradela, Maria Saprykina +1
arXiv3 Sep 2026PreprintarXiv licenceFull textDynamical systemsarXiv

Cite

BibTeX RIS

BibTeX

@misc{cheng2026much,
  title = {{How Much Can Approximate Equilibria Change the Social Cost of Selfish Routing?}},
  author = {Yu Cheng and Tianle Jiang},
  howpublished = {arXiv},
  year = {2026},
  month = nov,
  doi = {10.48550/arxiv.2611.01234},
  eprint = {2611.01234},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2611.01234},
}

RIS

TY  - UNPB
TI  - How Much Can Approximate Equilibria Change the Social Cost of Selfish Routing?
AU  - Yu Cheng
AU  - Tianle Jiang
PY  - 2026
DA  - 2026/11/01
PB  - arXiv
DO  - 10.48550/arxiv.2611.01234
UR  - https://arxiv.org/abs/2611.01234
AB  - We study approximate Nash equilibria in nonatomic congestion games, with the goal of understanding how much the social cost can change when the equilibrium condition is relaxed. We consider ε-approximate Nash equilibria (ε-NE), in which each player uses a strategy whose cost is at most 1 + ε times the minimum available cost. We compare the social costs of ε-NE and exact Nash equilibria. This lets us quantify, for example, how much a navigation app can reduce total travel time when drivers tolerate routes slightly slower than the fastest available route. For degree-d polynomial latencies in both general nonatomic congestion games and single-commodity routing games on series-parallel networks, we give tight lower and upper bounds on the relative change in social cost from an exact Nash equilibrium to any ε-NE, with matching instances for every ε. For small ε, the largest possible relative reduction and increase in general congestion games are both Θ(√(dε)), independently of the number of resources and populations. In contrast, on series-parallel networks of depth h, the largest possible relative reduction is Θ(hε), while the largest possible relative increase is known to be ε. For the classes of games we study, these results give a tight and quantitative characterization of the possible changes in social cost and establish a separation between general and series-parallel networks.
ER  -

Abstract

Related

Cite