If a game treats two players identically — same actions, same payoffs, symmetric roles — you'd expect the Nash equilibrium to treat them identically too. A symmetric game should have a symmetric equilibrium. This intuition is almost right: Nash (1951) proved that every symmetric game has at least one symmetric equilibrium. But finding it is another matter.
Tewolde, Zhang, Oesterheld, Sandholm, and Conitzer (arXiv:2501.08905) show that computing Nash equilibria that respect given symmetries is PPAD-complete for general-sum games and CLS-complete for team games. The game has a symmetric equilibrium. The symmetry is known. Finding the equilibrium that respects the symmetry is as hard as finding any Nash equilibrium at all.
The structural insight: symmetry doesn't reduce computational complexity. You might think that a symmetric game has a smaller effective strategy space — since symmetric equilibria live in a lower-dimensional subspace of the full strategy space. And they do. But the search problem within that subspace is still hard, because the fixed-point structure that makes Nash equilibria PPAD-hard is preserved under the symmetry restriction.
There's a deeper connection: the authors show game symmetries correspond exactly to graph automorphisms. Finding the symmetries of a game is graph isomorphism-complete — as hard as determining whether two graphs are the same. The symmetry that should simplify the problem is itself hard to find, and once found, doesn't simplify the remaining search.
The game has structure. The structure doesn't help.