Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR07-136 | 28th November 2007 00:00

Equilibria of Graphical Games with Symmetries

RSS-Feed




TR07-136
Authors: Felix Brandt, Felix Fischer, Markus Holzer
Publication: 29th December 2007 02:40
Downloads: 1764
Keywords: 


Abstract:

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