Paradoxes of Game Theoretic Equilibria and Price of Anarchy

• URL: http://arxiv.org/abs/2607.11752v1
• Date: Mon, 13 Jul 2026 16:09:35 GMT
• Title: Paradoxes of Game Theoretic Equilibria and Price of Anarchy
• Abstract summary: We show that reducing multi-agent learning to equilibrium obscures underlying dynamic disequilibrium and gameoretic bounds.<n>Worst-case pure Nash equilibria dictating robust Price of Anarchy bounds manifest as topologically unstable strict saddles.<n> projecting learning trajectories onto the discrete simplex of correlated play systematically accommodates non-rationalizable behavior.
• Score: 36.44731230315158
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: 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 $C^1$ 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 $Θ(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 $2^p$. These results necessitate re-evaluating worst-case equilibrium frameworks for dynamically grounded metrics.

Related papers

• Phi-Actor-Critic: Steering General-Sum Games to Pareto-Efficient Correlated Equilibria [3.061219970798378]
  Real-world multi-agent systems are often modeled as general-sum games where individual incentives conflict with collective welfare.<n>Standard deep multi-agent reinforcement learning (MARL) methods struggle with this problem.<n>We propose $$-Actor-Critic ($$-AC), a framework that leverages swap regret minimization to steer learning toward high-welfare correlated equilibria.
  arXiv  Detail & Related papers  (2026-06-09T16:40:26Z)
• Zeroth-Order Stackelberg Control in Combinatorial Congestion Games [24.797303933023567]
  We study Stackelberg (leader--follower) tuning of network parameters in congestion games.<n>We propose ZO-Stackelberg, which couples a projection-free Frank--Wolfe equilibrium solver with a zeroth-order outer update.<n> Experiments on real-world networks demonstrate that our method achieves orders-of-magnitude speedups over a differentiation-based baseline.
  arXiv  Detail & Related papers  (2026-02-26T17:52:08Z)
• Stability and Generalization of Push-Sum Based Decentralized Optimization over Directed Graphs [55.77845440440496]
  Push-based decentralized communication enables optimization over communication networks, where information exchange may be asymmetric.<n>We develop a unified uniform-stability framework for the Gradient Push (SGP) algorithm.<n>A key technical ingredient is an imbalance-aware generalization bound through two quantities.
  arXiv  Detail & Related papers  (2026-02-24T05:32:03Z)
• Barriers to Welfare Maximization with No-Regret Learning [68.66209476382213]
  We prove lower bounds for computing a near-optimal $T$-sparse CCE. In particular, we show that the inapproximability of maximum clique precludes attaining any non-trivial sparsity in time.
  arXiv  Detail & Related papers  (2024-11-04T00:34:56Z)
• On Tractable $Φ$-Equilibria in Non-Concave Games [53.212133025684224]
  We study tractable $Phi$-equilibria in non-concave games.<n>We show that when $Phi$ is finite, there exists an efficient uncoupled learning algorithm that converges to the corresponding $Phi$-equilibria.
  arXiv  Detail & Related papers  (2024-03-13T01:51:30Z)
• A Black-box Approach for Non-stationary Multi-agent Reinforcement Learning [53.83345471268163]
  We investigate learning the equilibria in non-stationary multi-agent systems. We show how to test for various types of equilibria by a black-box reduction to single-agent learning.
  arXiv  Detail & Related papers  (2023-06-12T23:48:24Z)
• Bayes correlated equilibria, no-regret dynamics in Bayesian games, and the price of anarchy [8.430481660019451]
  We present an efficient algorithm for minimizing untruthful swap regret with a sublinear upper bound.<n>We extend existing lower bounds on the price of anarchy based on the smoothness arguments from Bayes--Nash equilibria to equilibria.
  arXiv  Detail & Related papers  (2023-04-11T06:22:51Z)
• Follow-the-Regularized-Leader Routes to Chaos in Routing Games [23.497377573947382]
  We study the emergence of chaotic behavior of Follow-the-Regularized Leader (FoReL) dynamics in games. We show the existence of novel non-standard phenomena such as the coexistence of stable Nash equilibria and chaos in the same game. Although FoReL dynamics can be strange and non-equilibrating, we prove that the time average still converges to an exact equilibrium for any choice of learning rate and any scale of costs.
  arXiv  Detail & Related papers  (2021-02-16T06:40:31Z)
• No-regret learning and mixed Nash equilibria: They do not mix [64.37511607254115]
  We study the dynamics of "follow-the-regularized-leader" (FTRL) We show that any Nash equilibrium which is not strict cannot be stable and attracting under FTRL. This result has significant implications for predicting the outcome of a learning process.
  arXiv  Detail & Related papers  (2020-10-19T13:49:06Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.