How can game symmetries speed up Nash equilibrium computation?
Computing Game Symmetries and Equilibria That Respect Them
This paper explores symmetries in multi-agent games and their impact on finding equilibrium solutions. It demonstrates that identifying general symmetries is computationally hard (graph isomorphism complete) but becomes easier with constraints like player-separable symmetries or a limited number of orbits. Finding a symmetric equilibrium is generally as hard as finding any equilibrium, but becomes tractable with many symmetries or in two-player zero-sum games.
For LLM-based multi-agent systems, this research suggests: (1) Leveraging symmetries can simplify representation and computation if enough symmetries are present, particularly in systems with many agents or limited action spaces. (2) Enforcing symmetric solutions may sacrifice optimality and therefore should be considered carefully, particularly in cooperative settings. (3) Designing systems with inherent symmetries may ease LLM reasoning and solution finding, particularly when combined with explicit symmetry-respecting algorithms. (4) Even without explicit symmetry detection, methods exist for finding symmetric equilibria in some LLM-compatible game representations, especially in competitive settings.