Coordination Games on Directed Graphs

Apt, Krzysztof R, Simon, Sunil and Wojtczak, Dominik ORCID: 0000-0001-5560-0546 (2016) Coordination Games on Directed Graphs. In: Theoretical Aspects of Rationality and Knowledge (TARK).

Text direc-150830201511300051.pdf - Unspecified Download (483kB)

Abstract

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.

Item Type:	Conference or Workshop Item (Paper)
Additional Information:	In Proceedings TARK 2015, arXiv:1606.07295
Uncontrolled Keywords:	cs.GT, cs.GT
Depositing User:	Symplectic Admin
Date Deposited:	01 Dec 2015 17:00
Last Modified:	24 Jan 2023 20:35
DOI:	10.4204/EPTCS.215.6
Publisher's Statement :	© K. R. Apt, S. Simon & D. Wojtczak This work is licensed under the Creative Commons Attribution License.
Related URLs:	Author Publisher
URI:	https://livrepository.liverpool.ac.uk/id/eprint/2040088