Efficient Local Search in Coordination Games on Graphs

Simon, S and Wojtczak, DK ORCID: 0000-0001-5560-0546 (2016) Efficient Local Search in Coordination Games on Graphs. In: 25th International Joint Conference on Artificial Intelligence IJCAI-16.

Access the full-text of this item by clicking on the Open Access link.

Text main.pdf - Submitted version Download (334kB)

Abstract

We study strategic games on weighted directed graphs, where the payoff of a player is defined as the sum of the weights on the edges from players who chose the same strategy augmented by a fixed non-negative bonus for picking a given strategy. These games capture the idea of coordination in the absence of globally common strategies. Prior work shows that the problem of determining the existence of a pure Nash equilibrium for these games is NP-complete already for graphs with all weights equal to one and no bonuses. However, for several classes of graphs (e.g. DAGs and cliques) pure Nash equilibria or even strong equilibria always exist and can be found by simply following a particular improvement or coalition-improvement path, respectively. In this paper we identify several natural classes of graphs for which a finite improvement or coalition-improvement path of polynomial length always exists, and, as a consequence, a Nash equilibrium or strong equilibrium in them can be found in polynomial time. We also argue that these results are optimal in the sense that in natural generalisations of these classes of graphs, a pure Nash equilibrium may not even exist.

Item Type:	Conference or Workshop Item (Unspecified)
Additional Information:	Extended version of a paper accepted to IJCAI16
Uncontrolled Keywords:	cs.GT, cs.GT, cs.MA
Depositing User:	Symplectic Admin
Date Deposited:	06 Sep 2016 10:09
Last Modified:	19 Jan 2023 07:35
Open Access URL:	https://arxiv.org/pdf/1604.04809v1.pdf
Related URLs:	Author
URI:	https://livrepository.liverpool.ac.uk/id/eprint/3001780