Paradoxes of Game Theoretic Equilibria and Price of Anarchy

Static equilibria—Nash, Correlated (CE), and Coarse Correlated Equilibria (CCE)—and the Price of Anarchy (PoA) provide essential, tractable benchmarks for multi-agent systems. However, evaluating learning dynamics purely through $C^0$ fixed points and discrete empirical distributions abstracts away critical $C^1$ vector field information. We demonstrate that this reduction diverges significantly from physical learning trajectories. First, the worst-case pure Nash equilibria anchoring canonical PoA bounds mathematically manifest as strict saddles—and in canonical instances, even as global maxima of the exact potential; because they are topologically unstable repellers, natural learning actively bypasses these theoretical inefficiency bounds. Additionally, the PoA metric itself exhibits algebraic sensitivity; relaxing syntactic constraints to accommodate data-driven, strictly positive affine cost models renders the Price of Anarchy unbounded. Furthermore, evaluating algorithms strictly through time-averaged regret minimization to reach CCE or Proximal CE (PCE) structurally permits convergence to strictly dominated strategies. Even enforcing optimal $O(1/T)$ swap-regret minimization provably accommodates chaotic limit sets in minimal normal-form games. Finally, in non-atomic congestion games, discrete-time learning natively bifurcates into Li-Yorke chaos, driving time-averaged inefficiency to scale exponentially as $2^p$, diverging from static sub-linear bounds. Collectively, these findings highlight the necessity of augmenting classical algebraic frameworks with dynamically grounded metrics.