Coordination games on weighted directed graphs
From MaRDI portal
Publication:5085129
DOI10.1287/MOOR.2021.1159zbMATH Open1489.91051OpenAlexW3204578285MaRDI 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
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- A Game Theoretic Approach for Efficient Graph Coloring
- A class of games possessing pure-strategy Nash equilibria
- A classification of weakly acyclic games
- A classification of weakly acyclic games
- COALITION FORMATION GAMES: A SURVEY
- Computing Stable Outcomes in Hedonic Games
- Computing correlated equilibria in multi-player games
- Congestion games with player-specific payoff functions
- Convergence of Ordered Improvement Paths in Generalized Congestion Games
- Coordination games on directed graphs
- Coordination games on 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
- Equivalence of strong and coalition-proof Nash equilibria in games without spillovers
- Inapproximability of Nash equilibrium
- Iterative voting and acyclic games
- On minmax theorems for multiplayer games
- On strong NP-completeness of rational problems
- On the impact of combinatorial structure on congestion games
- Potential games
- Pure strategy Nash equilibrium in a group formation game with positive externalities
- Registration and recognition in images and videos
- Self-stabilization through the lens of game theory
- Self-stabilizing systems in spite of distributed control
- Social network games
- Strategic Coloring of a Graph
- Strong equilibria in games with the lexicographical improvement property
- Strong equilibrium in congestion games
- The Evolution of Conventions
- The complexity of pure Nash equilibria
- The max \(k\)-cut game and its strong equilibria
- The stability of hedonic coalition structures
- Weakly-Acyclic (Internet) Routing Games
- Weakly-acyclic (internet) routing games
Cited In (6)
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)
