On the structure of weakly acyclic games
From MaRDI portal
Publication:372989
DOI10.1007/978-3-642-16170-4_12zbMATH Open1290.91016arXiv1108.2092OpenAlexW2568233966MaRDI QIDQ372989FDOQ372989
Authors: Alex Fabrikant, Aaron D. Jaggard, Michael Schapira 
Publication date: 21 October 2013
Published in: Theory of Computing Systems, Algorithmic Game Theory (Search for Journal in Brave)
Abstract: The class of weakly acyclic games, which includes potential games and dominance-solvable games, captures many practical application domains. In a weakly acyclic game, from any starting state, there is a sequence of better-response moves that leads to a pure Nash equilibrium; informally, these are games in which natural distributed dynamics, such as better-response dynamics, cannot enter inescapable oscillations. We establish a novel link between such games and the existence of pure Nash equilibria in subgames. Specifically, we show that the existence of a unique pure Nash equilibrium in every subgame implies the weak acyclicity of a game. In contrast, the possible existence of multiple pure Nash equilibria in every subgame is insufficient for weak acyclicity in general; here, we also systematically identify the special cases (in terms of the number of players and strategies) for which this is sufficient to guarantee weak acyclicity.
Full work available at URL: https://arxiv.org/abs/1108.2092
Recommendations
Cites Work
- A class of games possessing pure-strategy Nash equilibria
- Potential games
- Dominance Solvable Voting Schemes
- The Evolution of Conventions
- Congestion games with player-specific payoff functions
- Payoff-based dynamics for multiplayer weakly acyclic games
- Improvement dynamics in games with strategic complementarities
- Weakly-Acyclic (Internet) Routing Games
- Title not available (Why is that?)
- Title not available (Why is that?)
- Learning in games by random sampling
Cited In (17)
- Pure Nash Equilibria and Best-Response Dynamics in Random Games
- Best-response dynamics in two-person random games with correlated payoffs
- On convergence rates of game theoretic reinforcement learning algorithms
- Coordination Games on Weighted Directed Graphs
- Iterative voting and acyclic games
- Unilaterally competitive games with more than two players
- Weakly-Acyclic (Internet) Routing Games
- When ``better is better than ``best
- Strong and Weak Acyclicity in Iterative Voting
- Highway games on weakly cyclic graphs
- On the weak distributivity game
- Weakly-acyclic (internet) routing games
- Setting Cournot Versus Lyapunov Games Stability Conditions and Equilibrium Point Properties
- A classification of weakly acyclic games
- A classification of weakly acyclic games
- On the structure of weakly acyclic games
- Best-response dynamics, playing sequences, and convergence to equilibrium in random games
This page was built for publication: On the structure of weakly acyclic games
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q372989)
