# The route to chaos in routing games: When is Price of Anarchy too optimistic?

arXiv: https://arxiv.org/abs/1906.02486 · HTML: https://mlsanity.com/paper/1906.02486/

## Key facts

- Cited by 15 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 6 Jun 2019.

## Built on by (most cited first, 15 of 15)

- [Adaptive Learning in Continuous Games: Optimal Regret Bounds and Convergence to Nash Equilibrium](https://mlsanity.com/paper/2104.12761/) (2021)
- [Multi-agent Performative Prediction: From Global Stability and Optimality to Chaos](https://mlsanity.com/paper/2201.10483/) (2022)
- [Scaling up Mean Field Games with Online Mirror Descent](https://mlsanity.com/paper/2103.00623/) (2021)
- [Alternating Mirror Descent for Constrained Min-Max Games](https://mlsanity.com/paper/2206.04160/) (2022)
- [Learning in Matrix Games can be Arbitrarily Complex](https://mlsanity.com/paper/2103.03405/) (2021)
- [Follow-the-Regularized-Leader Routes to Chaos in Routing Games](https://mlsanity.com/paper/2102.07974/) (2021)
- [Lyapunov Exponents for Diversity in Differentiable Games](https://mlsanity.com/paper/2112.14570/) (2021)
- [Nash, Conley, and Computation: Impossibility and Incompleteness in Game Dynamics](https://mlsanity.com/paper/2203.14129/) (2022)
- [Evolutionary Dynamics and Phi-Regret Minimization in Games](https://mlsanity.com/paper/2106.14668/) (2021)
- [On the Stability of Learning in Network Games with Many Players](https://mlsanity.com/paper/2403.15848/) (2024)
- [Swim till You Sink: Computing the Limit of a Game](https://mlsanity.com/paper/2408.11146/) (2024)
- [Regret Minimization in Population Network Games: Vanishing Heterogeneity and Convergence to Equilibria](https://mlsanity.com/paper/2507.17183/) (2025)
- [Chaos persists in large-scale multi-agent learning despite adaptive learning rates](https://mlsanity.com/paper/2306.01032/) (2023)
- [Inequality in Congestion Games with Learning Agents](https://mlsanity.com/paper/2601.20578/) (2026)
- [Natural Invariant Measures for Chaotic Game Dynamics: Finding Order in Chaos](https://mlsanity.com/paper/2607.21805/) (2026)

## Abstract (arXiv)

Routing games are amongst the most studied classes of games. Their two most well-known properties are that learning dynamics converge to equilibria and that all equilibria are approximately optimal. In this work, we perform a stress test for these classic results by studying the ubiquitous dynamics, Multiplicative Weights Update, in different classes of congestion games, uncovering intricate non-equilibrium phenomena. As the system demand increases, the learning dynamics go through period-doubling bifurcations, leading to instabilities, chaos and large inefficiencies even in the simplest case of non-atomic routing games with two paths of linear cost where the Price of Anarchy is equal to one. Starting with this simple class, we show that every system has a carrying capacity, above which it becomes unstable. If the equilibrium flow is a symmetric 50-50% split, the system exhibits one period-doubling bifurcation. A single periodic attractor of period two replaces the attracting fixed point. Although the Price of Anarchy is equal to one, in the large population limit the time-average social cost for all but a zero measure set of initial conditions converges to its worst possible value. For asymmetric equilibrium flows, increasing the demand eventually forces the system into Li-Yorke chaos with positive topological entropy and periodic orbits of all possible periods. Remarkably, in all non-equilibrating regimes, the time-average flows on the paths converge exactly to the equilibrium flows, a property akin to no-regret learning in zero-sum games. These results are robust. We extend them to routing games with arbitrarily many strategies, polynomial cost functions, non-atomic as well as atomic routing games and heteregenous users. Our results are also applicable to any sequence of shrinking learning rates, e.g., 1/√T, by allowing for a dynamically increasing population size.