2007 | OriginalPaper | Buchkapitel
Symmetries and the Complexity of Pure Nash Equilibrium
Extended Abstract
verfasst von : Felix Brandt, Felix Fischer, Markus Holzer
Erschienen in: STACS 2007
Verlag: Springer Berlin Heidelberg
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
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 TC
0
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 TC
0
-completeness and membership in AC
0
, 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.