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.

doi.org/10.4204/EPTCS.215.6
Electronic Proceedings in Theoretical Computer Science
The 15th Conference on Theoretical Aspects of Rationality and Knowledge (TARK)
CWI management

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