On the Structure of Weakly Acyclic Games

Details On the Structure of Weakly Acyclic Games On the Structure of Weakly Acyclic Games

2011-08-10

arxiv.org/abs/1108.2092v1

Computer Science

Computer Science and Game Theory

17 pages. Revised and expanded version of a paper that appeared in the Proceedings of SAGT 2010

Scientific paper

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.

Affiliated with

Also associated with

No associations

Rating

On the Structure of Weakly Acyclic Games does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with On the Structure of Weakly Acyclic Games, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and On the Structure of Weakly Acyclic Games will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-664489