TY - JOUR

T1 - Equilibria of graphical games with symmetries

AU - Brandt, Felix

AU - Fischer, Felix

AU - Holzer, Markus

N1 - Funding Information:
This material is based upon work supported by the Deutsche Forschungsgemeinschaft under grant BR 2312/3-2. We are grateful to Michael Tautschnig for providing us with a customized version of his ABsolver software.

PY - 2011/3/4

Y1 - 2011/3/4

N2 - 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.

AB - 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.

KW - Algorithmic game theory

KW - Computational complexity

KW - Graphical games

KW - Nash equilibria

KW - Symmetries

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

U2 - 10.1016/j.tcs.2010.11.002

DO - 10.1016/j.tcs.2010.11.002

M3 - Article

AN - SCOPUS:79151481834

SN - 0304-3975

VL - 412

SP - 675

EP - 685

JO - Theoretical Computer Science

JF - Theoretical Computer Science

IS - 8-10

ER -