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.

dx.doi.org/10.4204/EPTCS.215.6
Electronic Proceedings in Theoretical Computer Science
The 15th Conference on Theoretical Aspects of Rationality and Knowledge (TARK)
This work was funded by the The Netherlands Organisation for Scientific Research (NWO); grant id nwo/612.001.352 - Combining Machine Learning and Game-theoretic Approaches for Cluster Analysis
CWI management

Apt, K.R, Simon, S.E, & Wojtczak, D.K. (2016). Coordination games on directed graphs. In Electronic Proceedings in Theoretical Computer Science. doi:10.4204/EPTCS.215.6