# Paradoxes of Game Theoretic Equilibria and Price of Anarchy

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 9 of its 116 references that are in the map.
- First posted on arXiv 13 Jul 2026.

## Builds on (most cited first, 9 of 9)

- [V-Learning -- A Simple, Efficient, Decentralized Algorithm for Multiagent RL](https://mlsanity.com/paper/2110.14555/) (2021)
- [When Can We Learn General-Sum Markov Games with a Large Number of Players Sample-Efficiently?](https://mlsanity.com/paper/2110.04184/) (2021)
- [α-Rank: Multi-Agent Evaluation by Evolution](https://mlsanity.com/paper/1903.01373/) (2019)
- [Gradient Descent Only Converges to Minimizers: Non-Isolated Critical Points and Invariant Regions](https://mlsanity.com/paper/1605.00405/) (2016)
- [Full Swap Regret and Discretized Calibration](https://mlsanity.com/paper/2502.09332/) (2025)
- [Gradient Equilibrium in Online Learning: Theory and Applications](https://mlsanity.com/paper/2501.08330/) (2025)
- [Faster No-Regret Learning Dynamics for Extensive-Form Correlated and Coarse Correlated Equilibria](https://mlsanity.com/paper/2202.05446/) (2022)
- [Efficient Phi-Regret Minimization with Low-Degree Swap Deviations in Extensive-Form Games](https://mlsanity.com/paper/2402.09670/) (2024)
- [Polynomial-Time Computation of Exact Phi-Equilibria in Polyhedral Games](https://mlsanity.com/paper/2402.16316/) (2024)

## Abstract (arXiv)

For decades, static solution concepts (Nash, Correlated, and Coarse Correlated Equilibria) and the Price of Anarchy (PoA) have formed the bedrock of algorithmic game theory, with no-regret learning proving fast convergence to such game-theoretic equilibria. We show that reducing multi-agent learning to static equilibrium and black-box regret analysis obscures underlying dynamic disequilibrium and game theoretic bounds. First, interior Nash equilibria lack C1 vector field information, meaning agents cannot distinguish aligned from strictly opposing incentives. Inheriting this geometry, the worst-case pure Nash equilibria dictating robust PoA bounds manifest as topologically unstable strict saddles, and in canonical congestion games, as global repellers supported on almost everywhere strictly dominated strategies. Anchoring efficiency guarantees to these unstable states causes algebraic sensitivity; we prove that accommodating all strictly positive affine costs renders the PoA unbounded. Furthermore, projecting learning trajectories onto the discrete simplex of correlated play systematically accommodates non-rationalizable behavior. Evaluating dynamics via Coarse Correlated Equilibria or proximal refinements fails to preclude strictly dominated strategies. Moreover, optimal O(1/T) swap-regret minimization does not preclude macroscopic turbulence, manifesting as chaotic limit sets even in minimal games. Finally, we examine the non-atomic limit of congestion games. Though considered highly stable with tight sub-linear Theta(p/ln p) PoA bounds (where p is the polynomial degree), we prove that under discrete-time learning, the unique equilibrium destabilizes into Li-Yorke chaos and global attractors whose time-averaged inefficiency degrades exponentially as 2p. These results necessitate re-evaluating worst-case equilibrium frameworks for dynamically grounded metrics.