2016-06-23
Coordination games on directed graphs
Publication
Publication
Presented at the
The 15th Conference on Theoretical Aspects of Rationality and Knowledge (TARK) (June 2015), Carnegie Mellon University, Pittsburgh, USA
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.
| Additional Metadata | |
|---|---|
| doi.org/10.4204/EPTCS.215.6 | |
| Electronic Proceedings in Theoretical Computer Science | |
| The 15th Conference on Theoretical Aspects of Rationality and Knowledge (TARK) | |
| Organisation | 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 |
|
