TY - GEN

T1 - Symmetries and the complexity of pure nash equilibrium

AU - Brandt, Felix

AU - Fischer, Felix

AU - Holzer, Markus

N1 - Funding Information:
This material is based upon work supported by the Deutsche Forschungsgemeinschaft under grants BR 2312/3-1 and BR 2312/3-2. An extended abstract of an earlier version of the paper appeared in the Proceedings of the 24th International Symposium on Theoretical Aspects of Computer Science (STACS). We thank Jan Johannsen for helpful discussions on circuit complexity and local search, and Rob Powers for introducing the first author to the ambiguity of symmetry in games. We further thank the anonymous referees for helpful comments.

PY - 2007

Y1 - 2007

N2 - Strategic games may exhibit symmetries in a variety of ways. A common aspect, 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: identical payoff functions for all players and the ability to 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 Nash equilibria can be computed in TC0 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 make the difference between TC0-completeness and membership in AC0, while a growing number of actions renders the equilibrium problem NP-complete for three of the classes and PLS-complete for the most restricted class for which the existence of a pure Nash equilibrium is guaranteed. Finally, our results extend to wider classes of threshold symmetric games where players are unable to determine the exact number of players playing a certain action.

AB - Strategic games may exhibit symmetries in a variety of ways. A common aspect, 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: identical payoff functions for all players and the ability to 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 Nash equilibria can be computed in TC0 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 make the difference between TC0-completeness and membership in AC0, while a growing number of actions renders the equilibrium problem NP-complete for three of the classes and PLS-complete for the most restricted class for which the existence of a pure Nash equilibrium is guaranteed. Finally, our results extend to wider classes of threshold symmetric games where players are unable to determine the exact number of players playing a certain action.

UR - http://www.scopus.com/inward/record.url?scp=38049148776&partnerID=8YFLogxK

U2 - 10.1007/978-3-540-70918-3_19

DO - 10.1007/978-3-540-70918-3_19

M3 - Conference contribution

AN - SCOPUS:38049148776

SN - 9783540709176

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 212

EP - 223

BT - STACS 2007 - 24th Annual Symposium on Theoretical Aspects of Computer Science, Proceedings

PB - Springer Verlag

T2 - 24th Annual Symposium on Theoretical Aspects of Computer Science, STACS 2007

Y2 - 22 February 2007 through 24 February 2007

ER -