Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



TR06-091 | 29th May 2006 00:00

Symmetries and the Complexity of Pure Nash Equilibrium



Strategic games may exhibit symmetries in a variety of ways. A common aspect of symmetry, enabling the compact representation of games even when the number of players is unbounded, is that players cannot (or need not) distinguish between the other players. We define four classes of symmetric games by considering two additional properties: \emph{identical payoff functions} for all players and the ability to \emph{distinguish oneself} from the other players. Based on these varying notions of symmetry, we investigate the computational complexity of pure Nash equilibria. It turns out that in all four classes of games equilibria can be found efficiently when only a constant number of actions is available to each player, a problem that has been shown intractable for other succinct representations of multi-player games. We further show that identical payoff functions simplify the search for equilibria, while a growing number of actions renders it intractable. Finally, we show that our results extend to wider classes of \emph{threshold symmetric} games where players are unable to determine the exact number of players playing a certain action.

ISSN 1433-8092 | Imprint