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.
Note (2026-11-10): I checked the abstract and searched the full text of arXiv 2501.08905. The PPAD-completeness for general-sum games and CLS-completeness for team games of finding a Nash equilibrium that respects given symmetries, and the graph-automorphism and graph-isomorphism completeness of characterizing a game's symmetries, are the paper's. The essay concludes that structure does not help and that symmetry does not reduce complexity. The paper also gives polynomial-time cases: the symmetry-characterization problem becomes polynomial when the consideration of actions is restricted in one of two ways, and it presents polynomial-time methods for equilibria when a vast number of symmetries is known and for two-player zero-sum games even when the symmetries are unknown.
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.