We introduce natural strategic games on graphs, which capture the idea of coordination in a local setting.We show that these games have an exact potential and have strong equilibria when the graph is a pseudoforest. We also exhibit some other classes of games for which a strong equilibrium exists. However, in general strong equilibria do not need to exist. Further, we study the (strong) price of stability and anarchy. Finally, we consider the problems of computing strong equilibria and of determining whether a joint strategy is a strong equilibrium.
Coordination, Graphs, Strong equilibria, Strong price of anarchy, Strong price of stability, Computation of equilibria
Logistics (theme 3)
Lecture Notes in Computer Science
Conference on Web and Internet Economics
This work was funded by the The Netherlands Organisation for Scientific Research (NWO); grant id nwo/612.001.209 - Societal Impact Games

Apt, K.R, Rahn, M.M, Schäfer, G, & Simon, S.E. (2014). Coordination Games on Graphs. In LNCS (pp. 441–446). Springer.