Coordination games on graphs

Krzysztof R. Apt, Bart de Keijzer, Mona Rahn, Guido Schäfer, Sunil Simon*

*Corresponding author for this work

    Research output: Contribution to JournalArticleAcademicpeer-review

    Abstract

    We introduce natural strategic games on graphs, which capture the idea of coordination in a local setting. We study the existence of equilibria that are resilient to coalitional deviations of unbounded and bounded size (i.e., strong equilibria and k-equilibria respectively). We show that pure Nash equilibria and 2-equilibria exist, and give an example in which no 3-equilibrium exists. Moreover, we prove that strong equilibria exist for various special cases. We also study the price of anarchy (PoA) and price of stability (PoS) for these solution concepts. We show that the PoS for strong equilibria is 1 in almost all of the special cases for which we have proven strong equilibria to exist. The PoA for pure Nash equilbria turns out to be unbounded, even when we fix the graph on which the coordination game is to be played. For the PoA for k-equilibria, we show that the price of anarchy is between 2 (n- 1) / (k- 1) - 1 and 2 (n- 1) / (k- 1). The latter upper bound is tight for k= n (i.e., strong equilibria). Finally, we consider the problems of computing strong equilibria and of determining whether a joint strategy is a k-equilibrium or strong equilibrium. We prove that, given a coordination game, a joint strategy s, and a number k as input, it is co-NP complete to determine whether s is a k-equilibrium. On the positive side, we give polynomial time algorithms to compute strong equilibria for various special cases.

    Original languageEnglish
    Pages (from-to)851-877
    Number of pages27
    JournalInternational Journal of Game Theory
    Volume46
    Issue number3
    DOIs
    Publication statusPublished - 1 Aug 2017

    Funding

    The fact that for the case of a ring the coordination game has the c-FIP was first observed by Dariusz Leniowski. We thank José Correa for allowing us to use his lower bound in Theorem . It improves on our original one by a factor of 2. We thank the anonymous reviewers for their valuable comments. The first author is also a Visiting Professor at the University of Warsaw. He was partially supported by the NCN Grant No. 2014/13/B/ST6/01807.

    FundersFunder number
    Narodowe Centrum Nauki2014/13/B/ST6/01807

      Keywords

      • Coordination games
      • Graphs
      • Nash equilibria
      • Price of anarchy
      • Price of stability
      • Strong equilibria

      Fingerprint

      Dive into the research topics of 'Coordination games on graphs'. Together they form a unique fingerprint.

      Cite this