Research map / Learning theory and algorithms / Submodular and game algorithms

Paradoxes of Game Theoretic Equilibria and Price of Anarchy

NeurIPS 2026 · Learning theory and algorithms › Submodular and game algorithms · approach: Correlated equilibria in sequential games · 0 citations (OpenAlex)

Read the paperCheck your idea against 108,967 papers

AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.

Argues via dynamical-systems analysis (strict saddles, Chetaev instability, Li-Yorke chaos, zero-trace Hessian) that worst-case PoA equilibria, interior Nash, CCE/CE/SCE, and non-atomic congestion-game PoA bounds are misaligned with the dynamics of learning in games, with several theorems on unbounded PoA under negative intercepts.

Problem

Whether static equilibrium concepts (NE, CE, CCE) and Price of Anarchy bounds are meaningful predictors of the behavior of gradient-based and no-regret learning dynamics, given that they discard C^1 vector-field information and time-averaging.

Approach

Reinterprets worst-case PoA equilibria as strict saddles or repellers of the potential under learning dynamics, shows interior NE are strategically insensitive, and constructs examples where PoA is unbounded under affine costs with negative intercepts, coarse/proximal equilibria support dominated strategies, and discrete-time learning in non-atomic congestion games yields Li-Yorke chaos with socia

Key results

• Worst-case pure NE in the 3-player double-cycle congestion game is shown to be a strict saddle with Hessian eigenvalue -4 and eigenvector (1,1,1), with zero trace of Hessian.
• Affine congestion games with negative intercepts (two agents, two strategies, four resources) have unbounded PoA, including pure PoA.
• For MWU in symmetric two-path games, once a > 2^(p+1)/p the period-2 orbit has empirical social cost ratio to optimum converging to 2^p as a grows.

Surprising findings

• Worst-case pure Nash equilibria that tightly bound PoA can be strict saddles or global maxima of the potential rather than attractors.
• Replicator dynamics in a 6-agent two-strategy polymatrix game can be chaotic while simultaneously minimizing swap regret at O(1/T) and time-averaging to interior Nash.

Limitations

• Excerpt is partially incomplete with placeholder citations and unfinished sections; several claims are stated without full proofs in the text.
• Results rely on stylized, minimal game constructions (two-path, small polymatrix games) whose generality is asserted rather than shown.
• Some claims (e.g., generic robustness, chaos in congestion games) are argued by remark rather than proven.

Experimental setup

Metrics: social cost ratio Hessian eigenvalues time-averaged social cost

Builds on: smoothness framework replicator dynamics multiplicative weights update Wonderful Life Utility Chetaev instability theorem

Closest papers by meaning

• Beating Price of Anarchy and Gradient Descent without Regret in Potential Games (ICLR 2024 · similarity 0.91)
• The route to chaos in routing games: When is price of anarchy too optimistic? (NeurIPS 2020 · similarity 0.91)
• Learning-Augmented Coordination Mechanisms (NeurIPS 2026 · similarity 0.89)
• No-Regret Learning Dynamics for Extensive-Form Correlated Equilibrium (NeurIPS 2020 · similarity 0.89)
• No-Regret Learning and Mixed Nash Equilibria: They Do Not Mix (NeurIPS 2020 · similarity 0.88)
• Mediator Interpretation and Faster Learning Algorithms for Linear Correlated Equilibria in General Sequential Games (ICLR 2024 · similarity 0.87)