Coordination games on weighted directed graphs
From MaRDI portal
Publication:5085129
DOI10.1287/MOOR.2021.1159zbMATH Open1489.91051arXiv1910.02693OpenAlexW3204578285MaRDI QIDQ5085129FDOQ5085129
Authors: Krzysztof R. Apt, Sunil Simon, Dominik Wojtczak 
Publication date: 27 June 2022
Published in: Mathematics of Operations Research (Search for Journal in Brave)
Abstract: We study strategic games on weighted directed graphs, in which the payoff of a player is defined as the sum of the weights on the edges from players who chose the same strategy, augmented by a fixed non-negative integer bonus for picking a given strategy. These games capture the idea of coordination in the absence of globally common strategies. We identify natural classes of graphs for which finite improvement or coalition-improvement paths of polynomial length always exist, and, as a consequence, a (pure) Nash equlibrium or a strong equilibrium can be found in polynomial time. The considered classes of graphs are typical in network topologies: simple cycles correspond to the token ring local area networks, while open chains of simple cycles correspond to multiple independent rings topology from the recommendation G.8032v2 on the Ethernet ring protection switching. For simple cycles these results are optimal in the sense that without the imposed conditions on the weights and bonuses a Nash equilibrium may not even exist. Finally, we prove that the problem of determining the existence of a Nash equilibrium or of a strong equilibrium in these games is NP-complete already for unweighted graphs and with no bonuses assumed. This implies that the same problems for polymatrix games are strongly NP-hard.
Full work available at URL: https://arxiv.org/abs/1910.02693
Recommendations
Noncooperative games (91A10) Games involving graphs (91A43) Algorithmic game theory and complexity (91A68)
Cites Work
- A class of games possessing pure-strategy Nash equilibria
- Potential games
- Core in a simple coalition formation game
- Self-stabilizing systems in spite of distributed control
- The stability of hedonic coalition structures
- Title not available (Why is that?)
- COALITION FORMATION GAMES: A SURVEY
- The Evolution of Conventions
- Congestion games with player-specific payoff functions
- On the impact of combinatorial structure on congestion games
- The complexity of pure Nash equilibria
- Equivalence of strong and coalition-proof Nash equilibria in games without spillovers
- Strong equilibria in games with the lexicographical improvement property
- Title not available (Why is that?)
- Computing correlated equilibria in multi-player games
- Strong equilibrium in congestion games
- Weakly-Acyclic (Internet) Routing Games
- Title not available (Why is that?)
- Title not available (Why is that?)
- On the structure of weakly acyclic games
- Pure strategy Nash equilibrium in a group formation game with positive externalities
- Computing Stable Outcomes in Hedonic Games
- Diffusion in social networks with competing products
- Coordination games on graphs
- Efficient Equilibria in Polymatrix Coordination Games
- The max \(k\)-cut game and its strong equilibria
- A Game Theoretic Approach for Efficient Graph Coloring
- Title not available (Why is that?)
- Social network games
- Registration and recognition in images and videos
- Title not available (Why is that?)
- Self-stabilization through the lens of game theory
- Iterative voting and acyclic games
- Inapproximability of Nash Equilibrium
- On strong NP-completeness of rational problems
- Coordination Games on Graphs (Extended Abstract)
- A classification of weakly acyclic games
- Weakly-acyclic (internet) routing games
- Strategic Coloring of a Graph
- A classification of weakly acyclic games
- Convergence of Ordered Improvement Paths in Generalized Congestion Games
Cited In (3)
This page was built for publication: Coordination games on weighted directed graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5085129)
