Schedulers, Potentials and Weak Potentials in Weakly Acyclic Games

In a number of large, important families of finite games, not only do pure-strategy Nash equilibria always exist but they are also reachable from any initial strategy profile by some sequence of myopic single-player moves to a better or best-response strategy. This weak acyclicity property is shared, for example, by all perfect-information extensive-form games, which are generally not acyclic since even sequences of best-improvement steps may cycle. Weak acyclicity is equivalent to the existence of a weak potential, which unlike a potential increases along some rather than every sequence as above. It is also equivalent to the existence of an acyclic scheduler, which guarantees convergence to equilibrium by disallowing certain (improvement) moves. A number of sufficient conditions for acyclicity and weak acyclicity are known.

Keywords

Weakly acyclic games; Weak potential; Scheduler