Venue: ICLR 2023 Conference

Reviews:

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: This paper studies the computation of Nash Equilibrium for two-team zero-sum games, and

1. proves that computing an approximate (possibly mixed) NE in two-team zero-sum games is CLS-hard.

2. gives a simple family of two-team zero-sum games where some common online, first-order min-max optimization methods (GDA, OGDA, OMWU, EG) fail to converge to NE (regardless of convergence time) except for a measure zero set of initial conditions.

3. gives a new first-order method (KPV-GDA) to stabilize the dynamics around unstable Nash Equilibria in certain class of well-behaved games and converge to them.

4. argues that the study of two-team zero-sum games applies to multi-agent GANs, which performs better than a single-agent GAN on learning a mixture of 8 Gaussians in an experiment.
strength_and_weaknesses: What I like:
* The reduction to show CLS-hardness is very simple.
* The counter example (Generalized Matching Pennies) showing non-convergence is very simple and intuitive.
* The motivation for the new first-order method (KPV_GDA) to stabilize Nash Equilibria in certain general class of well-behaved games is also intuitive.

What might be improved:
* The argument connecting (the results in this paper concerning) two-team zero-sum games with (the real world performance of) multi-agent GANs, while interesting, may need stronger evidence.
clarity,_quality,_novelty_and_reproducibility: The introduction is well written, covering an extensive literature on game theory (different solution concepts and how they compare, importance of Nash Equilibrium in applications such as security, networks, and evolution). The technical exposition is also well written, if somewhat a bit too brief.

All theoretical results are new, and some of them require simple, but slightly new perspectives.

The simple experiments are described in enough details to reproduce.
summary_of_the_review: The paper contributes to the study of two-team zero-sum games, and this reader recommends acceptance.
review_title: null

final_score: rating: 3: reject, not good enough
review_content: summary_of_the_paper: This paper studies two-team zero-sum multiplayer games, where there are two teams of players, and team members in each team share the same payoff function. This paper focuses on computing a Nash equilibrium in these games, and they show that finding a Nash equilibrium in these two-team zero-sum games is CLS-hard based on the result of computing a Nash equilibrium in two-team zero-sum games. The result then will follow since computing Nash equilibria in congestion games is CLS-hard (Babichenko & Rubinstein 2021). They show that, with some specific settings, some gradient-based algorithms fail to converge (even locally) to a Nash equilibrium. They then provide a new version of gradient-based algorithms, which converges locally to Nash equilibria with some assumptions.
strength_and_weaknesses: This paper shows that finding a Nash equilibrium in these two-team zero-sum games is CLS-hard and theoretically proposes a new version of gradient-based algorithms, which converges locally to Nash equilibria with some assumptions. However, many things about this algorithm are unclear: the performance relative to existing algorithms, the reason (intuition) why it converges, whether the assumption is realistic in the real world, and how it connects to GAN.
Two-team zero-sum games (Schulman & Vazirani 2019b) have been studied. This paper aims to compute a Nash in these games. Schulman & Vazirani (2019b) proposed using a multilinear program to compute a maxmin equilibrium, which is a Nash equilibrium as well. In addition, there are other algorithms for computing a Nash equilibrium in general multiplayer games [1,2], which can solve two-team zero-sum games. Particularly, the proposed algorithm in this paper is not the first gradient-based algorithm guaranteeing to converge for Nash equilibrium in two-team zero-sum games because gradient-based algorithms with theoretical guarantee in general games were proposed [2], which can solve two-team zero-sum games. It is well-known that a gradient-based algorithm cannot guarantee convergence for Nash equilibrium. For convergence, some assumptions/operations should be added to the algorithm. Then, this paper needs to show that the proposed algorithm is better than existing algorithms in terms of theoretical results and/or experimental results.
 
 
 
Section 3 studies the reason why some settings of gradient-based algorithms cannot converge in GMP. Unfortunately, they only show that their proposed algorithm KPV-GDA can converge in GMP but do not show the reason why their algorithm KPV-GDA can converge in GMP. That is, it is unclear why KP-GDA converges in GMP. Understanding the reason why the proposed algorithm KPV-GDA converges in MPG is also important. 
 
 
Theorems 3.4 and 3.5 are the main results of this paper about the convergence of the proposed algorithm. However, both theorems assume that the matrix of Jacobian related to the Nash equilibrium is invertible. It is unclear if this assumption is realistic. Particularly, it is not easy for us to know the property of a Nash equilibrium before we can obtain it. That is, before we obtain a Nash equilibrium by using the proposed algorithm, we usually do not know its property. Then this requirement seems unrealistic.
 
In section 2.1 and Section 4, this paper uses GAN to motivate the study of two-team zero-sum games. However, it is unclear how to model that GAN by using the proposed two-team game. For example, it is unclear what a pure strategy in a Team-WGAN is, and it is unclear what the utility function in a Team-WGAN. I believe continuous games of GAN and discrete games of two-team games have different properties.
 

 


[1] Berg, K. and Sandholm, T., 2017, February. Exclusion method for finding Nash equilibrium in multiplayer games. In AAAI.

[2] Gemp, I., Savani, R., Lanctot, M., Bachrach, Y., Anthony, T., Everett, R., Tacchetti, A., Eccles, T. and Kramár, J., 2022. Sample-based Approximation of Nash in Large Many-Player Games via Gradient Descent.  In AAMAS

Minor:

‘lFurthermore’ -> Furthermore

‘a NE’ -> an NE

clarity,_quality,_novelty_and_reproducibility: The above.
summary_of_the_review: This paper shows that finding a Nash equilibrium in these two-team zero-sum games is CLS-hard and theoretically proposes a new version of gradient-based algorithms, which converges locally to Nash equilibria with some assumptions. However, many things about this algorithm are unclear: the performance relative to existing algorithms, the reason (intuition) why it converges, whether the assumption is realistic in the real world, and how it connects to GAN.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: The authors investigate the problem of computing Nash equilibrium in (normal-form) two-team zero-sum games. The authors argue that the problem is CLS-hard, and give an algorithm guaranteeing local convergence. 
strength_and_weaknesses: The premise of the paper is interesting, but I have nontrivial concerns about the technical results. In particular:

1. The CLS-hardness proof seems problematic. The game used in the reduction has $|S_i|$ actions for each of $n$ players, so the normal form of the game has representation size $n \cdot \prod_{i} |S_i|$, which could be exponential in the representation size of the congestion game instance. (Indeed, if we allowed ourselves an algorithm with that runtime, congestion games would become trivial, since one could directly compute the minimizer $\boldsymbol s \in \bigtimes_i S_i$ of the potential!) If the goal is to show that Nash computation is hard for zero-sum team games in some *succinct* game representation, the authors should formally specify exactly what that succinct representation is and why it is interesting. This is my main concern about the paper.

1. I am also unconvinced regarding the solution concept. In particular, in the GAN example (Sec 2.1.1) that seems like a fundamental motivating example in this paper, it seems that the correct solution concept should be TME. The natural goal is to find $G_p$ and $G_\theta$ maximizing the discriminator loss, which is exactly what TME does. Also recall that the gap in solution between an arbitrary Nash and a TME can be arbitrarily bad in general. Especially given that the game is already highly nonconvex-nonconcave, I do not see the benefit of using Nash instead of TME here.

Minor things not affecting my evaluation:

1. The probability expressions after Eq (1) are wrong, since $\zeta$ is a normal variable and therefore $\zeta+p$ may not be in $[0, 1]$.

1. Section 3.2: "[Theorem 3.1] does not preclude the prospect of attaining algorithms (learning first-order methods) that converge to Nash equilibria." I understand that this because you draw the distinction between $\text{poly}(1/\epsilon)$ convergence to $\epsilon$-Nash (which at this point in the paper could still be achieved learning methods) and $\log(1/\epsilon)$ convergence (which would be achieved by an exact method), correct? I think this is worth making explicit, and stating in any hardness result that you are showing hardness for the $\log(1/\epsilon)$ version of convergence.
clarity,_quality,_novelty_and_reproducibility: The paper is clearly written and addresses a problem previously unsolved in the literature. 
summary_of_the_review: The paper presents new and interesting results on a problem of obvious interest. I have one major concern regarding the technical part of the paper. If it is addressed, I will raise my score.
review_title: null

Meta-review: metareview:_summary,_strengths_and_weaknesses: (a) Summary: This paper proves that finding Nash equilibrium in two-team zero-sum games is CLS-hard in general, exhibits a class of simple games for which common online algorithms fail to converge, and proposes an algorithm that does converge to a Nash equilibrium under certain assumptions.  A connection to training GANs is proposed.

(b) Strengths:  One reviewer found the three main results (CLS-hardness proof, demonstration of non-convergence, and demonstration of a well-behaved class of games) clearly expressed.  The other positive reviewer was eventually satisfied on these points after an detailed conversation with the authors.

(c) Weaknesses:  All reviewers found the motivating connection to training GANs rather unconvincing.  One reviewer felt strongly that non-online benchmarks ought to have been included.
justification_for_why_not_higher_score: I have the sense from all of the reviewers that the motivation behind this work needs to be clearer.
justification_for_why_not_lower_score: The technical content seems solid, especially after a productive exchange with one reviewer.  The negative reviewer's concerns primarily revolve around the need to compare to batch benchmarks, but I agree with reviewer m964 that this is not necessary in a paper that aims to demonstrate feasibility for an online algorithm.
Decision: Accept: poster