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

Yu Cheng, Tianle JiangarXiv 2026 · arXiv

TL;DR

This paper provides the first tight characterization of how much the total travel time (social cost) can change when drivers in a network are allowed to choose "good enough" routes instead of strictly the fastest ones. The authors prove that while general networks can see significant changes in social cost even with tiny driver tolerance—on the order of $\sqrt{\epsilon}$—series-parallel networks are much more stable, with changes scaling linearly with tolerance.

What Problem Does This Paper Address?

In the study of traffic networks, researchers often use the Nash equilibrium to model driver behavior, assuming every driver perfectly chooses the absolute fastest route. The "Price of Anarchy" (PoA) then quantifies how much total travel time increases because of this selfish behavior compared to a centrally planned optimum.

However, real-world drivers aren't perfect: they lack precise data, have personal preferences, or follow navigation apps that might "nudge" them toward slightly slower but socially better routes. This paper investigates $\epsilon$-approximate Nash equilibria ($\epsilon$-NE), where drivers accept any route that is at most $1+\epsilon$ times slower than the fastest possible route. The core question is: How much can this small tolerance for delay improve or worsen the overall social cost?

Methods

The authors employ a primal-dual framework based on Lagrangian duality to derive tight upper and lower bounds for congestion games with polynomial latency functions (where travel time on an edge is a polynomial of the traffic volume).

Key technical steps include:

  • Cost Decomposition: Breaking down the difference in social cost between an exact Nash flow ($f$) and an approximate one ($f'$) into two terms: $T$ (the reduction in cost due to changing latencies) and $R$ (the additional cost incurred by the shift in traffic).
  • Unified Theorem: Developing a single theorem (Theorem 3.2) that provides lower bounds for various network structures by analyzing the relationship between $T$ and $R$.
  • Matching Instances: Constructing specific, worst-case network examples (like generalized Braess graphs and concatenations of Pigou's networks) to prove that their mathematical bounds are "tight"—meaning they cannot be improved further.

Datasets

As a theoretical paper in algorithmic game theory, this work does not use empirical datasets. Instead, it evaluates its findings using mathematical benchmarks and classic network topologies:

  • Pigou’s Network: A simple two-node, two-link network used to demonstrate basic inefficiency.
  • Braess Graphs: Famous examples where adding a road can actually increase travel time.
  • Series-Parallel Networks: A class of networks with a recursive structure known for "benign" behavior in traffic modeling.

Key Insights and Ideas

  • The $\sqrt{\epsilon}$ vs. $\epsilon$ Gap: For general networks, the social cost can change by a factor of $\Theta(\sqrt{d\epsilon})$ for small tolerance $\epsilon$ and polynomial degree $d$. This means a 1% tolerance in travel time could potentially lead to a 10% change in total traffic efficiency. In contrast, series-parallel networks are more stable, with changes scaling linearly ($\Theta(\epsilon)$).
  • Topology over Path Length: The high sensitivity in general networks isn't just about how long the paths are; it's about the network's structure. Even in networks with very short paths (like Braess graphs), the $\sqrt{\epsilon}$ sensitivity persists.
  • Navigation App Potential: The results quantify the "steering power" of navigation platforms. If drivers are willing to accept slightly sub-optimal routes, platforms have significant room to reduce total congestion, especially in complex, non-series-parallel urban grids.
Visualizing the gap between general and series-parallel networks

Key Results

The paper establishes tight bounds on the ratio of the social cost of an $\epsilon$-NE ($C(f')$) to an exact Nash flow ($C(f)$).

Setting Bound on $C(f')/C(f)$ Small $\epsilon$ behavior
General Congestion Games $\geq 1 - \sqrt{d\epsilon} + O_d(\epsilon)$ $\Theta(\sqrt{d\epsilon})$ change
$\leq 1 + \sqrt{d\epsilon} + O_d(\epsilon)$
Series-Parallel (depth $h$) $\geq 1 - h\epsilon + O_{d,h}(\epsilon^2)$ $\Theta(h\epsilon)$ reduction
$\leq 1 + \epsilon$ $\Theta(\epsilon)$ increase
Summary of tight bounds for polynomial latencies

These results show that the social cost of approximate equilibria is much more "stable" on series-parallel networks than on general ones.

Limitations and Future Work

  • Latency Functions: While the paper provides some results for arbitrary monotone latencies, the most detailed tight bounds are specific to polynomial functions.
  • Atomic Games: The study focuses on "nonatomic" games (infinitesimal drivers). Extending these tight bounds to "atomic" games (where each driver has a non-negligible impact, like freight trucks) remains an open challenge.
  • Dynamic Traffic: The model is static. Real-world traffic is dynamic, and how approximate equilibria behave over time as congestion shifts is a promising area for future research.

Summary updated

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 $Θ(\sqrt{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.
BibTeX
@misc{cheng2026how,
  author = {Yu Cheng and Tianle Jiang},
  title = {{How Much Can Approximate Equilibria Change the Social Cost of Selfish Routing?}},
  year = {2026},
  eprint = {2611.01234},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2611.01234},
}

Loading related content...

Figure