# Computing Game Symmetries and Equilibria That Respect Them

arXiv: https://arxiv.org/abs/2501.08905 · HTML: https://mlsanity.com/paper/2501.08905/

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- Builds on 12 of its 71 references that are in the map.
- First posted on arXiv 15 Jan 2025.

## Builds on (most cited first, 12 of 12)

- ["Other-Play" for Zero-Shot Coordination](https://mlsanity.com/paper/2003.02979/) (2020)
- [A New Formalism, Method and Open Issues for Zero-Shot Coordination](https://mlsanity.com/paper/2106.06613/) (2021)
- [Graphical Models for Game Theory](https://mlsanity.com/paper/1301.2281/) (2013)
- [The Complexity of Gradient Descent: CLS = PPAD cap PLS](https://mlsanity.com/paper/2011.01929/) (2020)
- [Game Theory with Simulation of Other Players](https://mlsanity.com/paper/2305.11261/) (2023)
- [Turbocharging Solution Concepts: Solving NEs, CEs and CCEs with Neural Equilibrium Solvers](https://mlsanity.com/paper/2210.09257/) (2022)
- [For Learning in Symmetric Teams, Local Optima are Global Nash Equilibria](https://mlsanity.com/paper/2207.03470/) (2022)
- [Game Transformations That Preserve Nash Equilibria or Best-Response Sets](https://mlsanity.com/paper/2111.00076/) (2021)
- [The Computational Complexity of Single-Player Imperfect-Recall Games](https://mlsanity.com/paper/2305.17805/) (2023)
- [Imperfect-Recall Games: Equilibrium Concepts and Their Complexity](https://mlsanity.com/paper/2406.15970/) (2024)
- [The Complexity of Symmetric Bimatrix Games with Common Payoffs](https://mlsanity.com/paper/2410.08031/) (2024)
- [Settling Some Open Problems on 2-Player Symmetric Nash Equilibria](https://mlsanity.com/paper/1412.0969/) (2014)

## Built on by (most cited first, 4 of 4)

- [Convergence of Regret Matching in Potential Games and Constrained Optimization](https://mlsanity.com/paper/2510.17067/) (2025)
- [Decision Making under Imperfect Recall: Algorithms and Benchmarks](https://mlsanity.com/paper/2602.15252/) (2026)
- [Do LLMs Take Care of Their Own? Similarity Signals Can Induce Cooperation](https://mlsanity.com/paper/2608.12125/) (2026)
- [On Symmetry for Characterizing Agent Heterogeneity in Multi-Agent Systems](https://mlsanity.com/paper/2610.18538/) (2026)

## Abstract (arXiv)

Strategic interactions can be represented more concisely, and analyzed and solved more efficiently, if we are aware of the symmetries within the multiagent system. Symmetries also have conceptual implications, for example for equilibrium selection. We study the computational complexity of identifying and using symmetries. Using the classical framework of normal-form games, we consider game symmetries that can be across some or all players and/or actions. We find a strong connection between game symmetries and graph automorphisms, yielding graph automorphism and graph isomorphism completeness results for characterizing the symmetries present in a game. On the other hand, we also show that the problem becomes polynomial-time solvable when we restrict the consideration of actions in one of two ways. Next, we investigate when exactly game symmetries can be successfully leveraged for Nash equilibrium computation. We show that finding a Nash equilibrium that respects a given set of symmetries is PPAD- and CLS-complete in general-sum and team games respectively -- that is, exactly as hard as Brouwer fixed point and gradient descent problems. Finally, we present polynomial-time methods for the special cases where we are aware of a vast number of symmetries, or where the game is two-player zero-sum and we do not even know the symmetries.