Nash-Preserving Symmetry Reductions for Markov Games

The standard solution concept for a Markov game is the Nash equilibrium, a joint policy at which no agent gains by deviating alone. Symmetry can make such a game much smaller, but the smaller game is useful only if an equilibrium found there is still an equilibrium of the original. This is not automatic: a symmetric policy that no agent can improve on within the symmetric class may still be beaten by an asymmetric deviation, so a reduction is trustworthy only if the Nash gap it reports matches the true one. We give two reductions that meet this test exactly. Symmetry among states collapses the game to one on groups of equivalent states; symmetry among interchangeable agents replaces their separate policies with a single shared one. Each preserves the Nash gap against all deviations, not merely symmetric ones, and the two combine when compatible. Because the reduced gap is the true one, we use it in three ways: to tighten existing convergence bounds, to derive a new one for shared policies that exposes the cost of tying agents together, and to cut the samples a generative model needs by pooling symmetric queries. Experiments on cooperative and zero-sum tabular games confirm that the reductions preserve equilibria and accelerate policy optimization.