Coordination Games on Weighted Directed Graphs

Apt, Krzysztof R, Simon, Sunil and Wojtczak, Dominik ORCID: 0000-0001-5560-0546 (2021) Coordination Games on Weighted Directed Graphs. Mathematics of Operations Research, 47 (2). pp. 995-1025.

Text
1910.02693.pdf - Author Accepted Manuscript
Download (498kB) | Preview

Official URL: http://dx.doi.org/10.1287/moor.2021.1159

Abstract

<jats:p> We study strategic games on weighted directed graphs, where each player’s payoff is defined as the sum of the weights on the edges from players who chose the same strategy, augmented by a fixed nonnegative integer bonus for picking a given strategy. These games capture the idea of coordination in the absence of globally common strategies. We identify natural classes of graphs for which finite improvement or coalition-improvement paths of polynomial length always exist, and consequently a (pure) Nash equilibrium or a strong equilibrium can be found in polynomial time. The considered classes of graphs are typical in network topologies: simple cycles correspond to the token ring local area networks, whereas open chains of simple cycles correspond to multiple independent rings topology from the recommendation G.8032v2 on Ethernet ring protection switching. For simple cycles, these results are optimal in the sense that without the imposed conditions on the weights and bonuses, a Nash equilibrium may not even exist. Finally, we prove that determining the existence of a Nash equilibrium or of a strong equilibrium is NP-complete already for unweighted graphs, with no bonuses assumed. This implies that the same problems for polymatrix games are strongly NP-hard. </jats:p>

Item Type:	Article
Uncontrolled Keywords:	noncooperative games, coordination games, Nash equilibrium, strong equilibrium, computational complexity
Divisions:	Faculty of Science and Engineering > School of Electrical Engineering, Electronics and Computer Science
Depositing User:	Symplectic Admin
Date Deposited:	14 Oct 2021 07:35
Last Modified:	18 Jan 2023 21:27
DOI:	10.1287/moor.2021.1159
Related URLs:	Author Publisher
URI:	https://livrepository.liverpool.ac.uk/id/eprint/3140283