Coordination games on graphs

Krzysztof R. Apt, Bart Keijzer, Mona Rahn, Guido Schäfer and Sunil Simon ()
Additional contact information
Krzysztof R. Apt: Centrum Wiskunde & Informatica (CWI), Networks and Optimization Group
Bart Keijzer: Centrum Wiskunde & Informatica (CWI), Networks and Optimization Group
Mona Rahn: Centrum Wiskunde & Informatica (CWI), Networks and Optimization Group
Guido Schäfer: Centrum Wiskunde & Informatica (CWI), Networks and Optimization Group
Sunil Simon: IIT Kanpur

International Journal of Game Theory, 2017, vol. 46, issue 3, No 11, 877 pages

Abstract: 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$$ 2 ( n - 1 ) / ( k - 1 ) - 1 and $$2(n-1)/(k-1)$$ 2 ( n - 1 ) / ( k - 1 ) . The latter upper bound is tight for $$k=n$$ 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; Strong equilibria; Price of anarchy; Price of stability (search for similar items in EconPapers)
Date: 2017
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (2)

Downloads: (external link)
http://link.springer.com/10.1007/s00182-016-0560-8 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:jogath:v:46:y:2017:i:3:d:10.1007_s00182-016-0560-8

Ordering information: This journal article can be ordered from
http://www.springer. ... eory/journal/182/PS2

DOI: 10.1007/s00182-016-0560-8

Access Statistics for this article

International Journal of Game Theory is currently edited by Shmuel Zamir, Vijay Krishna and Bernhard von Stengel

More articles in International Journal of Game Theory from Springer, Game Theory Society
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().