Anzeige
Erschienen in:
2011 | OriginalPaper | Buchkapitel
Pairwise-Interaction Games
verfasst von : Martin Dyer, Velumailum Mohanaraj
Erschienen in: Automata, Languages and Programming
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
We study the complexity of computing Nash equilibria in games where players arranged as the vertices of a graph play a
symmetric
2
-player game
against their neighbours. We call this a
pairwise-interaction game
. We analyse this game for
n
players with a fixed number of actions and show that (1) a mixed Nash equilibrium can be computed in constant time for any game, (2) a pure Nash equilibrium can be computed through Nash dynamics in polynomial time for games with a symmetrisable payoff matrix, (3) determining whether a pure Nash equilibrium exists for zero-sum games is NP-complete, and (4) counting pure Nash equilibria is #P-complete even for 2-strategy games. In proving (3), we define a new
defective
graph colouring problem called
Nash colouring
, which is of independent interest, and prove that its decision version is NP-complete. Finally, we show that pairwise-interaction games form a proper subclass of the usual graphical games.