Symmetries and the complexity of pure nash equilibrium

Felix Brandt, Felix Fischer, Markus Holzer

Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

4 Scopus citations

Abstract

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.

Original languageEnglish
Title of host publicationSTACS 2007 - 24th Annual Symposium on Theoretical Aspects of Computer Science, Proceedings
PublisherSpringer Verlag
Pages212-223
Number of pages12
ISBN (Print)9783540709176
DOIs
StatePublished - 2007
Externally publishedYes
Event24th Annual Symposium on Theoretical Aspects of Computer Science, STACS 2007 - Aachen, Germany
Duration: 22 Feb 200724 Feb 2007

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume4393 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference24th Annual Symposium on Theoretical Aspects of Computer Science, STACS 2007
Country/TerritoryGermany
CityAachen
Period22/02/0724/02/07

Fingerprint

Dive into the research topics of 'Symmetries and the complexity of pure nash equilibrium'. Together they form a unique fingerprint.

Cite this