The Cyclical Chaos And Its Equilibrium

We are delighted that the reviewer recognize the solid motivation of our paper, which is to find iterative self-play algorithms with low sample complexity. We appreciate the reviewer's acknowledgment of our rigorous result (Theorem 4.1) and the interesting experiments in two games, Connect4 and Naruto Mobile. We appreciate the reviewer's constructive feedback and we will revise our paper accordingly.

• Q1: The paper is generally not well-written. There are frequent typos, passages that seem out of place, and some definitions are not rigorous enough.
• A1: We apologize for the typos and the poor writing quality in some parts of the paper. We have proofread the paper carefully and fixed the errors. We have since revised the paper accordingly.

We agree with the reviewer that the paper should clarify the definitions of “previous strategy”.

The paper considers any finite game. The proof of Theorem 4.1 is based on Nash's Theorem 1 where any finite game exists an equilibrium point. This includes any finite class of game, nonsymmetric games included.

• Q2: The finding of Theorem 4.1 is not surprising and it seems that it is at least anecdotally known in the literature. Also, the paper seems to ignore a lot of papers on the average case performance of best response dynamics that have related results.

• A2: We agree that the idea of cycles being related to Nash equilibria is not new, but there is a difference between knowing versus being able to prove it. A proof of equivalency helps us understand what would be and would not be part of a mixed strategy Nash equilibrium support set, and how the algorithm of self-play can help us find such a set efficiently. Moreover, our theorem applies to any finite, non-cooperative game, including but not limited to n-players, non-symmetric, nondeterministic, etc. Whereas existing theoretical guarantees do not have such a strong claim and rigorous of proof.

• Q3: Some claims seem to be poorly justified. E.g., why does “This allows us to represent the learning representation of an equilibrium point in noncooperative games as a directed graph search” (see Intro) or why This aligns with Zermelo’s Theorem, providing theoretical validation. or Hence, the learning representation of a noncooperative game as a graph provides a theoretical guarantee to find a NE.

• A3: We have revised these claims and provided more explanations and references to support them. For example, we have explained that the graph representation of a game allows us to track the best response dynamics and identify cycles, which are related to Nash equilibria by our theorem. We have also explained that Zermelo’s theorem states that every finite, two-player, zero-sum game has a pure Nash equilibrium, which is consistent with our algorithm’s output in such games. We have also clarified that the graph representation does not guarantee to find a NE in general, but only in the cases where the game has a pure NE or a cyclical NE.

• Q4: Figure 2 is hard/impossible to parse due to the small font, but even then, I don’t understand what the numbers represent.

• A4: We have enlarged the font size and improved the readability of Figure 2. We have also added a caption to explain what the numbers represent.

We hope these revisions address the reviewer’s concerns and enhance the clarity of our paper.

In addition, we have made the necessary changes in our paper with red line highlighting the changes. We value the reviewer's feedback and welcome any further questions. If our answers is satisfactory, we kindly ask to consider increasing the score of our paper.

We are delighted that the reviewer find our graph search learning representation of self-play and our empirical results as the strengths of our paper. We appreciate your valuable feedback and suggestions. Here are our responses to the reviewer's questions: Q1: Can the authors provide a visual representation of the algorithm similar to what they do for self-play and PSRO?

A1: Yes, we agree that a visual representation of our algorithm would be helpful for the readers to understand the main idea and the steps involved. We have come up with an interesting visual of GraphNES yesterday. We are excited to add the figure in the revised version of the paper.

Q2: What is the criteria for selecting the environments that the authors used and why did they not use more common ones?

A2: We chose the environments that we used based on the following criteria:

They are non-cooperative games that are either known to cycle or not cycle.

The game Connect4 would be a standard game that is part of the OpenSpiel library. We specifically chose this environment because it satisfies Zermelo Theorem, where it is known that the Nash Equilibrium of the game is deterministic. From our Theorem 4.1, this would suggest there isn’t a cycle. The environment would be ideal to illustrate the training efficiency of GraphNES’s Myopic BR versus PSRO’s approach of probabilistic full computation graph.

The game of Naruto Mobile is a Street Fighter genre game. In Street Fighter, it is known that due to its 'simultaneous turn actions', the game does have a cycle of best response strategies (grab attack defense).

Evaluating on a game similar to Street Fighter make it easy to let GraphNES answer question like: If all policies discovered are part of a cycle? What would be the shape of the cycle? How does the training efficiency of GraphNES compares to Simplex-NeuPL? Many interesting questions can be explored in this setting. We agree with the reviewer that it would be interesting and useful to compare our method with other baselines on these environments as well, and we plan to do so in our future work. Q3: Can the authors provide a more representative example that helps understand what the algorithm is doing?

A3: Yes we can do that. This may take a bit more time to step by step work out examples of matrix games with vs without cycle. The reviewer may expect the matrix game more towards the end of the rebuttal period.

We have made the necessary changes (except examples of matrix games) in our paper with red line highlighting the changes. We value the reviewer's feedback and welcome any further questions. If our answers is satisfactory, we kindly ask to consider increasing the score of our paper.

We thank the reviewer for their feedback.

Q1: What is the unambiguous statement of the main theorem?

A1: The support set of a Mixed Strategy Nash Equilibrium is equivalent to a complete set of cyclical best response strategies.

The proof is based on the definition distinction of Mixed Strategy Nash Equilibrium and Pure Strategy Nash Equilibrium. The theorem applies to any finite game that satisfy this basic property (Including but not limited to n players game, imperfect information game, asymmetric game, etc).

The theorem highlights the importance of cycle detection algorithm is not just as a tool for analyzing strategic behaviors in games, but also as a method to reveal the fundamental structures that form the basis of Mixed Strategy Nash Equilibria (MSNEs).

Q2: Reading through the intro and even up to and including the main theorem statement I still do not know what the paper has actually showed.

A2: We appreciate the reviewer's feedback. We understand there are room for paper writing improvement.

The aim of the paper is to first understand why self-play algorithm may got in situation of cyclical best response. How do these cyclical best response strategies relate to a Nash Equilibrium? We rigorously established Theorem 3.1. The finding of the Theorem is the cyclical best response strategies forms a counterbalance dynamic. If we can find a complete set, the complete set is equivalent to a Mixed Strategy Nash Equilibrium.

The second part of our paper we introduce a novel way to detect cycle on a self-play computation graph - GraphNES. This is to improve the compute efficiency of the existing approach - PSRO.

We have revise the writing of the paper in the paper revision for general improvement of writing.

Q3: What are the formal definition of cyclical strategies and the complete set?

A3: The formal definition of cyclical strategies and the complete set is defined as the following (On page 4 of our paper):

$**Cyclical Set:**$ This is a collection of strategies where each strategy is a best response to the previous strategy in the set.

$**Complete Cyclical Set:**$ A cyclical set $C$ is complete if adding any other pure strategy to it does not improve the payoff of any mixed strategy with support in $C$.

Formally, if $\sigma^{id}$ is the optimal mixed strategy for player $id$ with support in $C$, and $\sigma_{'}^{id}$ is the optimal mixed strategy that includes the pure strategy of $ps^{id}$ with support in $C' = C$ $\cup$ $ps^{id}$, then $U(\sigma^{id}$, $\sigma^{-id}$) $\geq$ $U(\sigma_{'}^{id}$, $\sigma^{-id})$. Here, $\sigma^{-id}$ represents the optimal mixed strategy of the opponent.

We agree with the reviewer that the notation of \sigma^{i}{*'} is difficult to read. To address the readability, we have changed it to \sigma^{i}{\hat{*}}.

We have made the necessary changes in our paper with red line highlighting the changes. We value the reviewer's feedback and welcome any further questions. If our answers is satisfactory, we kindly ask to consider increasing the score of our paper.

We understand the reviewer's concern in regards to the paper writing. We are working on to further improve the writing of the paper.

Q1: What is the definition of cycle?

A1: The formal definition of cyclical set is defined on page 4:

Cyclical set: This is a collection of strategies where each strategy is a best response to the previous strategy in the set. For example Rock, Paper, Scissors.

Q2: Why there are two proofs under Theorem 3.1. ?

A2: Theorem 3.1. is based claiming of equivalence. This is to say our theorem needs to first proof A is B, then also proof B is also A. Using two proofs is the most common way of proving equivalence relationship.

We have made the necessary changes in our paper with red line highlighting the changes. We value the reviewer's feedback and welcome any further questions. If our answers is satisfactory, we kindly ask to consider increasing the score of our paper.

I thank the authors for their time, I have no further questions at this point. I found the paper very hard to read at the time of my review and I still do. That said, some of the explanations of Reviewer bTtB have clarified my understanding and slightly peaked my interest. I will keep my score as is for the moment but remain open to a change as the discussion continues and my understanding of the paper improves.

We have made the necessary changes in our paper with red line highlighting the changes. We value the reviewer's feedback and welcome any further questions. If our answers is satisfactory, we kindly ask to consider increasing the score of our paper.

$**Q2**$: The topic of representing Noncooperative Games as a graph and the potential for encountering a cycle on such a graph is well-documented in literature. Does Theorem 3.1 offer any new insights?

$**A1:**$ We appreciate the reviewer’s reference to the extensive literature that informs our research. Here, we will provide a breakdown of each paper and show that while the problem has been identified, existing works are not yet sufficient to solve it.

$**i.**$ We start with "Impossibility and Incompleteness in Game Dynamics" by Milionis et al., 2022. Their main result stated that: "There are games in which any continuous, or discrete time, dynamics $**fail to converge to a Nash equilibrium**$... the Nash equilibrium concept is plagued by a form of incompleteness... insufficient for describing global dynamics, e.g. $**they allow cycling**$".

This excerpt shows the phenomenon of cycle is viewed as a problem that breaks the guarantee of NE. The problem is viewed as intractable.

$**ii.**$ We discuss "No-Regret Learning and Mixed Nash Equilibria:They Do Not Mix" by Vlatakis-Gkaragkounis et al., 2020. Their main result stated that "...we show that any Nash equilibrium which is not strict (in the sense that every player has a unique best response) cannot be stable..."

This paper claims that if a player’s best response strategy is not unique, then there will be instability. However, Nash’s paper in 1951 already proved there still exist equilibrium stability even in cases where the best response strategy is not unique. This is demonstrated with Nash’s Theorem 1 proved based on Kakutani’s fixed point theorem. Kakutani’s fixed point theorem is based on set-value function, where one input can map to a set of outputs, and that the theorem is able to guarantee a fixed point. Showing even if one strategy were to have a set of best responses, there would still have a fixed point equilibrium. $**Suggesting an alternative theoretical result**$ to Vlatakis-Gkaragkounis et al.'s claim.

$**iii.**$ We move to "Cycles in adversarial regularized learning" by Mertikopoulos et al., 2018. The main result of the paper stated that "Does fast regret minimization necessarily imply (fast) equilibration in this case?... We settle these questions with a resounding 'no'... our analysis unifies and generalizes many prior results on the cycling behavior..."

This paper identified that if we only apply Myopic best response, then there exist the case of cycle. However, the authors didn’t provide an answer to how to establish a Nash Equilibrium once a cycle is encountered.

$**iv.**$ We may take a look at "The Replicator Dynamic, Chain Components and the Response Graph" by by Biggar and Shames. Both of their contributions of Theorem 4.1 (Existence of sink chain components) and their Theorem 5.2 show solid theoretical work of how finding a Nash Equilibrium can be represented as finding the sink or a complete set of strongly connected components. What is differ from their work to ours is the below:

$**Our Theorem 3.1. Contribution:**$ Our proof is based on proving the equivalency between a complete set of cyclical strategies and the support set of a MSNE. The claim of equivalency is a much stronger claim that requires a more difficult proof. The proof of equivalency allows us to claim that we have addressed $**all mixed strategy cases of NE**$ in any finite game. This gives us sufficient theoretical guarantee to then discuss if a practical algorithm would be tractable.

From this thorough review of the literature, we hope we have shown why existing literature is not yet sufficient to claim the problem of finite noncooperative game is tractable, and how our proof contributes to answering that question.

We are glad the reviewer recognizes the strength in our paper, particularly the contemporary interpretation and formalization of long-observed phenomena in game theory, the connection between cycle detection and MSNE, and the implications of our result for understanding equilibrium.

Q1: Is identifying a cycle on a graph an easy task? How do we cope with the potential exponential running time as shown in PPAD-hardness of the result?

A1: We appreciate the reviewer's question about the computational complexity of identifying a cycle on a graph. We had similar concern when we first read Daskalakis et al's End of the Line argument (PPAD hardness). The main argument of End of the Line is represent a noncooperative game as a directed graph. As such, finding a Nash Equilibrium is to find a fixed point of a graph's leave or a cycle. In the paper they argue that the termination of such a graph algorithm may be exponential if there are $2^{n}$ vertices layout that forms a single line. If we start from one end and we want to reach the other end, we may need to perform $2^{n}$ computation.

We believe the difficulty of of this problem is a misuse of $2^{n}$ vertices to analyze an algorithm's compute complexity. Traditionally, an algorithm's compute complexity is analyzed based on a "constant" size of input, and we hope to measure how efficient an algorithm is when operating on the input. For example, a sorting algorithm would have 'n' elements instead of $2^{n}$ elements. For a graph algorithm of detecting cycle, the input would be V and E, the complexity would be O(EV) if we can find similar color of vertices in O(1) time. If we were to change any existing algorithm's input to $2^{n}$, all algorithms would have exponential compute complexity.

The difficulty during our research is to convert from theory to an algorithm. How do we detect similar color of vertices when each vertex is now represented as a deep learning model? So far, we find that we cannot hope to compare the similarity of V amount of models in O(1), but we can build a vector database to compare their interaction similarity in O(log(v)). This makes the compute complexity at least tractable.

This makes the cycle detection problem more tractable than the PPAD-hardness result suggests.