Venue: ICLR 2022 Conference

Reviews:

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: This work considers two-team zero-sum games where two teams with opposite objectives are facing each other. While the literature is quite extensive on learning in zero-sum games, very little is known for two-team zero sum-games. This paper first shows that this problem is much harder than classical zero-sum games by showing that the computation of a NE is CLS hard. Besides showing the failure of classical optimization methods for zero-sum games, the authors propose an optimisation algorithm better suited to this setting, which converges locally to a NE for carefully tuned hyperparameters.
main_review: I have read the authors answer' and the other reviews. I am satisfied with their answers and do not have any concern other than the lack of clarity at some points. I am thus still in favour of its acceptance.
-----------------------------------------
I globally find this work very interesting, well writtend and I think the problem of two-team zero-sum games deserves careful considerations. My main concern is about the comparison with related work, which seems weird/incomplete. When reading the related paper from Daskalakis and Panageas for example, they already claim that GDA and OGDA may not converge to NE in zero sum-games (in last iterate). A main part of this work is a similar claim in two-team zero-sum games (Thm 3.5), but it trivially holds if it is already the case in classical zero-sum games. As a consequence, I think the better should better focus on comparing to average iterates of these algorithms, that are known to converge to equilibria, or to methods that are known to converge in last iterate, such as OMWU for example. The case of average iterates is only mentioned in Figure 4 and Remark 3.6, but having a longer discussion (+ a theoretical result) on this would be great in my opinion. For example, Figure 2 makes less sense as soon as we are considering average iterates.

The other main "weakness" of this paper is the fact that Theorem 3.7 only holds under specific choices of the matrices K and P, that depend on the problem parameters. This is mentioned by the authors in the conclusion, and I agree with them that this can be left as future work.

Minor comments:
- p.2: "is computationally harder of finding pure NE in a congestion game". Isn't it a typo? "than" instead of "of"?
- typos:
           p.3 "introduces" -> "introduced"
                 "their" -> "they are"
           p.5 "captures" -> "capture"
           p.6 "non-trivial", don't you mean "trivial"?
           p.9: "small number of neurons achieves to", the end of the sentence is missing

- could you please explain the meaning of equation (2.4) with words?
- the figures are lacking legends and are thus hard to interpret for some of them
- Theorem 3.1: I think it would be nice to define CLS hard before
- Theorem 3.7: what is exactly $\nabla_{x,x}$?
summary_of_the_review: This paper is overall interesting and significant for the problem of two team zero sum games. My main concern is how it relates to previous works and I hope the authors could clarify this point.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: The main contributions of the paper are as follows. First, the authors show show that the computation of Nash equilibrium in two-team zero-sum game is CLS-hard. As a result, GDA and its variants (including optimistic GDA and extragradient) cannot---in general---be used to converge to the Nash equilibrium. Then, the authors propose a "stabilized" version of GDA (called KPV-GDA) obtained through certain stabilization techniques in control theory. 
main_review: Overall, I am a bit conflicted for this paper. I appreciate the CLS-hardness result, and like the idea of using control theory to stabilize the dynamics of GDA. At the same time, I think the paper is lacking in many aspects:

#1. First of all, I was surprised to see no mention of the dichotomy between team maxmin equilibrium [3] (which to my understanding is what the authors are focusing on), versus its convexification TMECor [1][2] until the appendix. TMECor allows for correlated strategies to be used within the team. As independent strategies are a special case of correlated strategies, TMECor always allows for higher social welfare compared to TME against the same opponent. Also, the use of correlation is not an obstacle, as long as the team members can agree on a common shared signal to use to seed the same random number generator (for example, the team member having access to the current time would often be good enough).

But above all, beyond higher welfare and limited additional assumptions, TMECor is a convex concave problem. So, I think that TME makes for a pretty non compelling solution concept compared to TMECor. Showing hardness of TME is definitely interesting, but I believe that a robust discussion about TMECor and its benefits should be present in the paper. Realistically, it's hard for me to imagine a practical case where I'd rather use TME than TMECor.

#2. The paper is a bit hard to read. I've numbered here a few questions that would help clarify a few of the obscure points in the rebuttal:

a) It was not immediately clear to me what "converge *locally* to a point" means

b) Is KPV-GDA defined in the introduction the same as GDA-KPV mentioned in Theorem 3.7?

c) In the conclusions you mention that your stabilized algorithm "manages to stabilize *around* Nash equilibria". What does around mean here? In Theorem 3.7 you talk about "local convergence" to a Nash equilibrium. So, it that the same thing?

d) What can be said about the matrices K and P in Theorem 3.7? Does it mean that the theorem is purely an existential result? Or is there an algorithm to compute the required matrices?

#3. I think the paper would benefit from polishing the language. That goes beyond typos: I think the overall language of the paper needs to be made more precise, as it often came off to me as vague and handwavy. For example, beyond all examples mentioned above in point 2.:
- In the abstract, you write "We present a family of team games whose induced utility is non-multilinear with non-attracting per-se mixed Nash equilibria". What does "per-se" bind to here? The term is only used once, and it was not clear to me if it was a technical term I was not familiar with (a "per-se Nash equilibrium"), or if it instead referred to "per-se not-attracting", which again was not clear. Is the point attracting, or not attracting, or something else that needs to be explained? Also, if "per-se" referred to the Latin expression, I believe it does not need a hyphen.
- In the abstract again, you write ".. is not possible using .. (GDA), its optimistic variant and extra gradient". I think it would have been clearer to say "its extragradient variant".
- The paper is inconsistent between "two-player zero-sum" and "two player zero-sum".
- In the introduction, you talk about a certain min-max approach missing "the critical component of the collective strategy making". What is the critical component? I wish you had been way more specific.
- Introduction: "computing local Nash Equilibrium .. are" -> is
- Introduction: "is computationally harder of finding" -> than
- Introduction: "From optimization perspective" -> "From an"
- I encourage the authors to improve the figures, which are hard to read due to the fonts (very low contrast, the text looks pale instead of black) and font sizes used.
- Section 3.4: "our machiner" -> "machinery"
- Experiments: "Iter 3000" refers to data generated by 3000 episodes worth of training? It would be great to dive a more complete description as to how the experiments were run in the Experimental section of the paper.


[1] Basilico et al. "Team–Maxmin Equilibrium: Efficiency Bounds and Algorithms"

[2] Celli & Gatti "Computational Results for Extensive-Form Adversarial Team Games". 

[3] von Stengel & Koller "Team maxmin equilibria".
summary_of_the_review: I appreciated the theoretical results of the paper, though I believe more needs to be done to justify the model. I also think the writing could be significantly improved. Overall, I am somewhat on the fence. I welcome a thorough discussion with the authors.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: This paper studies the equilibrium compution in two-team zero-sum games. Finding the per player Nash is proved to be CLS-hard, and many popular gradient-based algorithms are proved to be not stable. A vaned gradient descent ascent algorithm is proposed to address the instability, shown to locally converge.
main_review: Strengths:
1. The setting of two-team games is important, even the zero-sum version has many applications.
2. The techniques used in the paper are well-motivated and, as far as I checked, are correct.

Weaknesses:
1. The detailed proofs are relatively simple. Although not trivial, most conclusions are not suprising. The reduction for CLS-hardness is somewhat straightforward. The locally convergence of the proposed KPV-GDA is proved by showing the existance of suitable K and P but no construction is provided.
2. There are several issues related to the presentation. The general organization is fine but there are many typos and misused capital chatractors. The most important one is the ambiguity in Section 4 (last two sentences). Basically, I cannot understand the settings and the results provided in the experiments, although this does not influence the theoretical parts.
3. One minor concern about the illustraive exmample on multi-agent GANs: The Nash equilibrium in this paper is defined in the sense of per player, i.e. each individual player cannot improve itself by unilaterally changing its strategy. However, it seems MGANs should in fact care about the equilibrium where each team cannot improve itself by unilaterally changing all its team members' strategies (still restricted in the space of Cartesian product of simplices). The later, just called per team NE as I have not the official name, is defined similarly as the team max-min equilibrium except both teams can have multiple players. Each per team NE, although not necessarily exists, must be a per player NE, but not vise versa.
summary_of_the_review: I think this paper is blow the bar of acceptance. Currently I am negative on it due the weaknesses I mentioned, but may change to be positive if those issues can be addressed.
review_title: null

final_score: rating: 3: reject, not good enough
review_content: summary_of_the_paper: This paper shows that finding a Nash equilibrium in team zero-sum games is CLS-hard (i.e., it is unlikely to have a polynomial-time algorithm for computing a Nash equilibrium).  They show that the commonly used gradient-based methods cannot converge to a Nash equilibrium and then propose a gradient-based method with special conditions, which manages to stabilize around Nash equilibria.
main_review: The claims in this paper are supported by theoretical and experimental results.

However, my concerns are:

The solution concept for the studied two-team zero-sum game is Nash equilibrium, and this two-team zero-sum game is an N-player game. It is well-known that computing a Nash equilibrium in N-player games is PPAD-complete (Daskalakis et al., 2009) (i.e.., it is unlikely to have a polynomial-time algorithm for computing a Nash equilibrium), and this paper shows that finding a Nash equilibrium in two-team zero-sum games is CLS-hard (i.e., it is unlikely to have a polynomial-time algorithm for computing a Nash equilibrium). 

Gradient-based algorithms have been used to compute a Nash equilibrium in N-player games (Mckelvey, 1988; Mckelvey et al., 2014; Gemp et al., 2021), which cannot guarantee the convergence in general but will converge to a Nash equilibrium with special settings. That is the similar result presented in this paper.

Therefore, this paper cannot make us understand two-team zero-sum games better.


 
McKelvey, R.D., 1998. A Liapunov function for Nash equilibria.\
McKelvey, Richard D., McLennan, Andrew M., and Turocy, Theodore L. (2014). Gambit: Software Tools for Game Theory, Version 16.0.1. http://www.gambit-project.org. \
Gemp, I., Savani, R., Lanctot, M., Bachrach, Y., Anthony, T., Everett, R., Tacchetti, A., Eccles, T. and Kramár, J., 2021. Sample-based Approximation of Nash in Large Many-Player Games via Gradient Descent. arXiv preprint arXiv:2106.01285.


The presentation can be improved:
1.	It will be better to explain the given equations, e.g., the gradient formulation in Section 2. By the way, what is k+1/2 in Extra Gradient Method? 
2.	How to obtain Eq.(2.5) from Eq.(2.4)? What is \mu in Eq.(2.5)?
3.	What is “measure zero” in Theorem 3.2?
4.	The number in figures is unclear.
5.	Need to explain how the experimental results in Section 4 validate the theoretical findings (or which finding).


Minor: \
There are many grammar issues:\
In the abstract: “Moreover In ”\
In Section 1: “Firstly, computing local Nash Equilibria (NE) in general non-convex non-concave games **are** PPAD-complete”, "MD-GAN (Hardy et al., 2019) **are**"\
In Section 3.2: “we prove an important **Theorem** ”\
In Section 3.3: “**course**-correlated equilibria (CCE)”\
In Section 4: “On the other hand our architecture with a small number of neurons achieves to **We 
defer an execution** of multi-generators multi-discriminators architectures for CIFAR-10 **again to** the 
paper’s supplement. ”

About the related work on TME, the following two latest papers should be discussed:\
Zhang, Y., An, B. and Černý, J., 2021, May. Computing Ex Ante Coordinated Team-Maxmin Equilibria in Zero-Sum Multiplayer Extensive-Form Games. In Proceedings of the AAAI Conference on Artificial Intelligence (Vol. 35, No. 6, pp. 5813-5821).\
Farina, G., Celli, A., Gatti, N. and Sandholm, T., 2021, July. Connecting Optimal Ex-Ante Collusion in Teams to Extensive-Form Correlation: Faster Algorithms and Positive Complexity Results. In International Conference on Machine Learning (pp. 3164-3173). PMLR.

summary_of_the_review: This paper cannot make us understand two-team zero-sum games better.

***After the discussion:***
It seems that the authors have misunderstood the relation between different solution concepts.

The statement “the notion of"per player Nash equilibria" can be seen as a smoother figure of merit for the performance of a defensive team against an adversary” is not correct because a per-player Nash equilibrium may not be a team maxmin equilibrium (TME). Similar to TME, a two-team maximin equilibrium is still a per-player Nash equilibrium, but a per-player Nash equilibrium may not be a two-team maximin equilibrium. This paper focuses on min-max optimization in team zero-sum games, but it only achieves a per-player Nash equilibrium. I think this is inappropriate.
review_title: null

Meta-review: In this paper, the authors study "team-zero sum games", where two teams are facing each other with opposite objective. 

The main result is that the complexity of finding equilibrium is CLS, hence probably not polynomial. This result is obtained via a reduction to some congestion games.

Three reviewers gave a mild positive score (6) while the fourth one had more concerns. I tend to agree with the first three reviewers, with a  a personal opinion around 5-6. The paper is interesting, but could benefit from polishing here and there (I acknowledge that the related work section is more precise after discussion). 

This said, I also kind of agree with the last reviewer in the sense that the result of this paper is a bit narrow (also not really surprising, but we cannot always have breathtaking results), and I am also not sure that most of the ICLR community will be interested by this kind of result. This is not really a criticism, but this paper is really borderline, and this is what makes it fall into the rejection pile.

For instance, I think this paper would be more suited to some other conferences, more concerned about games and computations for instance (or even a journal).
Decision: Reject