Coordination games on graphs

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

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.

LanguageEnglish
Pages851-877
Number of pages27
JournalInternational Journal of Game Theory
Volume46
Issue number3
DOIs
Publication statusPublished - 1 Aug 2017

Fingerprint

Game
Graph in graph theory
Price of Anarchy
anarchy
Graph
Strong equilibrium
Coordination games
Solution Concepts
Price of anarchy
Nash Equilibrium
Polynomial-time Algorithm
Deviation
NP-complete problem
Upper bound
Computing

Keywords

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

Cite this

Apt, Krzysztof R. ; de Keijzer, Bart ; Rahn, Mona ; Schäfer, Guido ; Simon, Sunil. / Coordination games on graphs. In: International Journal of Game Theory. 2017 ; Vol. 46, No. 3. pp. 851-877.
@article{4e8de7a8262d4f2bb42a05c8ca8db412,
title = "Coordination games on graphs",
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.",
keywords = "Coordination games, Graphs, Nash equilibria, Price of anarchy, Price of stability, Strong equilibria",
author = "Apt, {Krzysztof R.} and {de Keijzer}, Bart and Mona Rahn and Guido Sch{\"a}fer and Sunil Simon",
year = "2017",
month = "8",
day = "1",
doi = "10.1007/s00182-016-0560-8",
language = "English",
volume = "46",
pages = "851--877",
journal = "International Journal of Game Theory",
issn = "0020-7276",
publisher = "Springer Verlag",
number = "3",

}

Apt, KR, de Keijzer, B, Rahn, M, Schäfer, G & Simon, S 2017, 'Coordination games on graphs', International Journal of Game Theory, vol. 46, no. 3, pp. 851-877. https://doi.org/10.1007/s00182-016-0560-8

Coordination games on graphs. / Apt, Krzysztof R.; de Keijzer, Bart; Rahn, Mona; Schäfer, Guido; Simon, Sunil.

In: International Journal of Game Theory, Vol. 46, No. 3, 01.08.2017, p. 851-877.

Research output: Contribution to JournalArticleAcademicpeer-review

TY - JOUR

T1 - Coordination games on graphs

AU - Apt, Krzysztof R.

AU - de Keijzer, Bart

AU - Rahn, Mona

AU - Schäfer, Guido

AU - Simon, Sunil

PY - 2017/8/1

Y1 - 2017/8/1

N2 - 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.

AB - 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.

KW - Coordination games

KW - Graphs

KW - Nash equilibria

KW - Price of anarchy

KW - Price of stability

KW - Strong equilibria

UR - http://www.scopus.com/inward/record.url?scp=84996878199&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84996878199&partnerID=8YFLogxK

U2 - 10.1007/s00182-016-0560-8

DO - 10.1007/s00182-016-0560-8

M3 - Article

VL - 46

SP - 851

EP - 877

JO - International Journal of Game Theory

T2 - International Journal of Game Theory

JF - International Journal of Game Theory

SN - 0020-7276

IS - 3

ER -