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.
Additional Metadata
Keywords Coordination, Graphs, Strong equilibria, Strong price of anarchy, Strong price of stability, Computation of equilibria
THEME Logistics (theme 3)
Publisher Springer
Series Lecture Notes in Computer Science
Conference Conference on Web and Internet Economics
Grant This work was funded by the The Netherlands Organisation for Scientific Research (NWO); grant id nwo/612.001.209 - Societal Impact Games
Citation
Apt, K.R, Rahn, M.M, Schäfer, G, & Simon, S.E. (2014). Coordination Games on Graphs. In LNCS (pp. 441–446). Springer.