Coordination Games on Graphs

For the past five years we have been studying a natural class of coordination games. In these games the players are nodes in a (possibly directed), each with a finite set of strategies, and the payoff of each player defined as the number of his neighbours who selected the same strategy. These games capture the idea of coordination in the absence of globally common strategies. In [1] we investigated games on undirected graphs. Such games always have (pure) Nash equilibria and the focus of this work was on identifying classes of graphs for which strong equilibria exist. More recently, see [2], we considered games on directed weighted graphs in presence of bonuses. For such graphs the payoff 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. In these games Nash equilibria do not need to exist. However, for several natural classes of graphs, including cycles, open chains of cycles, DAGs, and cliques, finite improvement or coalition-improvement paths of polynomial length always exist. As a consequence, a (pure) Nash equilibrium or a strong equilibrium in them can be found in polynomial time. The problem of determining the existence of a Nash equilibrium or of a strong equilibrium in these games is NP-complete already for unweighted graphs and no bonuses. References: [1] K.R. Apt, B. de Keijzer, M. Rahn, G. Schäfer, and S. Simon, Coordination Games on Graphs. International Journal on Game Theory 46(3), https://link.springer.com/article/10.1007%2Fs00182-016-0560-8 , pp. 851-877, 2017. [2] K. R. Apt, S. Simon, D. Wojtczak, Coordination Games on Weighted Directed Graphs. Mathematics of Operations Research, 2021. https://drive.google.com/file/d/1LRBg5bMuz4W5Ll7tjzKD3RRjx_NVyNy-/view?usp=sharing