Journal article

Publication year: 2011

Pages: 675-685

Journal: Theoretical Computer Science

Volume number: 412

Issue number: 8-10

ISSN: 0304-3975

eISSN: 1879-2294

DOI Link: https://doi.org/10.1016/j.tcs.2010.11.002

Publisher: Elsevier

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. (C) 2010 Elsevier B.V. All rights reserved.

Harvard Citation style: Brandt, F., Fischer, F. and Holzer, M. (2011) Equilibria of graphical games with symmetries, Theoretical Computer Science, 412(8-10), pp. 675-685. https://doi.org/10.1016/j.tcs.2010.11.002

APA Citation style: Brandt, F., Fischer, F., & Holzer, M. (2011). Equilibria of graphical games with symmetries. Theoretical Computer Science. 412(8-10), 675-685. https://doi.org/10.1016/j.tcs.2010.11.002