On the structure of weakly acyclic games (Q372989)

The paper under review is to link the class of weakly acyclic games with the existence of pure Nash equilibria in its subgames. The authors prove that the uniqueness of a pure Nash equilibrium in every subgame leads to weak acyclicity of a game, and the existence of multiple pure Nash equilibria in every subgame does not imply weak acyclicity in general. In a better-response dynamics, players take turns in an arbitrary order, with each player making a better-response to the strategies of the other players, given the current strategies of the other players. Repeat this process until no player wants to switch to a different strategy, at which point we reach a pure Nash equilibrium. Weakly acyclic games are those games in which from any starting state there exists a better-response improvement path leading from the strategies profile to a pure Nash equilibrium. In the introductory section, the authors present a motivating example on a four-nodes network, which serves as a good example for the main results of the paper. The most important result states that if every subgame of a game has a unique pure Nash equilibrium then the game is weakly acyclic. Some related works are provided. Section 2 starts with precise definitions of better-response strategies (improved path), best-response strategies (improved path), pure Nash equilibrium and weakly acyclic games among others. Theorem 1 in Section 3 gives a sufficient condition for weak acyclicity with \(n\) players, that every game that has a unique pure Nash equilibrium in every subgame is weakly acyclic under best-response. \textit{T. Yamamori} and \textit{S. Takahashi} [``The pure Nash equilibrium property and the quasi-acyclic condition'', Econ. Bull. 3, No. 22, 1--6 (2002), \url{http://www.economicsbulletin.com/2002/volume3/EB-02C70011A.pdf}] showed that subgame stability in 2-player games implies weak acyclicity even under best-response, which is not true in \(3 \times 3 \times 3\) games. Theorem 2 of the paper shows that subgame stability is not sufficient for weak acyclicity even in non-strict \(2\times 2\times 2\) games. On the other hand, Theorem 3 proves that subgame stability is sufficient for weak acyclicity in any strict \(2\times 2\times M\) or \(2\times 3\times M\) game. The proof of Theorem 3 follows, with a series of lemmas and case studies. Theorem 3 is maximal, any sizes of 3-player games admit subgame-stable examples that are not weakly acyclic in Theorem 4. Theorem 5 provides insufficiency for more players to have weakly acyclic games and completes the classification of weak acyclicity under three subgame-based properties. The authors leave an important open question on finding efficient algorithms for checking unique subgame stability. It will be also interesting to know whether such an algorithm, if it exists, is in P or NP.