On the structure of weakly acyclic games
Venue
Theory of Computing Systems, vol. 53 (2013), pp. 107-122
Publication Year
2013
Authors
Alex Fabrikant, Aaron D Jaggard, Michael Schapira
BibTeX
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.
