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

Computing Game Symmetries and Equilibria That Respect Them

AAAI 2025 · Learning theory and algorithms › Submodular and game algorithms · approach: Correlated equilibria in sequential games · 3 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.

Studies the complexity of identifying game symmetries (graph automorphism/isomorphism-complete in general) and of computing Nash equilibria that respect a given set of symmetries (PPAD-complete in general-sum, CLS-complete in team games, polynomial for few orbits and for two-player zero-sum games).

Problem

Identifying symmetries of normal-form games and computing Nash equilibria that respect those symmetries, including the computational complexity of both tasks.

Approach

Connects game symmetries to graph automorphisms and isomorphisms via a graph construction, yielding tight complexity classifications; shows symmetry-respecting Nash equilibria reduce to orbit-level computation, and that two-player zero-sum equilibria can respect all symmetries in polytime without computing them, via an entropy-like strictly convex regularizer.

Key results

• Deciding whether a normal-form game has a nontrivial symmetry is GI-complete... actually GA-complete (graph automorphism-complete), even for two-player zero-sum or team games with player-separable symmetries.
• Finding a Nash equilibrium that respects given symmetries is PPAD-complete in general-sum games and CLS-complete in team games.
• Two-player zero-sum games admit an exact Nash equilibrium respecting all game symmetries in polynomial time, without computing the symmetries.

Surprising findings

• Respecting symmetries can force players into lower-payoff equilibria (e.g., coordination game where the symmetric equilibrium yields 4 vs 12 for the best coordinated outcome).
• Symmetry-respecting equilibrium in team games is CLS-hard even for totally symmetric five-player games, so gradient descent is essentially the best one can do.

Limitations

• Results focus on exact symmetries; approximate symmetries are left to future work.
• Analysis is restricted to normal-form (explicit) games; graphical games are already hard to characterize by symmetry.

Experimental setup

Builds on: Nash existence via Brouwer fixed point PPAD CLS graph isomorphism

Closest papers by meaning

• The Complexity of Symmetric Equilibria in Min-Max Optimization and Team Zero-Sum Games (NeurIPS 2025 · similarity 0.91)
• ${\rm E}(3)$-Equivariant Actor-Critic Methods for Cooperative Multi-Agent Reinforcement Learning (ICML 2024 · similarity 0.87)
• Securing Equal Share: A Principled Approach for Learning Multiplayer Symmetric Games (ICML 2025 · similarity 0.87)
• The Complexity of Computing Robust Mediated Equilibria in Ordinal Games (AAAI 2024 · similarity 0.86)
• Certifying Concavity and Monotonicity in Games via Sum-of-Squares Hierarchies (NeurIPS 2025 · similarity 0.86)
• Playing Markov Games Without Observing Payoffs (NeurIPS 2026 · similarity 0.86)