Acyclic and Weakly Acyclic Games: A Concise Review

Igal Milchtaich

Abstract

In a number of large, important families of finite games, not only is the set of pure strategy Nash equilibria nonempty but it is also reachable from any initial strategy profile by some sequence of myopic single player moves to a better or best reply strategy. This weak acyclicity property is weaker than acyclicity of the game, which requires every such sequence to reach an equilibrium. For example, all perfect information extensive form games are weakly acyclic, but they are generally not acyclic as even sequences of best improvement steps may cycle. Weak acyclicity is equivalent to acyclicity of some priority rule, which is a rule that allows only some improvement moves. It is also equivalent to the existence of a weak potential, which unlike a potential increases along some rather than every sequence as above.

Keywords

Acyclic game; Weakly acyclic games; Potential; Weak potential; Priority rules