Equilibria of graphical games with symmetries

Felix Brandt, Felix Fischer, Markus Holzer

Research output: Contribution to journalArticlepeer-review

4 Scopus citations

Abstract

We study graphical games where the payoff function of each player satisfies one of four types of symmetry in the actions of his neighbors. We establish that deciding the existence of a pure Nash equilibrium is NP-hard in general for all four types. Using a characterization of games with pure equilibria in terms of even cycles in the neighborhood graph, as well as a connection to a generalized satisfiability problem, we identify tractable subclasses of the games satisfying the most restrictive type of symmetry. Hardness for a different subclass leads us to identify a satisfiability problem that remains NP-hard in the presence of a matching, a result that may be of independent interest. Finally, games with symmetries of two of the four types are shown to possess a symmetric mixed equilibrium which can be computed in polynomial time. We thus obtain a natural class of games where the pure equilibrium problem is computationally harder than the mixed equilibrium problem, unless P=NP.

Original languageEnglish
Pages (from-to)675-685
Number of pages11
JournalTheoretical Computer Science
Volume412
Issue number8-10
DOIs
StatePublished - 4 Mar 2011

Keywords

  • Algorithmic game theory
  • Computational complexity
  • Graphical games
  • Nash equilibria
  • Symmetries

Fingerprint

Dive into the research topics of 'Equilibria of graphical games with symmetries'. Together they form a unique fingerprint.

Cite this