Coordination Games on Weighted Directed Graphs

Krzysztof R. Apt (), Sunil Simon () and Dominik Wojtczak ()
Additional contact information
Krzysztof R. Apt: National Research Institute for Mathematics and Computer Science (CWI), 1098 XG Amsterdam, Netherlands; Faculty of Mathematics, Informatics, and Mechanics, University of Warsaw, 02-097 Warszawa, Poland
Sunil Simon: Department of Computer Science and Engineering, Indian Institute of Technology Kanpur, Kanpur 208016, India
Dominik Wojtczak: Department of Computer Science, University of Liverpool, Liverpool L69 3BX, United Kingdom

Mathematics of Operations Research, 2022, vol. 47, issue 2, 995-1025

Abstract: 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.

Keywords: Primary: 91A68; secondary: 91A10; noncooperative games; coordination games; Nash equilibrium; strong equilibrium; computational complexity (search for similar items in EconPapers)
Date: 2022
References: Add references at CitEc
Citations:

Downloads: (external link)
http://dx.doi.org/10.1287/moor.2021.1159 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:ormoor:v:47:y:2022:i:2:p:995-1025

Access Statistics for this article

More articles in Mathematics of Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().