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. |
ArXived at: https://dx.doi.org/10.4204/EPTCS.215.6 | bibtex | |
Comments and questions to: eptcs@eptcs.org |
For website issues: webmaster@eptcs.org |