Coordination Games on Directed Graphs

Krzysztof R. Apt
(Centrum Wiskunde and Informatica, Amsterdam, The Netherlands)
Sunil Simon
(Department of CSE, IIT Kanpur, Kanpur, India)
Dominik Wojtczak
(University of Liverpool, Liverpool, U.K.)

We study natural strategic games on directed graphs, which capture the idea of coordination in the absence of globally common strategies. We show that these games do not need to have a pure Nash equilibrium and that the problem of determining their existence is NP-complete. The same holds for strong equilibria. We also exhibit some classes of games for which strong equilibria exist and prove that a strong equilibrium can then be found in linear time.

In R Ramanujam: Proceedings Fifteenth Conference on Theoretical Aspects of Rationality and Knowledge (TARK 2015), Carnegie Mellon University, Pittsburgh, USA, June 4-6, 2015, Electronic Proceedings in Theoretical Computer Science 215, pp. 67–80.
Published: 23rd June 2016.

ArXived at: http://dx.doi.org/10.4204/EPTCS.215.6 bibtex PDF
References in reconstructed bibtex, XML and HTML format (approximated).
Comments and questions to: eptcs@eptcs.org
For website issues: webmaster@eptcs.org