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

The Complexity of Symmetric Equilibria in Min-Max Optimization and Team Zero-Sum Games

NeurIPS 2025 · Learning theory and algorithms › Submodular and game algorithms · approach: Zero-sum game learning dynamics · 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.

Shows that computing epsilon-Nash equilibria in 3-player adversarial team games is CLS-complete, and that symmetric first-order equilibria in symmetric min-max optimization (and symmetric NE in 3v3 team zero-sum polymatrix games) are PPAD-complete, via a symmetry-enforcing adversary gadget.

Problem

Complexity of computing Nash and first-order stationary points in min-max optimization, especially adversarial and two-team zero-sum games, and symmetric equilibria in symmetric min-max problems.

Approach

Reduces symmetric epsilon-NE in symmetric identical-payoff two-player games to adversarial team games by adding an adversary whose payoff penalizes asymmetry between the two team players, forcing x≈y without changing the equilibria; the same gadget yields PPAD-hardness for symmetric min-max and team zero-sum games.

Key results

• Computing epsilon-NE in 3-player (2 vs. 1) adversarial team games is CLS-complete, even for polymatrix games.
• Computing symmetric first-order Nash equilibria in symmetric min-max optimization is PPAD-complete even for quadratic functions, for epsilon = 1/n^c.
• Computing a symmetric 1/n^c-NE in symmetric 3 vs. 3 team zero-sum polymatrix games is PPAD-complete; finding non-symmetric fixed points of GDA in symmetric min-max is FNP-hard.

Surprising findings

• Adversarial team games with n=2 admit a unique Nash equilibrium supported on irrational numbers.
• Symmetric learning dynamics cannot converge to first-order Nash equilibria in polynomial time unless PPAD = P.

Limitations

• Strong (geometric) approximation of Nash equilibria in adversarial team games remains open.
• Complexity of computing general first-order Nash equilibria (GDAFixedPoint) is left open.

Experimental setup

Builds on: CLS-hardness of symmetric identical-payoff games GDAFixedPoint PPAD membership Daskalakis-Goldberg-Papadimitriou PPAD-hardness of Nash

Closest papers by meaning

• The Complexity of Two-Team Polymatrix Games with Independent Adversaries (ICLR 2025 · similarity 0.91)
• Computing Game Symmetries and Equilibria That Respect Them (AAAI 2025 · similarity 0.91)
• Towards convergence to Nash equilibria in two-team zero-sum games (ICLR 2023 · similarity 0.90)
• Learning Equilibria in Adversarial Team Markov Games: A Nonconvex-Hidden-Concave Min-Max Optimization Problem (NeurIPS 2024 · similarity 0.89)
• Certifying Concavity and Monotonicity in Games via Sum-of-Squares Hierarchies (NeurIPS 2025 · similarity 0.88)
• Securing Equal Share: A Principled Approach for Learning Multiplayer Symmetric Games (ICML 2025 · similarity 0.88)