2011/08/10 by Alex Fabrikant, Aaron D. Jaggard, Fabrikant, Alex +3
Computer Science · #Computer Science and Game Theory (cs.GT) #FOS: Computer and information sciences #cs.GT
paper · pdf · doi:10.48550/arxiv.1108.2092
17 pages. Revised and expanded version of a paper that appeared in the Proceedings of SAGT 2010
arxiv created 2011/08/10 · arxiv updated 2011/08/11
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.