Coordination games on graphs

DOI10.1007/S00182-016-0560-8MaRDI QIDQ1677255zbMATH OpenOpenAlexFDO

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

Publication date 10 November 2017

Published in International Journal of Game Theory (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1501.07388, https://ir.cwi.nl/pub/25049

zbMATH Keywords

coordination gamesgraphsNash equilibriaprice of anarchyprice of stabilitystrong equilibria

Mathematics Subject Classification ID

Games on graphs (graph-theoretic aspects) (05C57) Games involving graphs (91A43)

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.

Recommendations

• Coordination games on directed graphs
• Coordination games on graphs (extended abstract)
• Coordination games on weighted directed graphs
• Graphs and Cooperation in Games
• Coordination games on dynamical networks
• scientific article; zbMATH DE number 1599890
• Games on graphs
• Publication:3486382
• Cooperative games on simplicial complexes

Cites work

• A class of games possessing pure-strategy Nash equilibria
• A Game Theoretic Approach for Efficient Graph Coloring
• A unified framework for strong price of anarchy in clustering games
• Computing desirable partitions in additively separable hedonic games
• Computing Stable Outcomes in Hedonic Games
• Congestion games with player-specific payoff functions
• Coordination games on directed graphs
• Coordination games on graphs (extended abstract)
• Core in a simple coalition formation game
• Diffusion in social networks with competing products
• Efficient equilibria in polymatrix coordination games
• Equilibria of Polymatrix Games
• Graphical congestion games
• scientific article; zbMATH DE number 3139273 (Why is no real title available?)
• scientific article; zbMATH DE number 7356860 (Why is no real title available?)
• scientific article; zbMATH DE number 3326981 (Why is no real title available?)
• On minmax theorems for multiplayer games
• Pure strategy Nash equilibrium in a group formation game with positive externalities
• Social network games
• Strategic Coloring of a Graph
• Strong equilibria in games with the lexicographical improvement property
• Strong equilibrium in congestion games
• Strong price of anarchy
• The max k-cut game and its strong equilibria
• The stability of hedonic coalition structures

Cited in

(24)

• Strong price of anarchy
• Digraph competitions and cooperative games
• On discrete preferences and coordination
• Equilibria and efficiency loss in games on networks
• Dynamic matching pennies on networks
• A note on concurrent graph sharing games
• Anti-coordination games and stable graph colorings
• Coordination games on graphs (extended abstract)
• Efficient equilibria in polymatrix coordination games
• Invitation games and the price of stability
• scientific article; zbMATH DE number 5823886 (Why is no real title available?)
• The max k-cut game and its strong equilibria
• Efficient Coordination in Weakest-Link Games
• Coordination games on directed graphs
• Price of anarchy for graph coloring games with concave payoff
• Reasoning about social choice and games in monadic fixed-point logic
• Coordination games on weighted directed graphs
• Two-Level Cooperative Game on Hypergraph
• The optimal way to play the most difficult repeated two-player coordination games
• Local and global price of anarchy of graphical games
• Discrete preference games with logic-based agents: formal framework, complexity, and islands of tractability
• Attaining equilibria using control sets
• On the performance of mildly greedy players in k-coloring games
• Topological price of anarchy bounds for clustering games on networks

This page was built for publication: Coordination games on graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1677255)