Coordination Games on Graphs

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.