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

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

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 12 Feb 2025.

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

- [The Complexity of Finding Local Optima in Contrastive Learning](https://mlsanity.com/paper/2509.16898/) (2025)
- [The Complexity of Min-Max Optimization for Quadratic Polynomials](https://mlsanity.com/paper/2606.17000/) (2026)

## Abstract (arXiv)

We consider the problem of computing stationary points in min-max optimization, with a particular focus on the special case of computing Nash equilibria in (two-)team zero-sum games. We first show that computing ε-Nash equilibria in 3-player adversarial team games -- wherein a team of 2 players competes against a single adversary -- is textsfCLS-complete, resolving the complexity of Nash equilibria in such settings. Our proof proceeds by reducing from symmetric ε-Nash equilibria in symmetric, identical-payoff, two-player games, by suitably leveraging the adversarial player so as to enforce symmetry -- without disturbing the structure of the game. In particular, the class of instances we construct comprises solely polymatrix games, thereby also settling a question left open by Hollender, Maystre, and Nagarajan (2024). We also provide some further results concerning equilibrium computation in adversarial team games. Moreover, we establish that computing symmetric (first-order) equilibria in symmetric min-max optimization is textsfPPAD-complete, even for quadratic functions. Building on this reduction, we further show that computing symmetric ε-Nash equilibria in symmetric, 6-player (3 vs. 3) team zero-sum games is also textsfPPAD-complete, even for ε = poly(1/n). As an immediate corollary, this precludes the existence of symmetric dynamics -- which includes many of the algorithms considered in the literature -- converging to stationary points. Finally, we prove that computing a non-symmetric poly(1/n)-equilibrium in symmetric min-max optimization is textsfFNP-hard.