Coordination Games on Graphs

Authors
Publication date 2014
Host editors
  • T.-Y. Liu
  • Q. Qi
  • Y. Ye
Book title Web and Internet Economics
Book subtitle 10th International Conference, WINE 2014, Beijing, China, December 14-17, 2014: proceedings
ISBN
  • 9783319131283
ISBN (electronic)
  • 9783319131290
Series Lecture Notes in Computer Science
Event Web and internet economics: 10th International Conference, WINE 2014
Pages (from-to) 441-446
Publisher Cham: Springer
Organisations
  • Interfacultary Research - Institute for Logic, Language and Computation (ILLC)
Abstract 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 graphs 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.
Document type Conference contribution
Note Extended abstract
Language English
Published at https://doi.org/10.1007/978-3-319-13129-0_37
Permalink to this page
Back