On the Structure of Weakly-Acyclic Games

Full textClick to download.
CitationSAGT 2010
AuthorsAlex Fabraikant
Aaron D. Jaggard
Michael Schapira


The class of weakly acyclic games, which includes potential games and dominance-solvable games, captures many practical application domains. Informally, a weakly acyclic game is one where 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. Speci cally, 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 insfficient for weak acyclicity.

Back to publications
Back to previous page