Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



TR07-136 | 28th November 2007 00:00

Equilibria of Graphical Games with Symmetries


Authors: Felix Brandt, Felix Fischer, Markus Holzer
Publication: 29th December 2007 02:40
Downloads: 3977


We study graphical games where the payoff function of each player satisfies one of four types of symmetries in the actions of his neighbors. We establish that deciding the existence of a pure Nash equilibrium is NP-hard in graphical games with each of the four types of symmetry. 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. In the process, we characterize 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 have thus identified a class of games where the pure equilibrium problem is computationally harder than the mixed equilibrium problem, unless P=NP.

ISSN 1433-8092 | Imprint