A Sufficient Condition for Weakly Acyclic games with Applications

The class of weakly acyclic games captures many practical application domains, and is particularly relevant for multi-agent distributed control problems. However, reliably checking weak acyclicity is extremely computationally intractable (PSPACE-complete) in the worst case. The present paper identifies sufficient conditions for weak acyclicity by means of the transitive closure of individual conditional preference, which can be constructed in terms of better-reply improvement paths. This pure-ordinal approach leads to a novel connection between weak acyclic games and better-reply secure games. Specifically, a better-reply secure game is weakly acyclic if the better reply dynamics does not possess a dense orbit (in addition to the quasi-concavity of individual preferences as well as the usual convexity and compactness assumptions on strategy sets). These results give a partial answer to an open problem of finding applicable and tractable conditions for weak acyclicity, posed by Fabrikant, Jaggard, and Schapira in 2013.