Symmetries and the complexity of pure Nash equilibrium

摘要

Strategic games may exhibit symmetries in a variety of ways. A characteristic feature, 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 investigate the computational complexity of pure Nash equilibria in four classes of symmetric games obtained by considering two additional properties: identical payoff functions for all players and the ability to distinguish oneself from the other players. In contrast to other types of succinctly representable multi-player games, the pure equilibrium problem is tractable in all four classes when only a constant number of actions is available to each player. Identical payoff functions make the difference between TC0-completeness and membership in AC0, while a growing number of actions renders the equilibrium problem NP-hard for three of the classes and PLS-hard for the most restricted class for which the existence of a pure equilibrium is guaranteed. Our results also extend to larger classes of threshold symmetric games where players are unable to determine the exact number of players playing a certain action.