Coordination Games on Graphs
Presented at the Conference on Web and Internet Economics, Beijing
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.