The Complexity of Two-Team Polymatrix Games with Independent Adversaries

## 1 Introduction

Game theory is a fundamental tool to encode strategic agent interactions and has found many applications in the modern AI landscape such as Generative Adversarial Networks [], obtaining agents with expert level play in multiplayer games such as Starcraft and Quake III [, ] and superhuman performance in poker [, ]. Computing a Nash equilibrium or a saddle point (when considering general minmax optimization problems) is a computational task of central importance in these applications. The celebrated minmax theorem of von Neumann and Morgenstern [] established that two-player zero-sum games have efficient algorithms. However, it was shown that three-player zero-sum games [] or two-player general games [] are computationally intractable (formally $\PPAD$-hard) and the hardness is also known to hold for computing approximations.

Consequently, Daskalakis and Papadimitriou [] proposed a tractable class of multiplayer zero-sum games, where the players are placed on the nodes of a graph and play a matrix zero-sum game with each adjacent player. In this setting, the total utility that a player gets is the sum of the utilities from each game that they participate in. It is to be highlighted that removing the zero-sum game assumption between each player makes the problem hard. Indeed, computing Nash equilibria in general polymatrix games is known to be $\PPAD$-hard [, , , ]. Cai and Daskalakis [] studied an intermediate setting where every edge of the polymatrix game can be either a zero-sum game or a coordination game. They showed $\PPAD$-hardness, even for the special case where the players can be grouped into *three* teams, such that players within the same team play coordination games, and players in different teams play zero-sum games. However the case of two-team polymatrix games with zero-sum and coordination edges has remained open.

#### Adversarial Two-team Games With a Single Adversary:

The general notion of adversarial *team* games introduced by Von Stengel and Koller [] studies two teams that are playing a zero-sum game with each other, meaning each team member gets the *same* payoff as the whole team and the sum of the team payoffs is zero. The primary motivation here is to study strategies for companies against adversaries. What makes the “team” aspect special is that the team members cannot coordinate their actions and must play independent mixed strategies. This captures imperfect coordination within companies. Indeed, if the teams instead had perfect coordination, then the setting would simply reduce to a two player zero-sum game. Von Stengel and Koller showed that there exists a team maxmin equilibrium, that can be extended to a Nash equilibrium for this setting when the team is playing against a *single* adversary. Moreover, they showed that this is the *best* Nash equilibrium for the team, thereby alleviating equilibrium selection issues. However, it was later shown that finding a team maxmin equilibrium is in fact $\FNP$-hard and the problem does not become easier if one allows approximate solutions [, ]. Recently, Anagnostides et al. [] studied the *single* adversary setting, and were able to show that finding a Nash equilibrium in this setting is in fact $\CLS$-complete. The $\CLS$-hardness immediately follows from the work of Babichenko and Rubinstein [], but importantly it requires a sufficiently general game structure and so does not apply to the polymatrix setting. The $\CLS$-membership on the other hand applies to any adversarial game with a single adversary. The main idea is to obtain a Nash equilibrium from an approximate stationary point of the max Moreau envelope of the function $x\mapsto\max_{y\in\mathcal{Y}}U(x,y)$ (where $x$ is the min variable, $y$ is the max variable and $U$ is the payoff function).

#### Connections to Complexity of Minmax Optimization:

Two-team games are a special case of general nonconvex-nonconcave constrained minmax problems. Daskalakis et al. [] recently studied this general setting and showed that finding a stationary point is $\PPAD$-complete. Crucially, their $\PPAD$-hardness only applies when the constraint sets are *coupled* between the min and the max player. However, games usually induce minmax problems with *uncoupled* constraints. The complexity of the problem for uncoupled constraints remains open, although it is known to be $\CLS$-hard, since it is at least as hard as finding stationary points of standard non-convex minimization problems []. As we discuss below, our results also have implications for uncoupled minmax optimization, where we obtain a $\CLS$-hardness result for a particularly simple family of objective functions. We note that Li et al. [] showed a *query* lower bound of $\Omega(\frac{1}{\varepsilon^{2}})$ for smooth nonconvex-strongly-concave minmax optimization problems, but these results do not apply to the simple objective functions that we study (and which can only be studied from the perspective of computational complexity).

#### Connections to Multiagent Learning:

From a learning dynamics perspective, qualitative results focus on understanding the limit behavior of certain no-regret learning dynamics in polymatrix games. In particular, some works focus on obtaining asymptotic convergence guarantees for Q-learning and its variants [, ]. In a similar vein, some other works studied the limit behaviors of replicator dynamics for polymatrix games, particularly with zero-sum and coordination edges [, ]. In these works, the focus was on trying to identify network topologies under which the learning dynamics exhibited simple (non-chaotic) behaviors. Surprisingly, there were works that could obtain non-asymptotic convergence guarantees using discrete time algorithms in multiagent reinforcement learning as well, with Leonardos et al. [] establishing convergence to Nash policies in Markov potential games. In adversarial settings, Daskalakis et al. [] studied independent policy gradient and proved convergence to Nash policies. Moreover, some recent works establish convergence to Nash policies in Markov zero-sum team games [] and Markov polymatrix zero-sum games []. This further establishes the need to theoretically study the computational challenges in the simplest polymatrix settings which allow for *both* zero-sum and coordination edges, in order to understand convergence guarantees in more complicated multiagent reinforcement learning scenarios. This leads us to the following main question:

*What is the complexity of finding Nash equilibria in two-team zero-sum polymatrix games?*

### 1.1 Our Contributions

Our main contribution is the following computational hardness result.

###### Theorem 1.1 (Informal) .

It is $\CLS$-hard to find an approximate Nash equilibrium of a two-team zero-sum polymatrix game, even when one of the teams does not have any internal edges.

Our result is incomparable to the $\CLS$-hardness result proved by Anagnostides et al. [] (which essentially immediately follows from the work of Babichenko and Rubinstein []). On the one hand, our result is stronger because it applies to games with a simpler structure, namely polymatrix games, whereas their result only applies to the more general class of degree-5 polytensor games. On the other hand, our result is weaker because it requires the presence of multiple adversaries, instead of just a single adversary. The case of two-team polymatrix games with a single adversary remains open. If one could prove $\CLS$-hardness for that version of the problem, then this would constitute a strengthening of both our result and the result of Anagnostides et al.

As our second contribution, we complement the hardness result in Theorem 1.1 by showing that the problem is in fact $\CLS$-complete in this particular case where the adversaries are independent (i.e., when there are no internal edges in the second team). Namely, the problem of finding an approximate Nash equilibrium in a two-team zero-sum polymatrix game with multiple independent adversaries lies in the class $\CLS$. The polymatrix setting allows us to provide a simple proof of this fact, in particular avoiding the use of more advanced machinery, such as the Moreau envelope used in the \CLS-membership of Anagnostides et al. []. We note that if the adversaries are not independent, then the problem is only known to lie in $\PPAD$, and it remains an important open problem to determine whether it also lies in $\CLS$ or is in fact $\PPAD$-complete.

Going back to our main result, Theorem 1.1, we note that it also has some interesting consequences for minmax optimization in general. Namely, we obtain that computing a stationary point, i.e., a Karush-Kuhn-Tucker (KKT) point of

$$ $\min_{x\in[0,1]^{n}}\max_{y\in[0,1]^{m}}f(x,y)$ $$

is $\CLS$-hard, and thus intractable in the worst case, even when $f$ is a bilinear polynomial(^1^11Previous $\CLS$-hardness results required more general objective functions, namely $f$ had to be a quadratic (non-bilinear) polynomial [].) that is concave in $y$. This is somewhat surprising, as these objective functions are the simplest case beyond the well-known tractable setting of convex-concave.

###### Theorem 1.1 (Informal) .

#### The meaning of \CLS \CLS \CLS -hardness.

The complexity class $\CLS$ was introduced by Daskalakis and Papadimitriou [] to capture the complexity of problems that are guaranteed to have a solution both by a fixed point argument and a local search argument. This class is a subset of two well-known classes: $\PPAD$ and $\PLS$. While $\PPAD$ is mainly known for capturing the complexity of computing Nash equilibria in general games [, ], $\PLS$ captures the complexity of various hard local search problems, such as finding a locally maximal cut in a graph []. Recently, following the result by Fearnley et al. [] that $\CLS=\PPAD\cap\PLS$, it has been shown that the class captures the complexity of computing mixed Nash equilibria in congestion games [], and KKT points of quadratic polynomials []. See Figure 1 for an illustration of the relationship between the classes.

A $\CLS$-hardness result indicates that the problem is very unlikely to admit a polynomial-time algorithm. To be more precise, our results indicate that we should not expect an algorithm to exist which can find an $\varepsilon$-approximate Nash equilibrium in these two-team polymatrix games in time polynomial in $\log(1/\varepsilon)$. Similarly, for the minmax problem with bilinear polynomial objective functions, we should not expect an algorithm that finds an $\varepsilon$-KKT point in time polynomial in $\log(1/\varepsilon)$. The evidence that $\CLS$ is a hard class is supported by various cryptographic lower bounds, which apply to both $\PPAD$ and $\CLS$ [, , ].

Figure: Figure 1: Classes of total search problems. Arrows are used to denote containment. For example, $\CLS$ is contained in $\PLS$ and in $\PPAD$. The class $\TFNP$ contains all total search problems, i.e., problems which are guaranteed to have efficiently checkable solutions. $\P$ contains all such problems solvable in polynomial time.

### 1.2 Other Related Work

It is worth mentioning that the computation of team maxmin equilibria for the two-team adversarial game has been studied where the team members are allowed to coordinate *ex ante*, which is different from what a polymatrix coordination game would induce, as we study in this paper. There it was shown that the game can be reduced to a two-player game with imperfect-recall [, , ] and that efficient algorithms exist under some assumptions about the players’ information sets []. Finally, similar notions have been studied for extensive-form games too [].

## 2 Preliminaries

### 2.1 Polymatrix games

A polymatrix game [] is a type of multiplayer game in which the payoff function can be succinctly represented. More precisely, there is a set of players $\mathcal{N}$ and a set of pure strategies $S_{i}$ for each player $i\in\mathcal{N}$. Moreover, players are represented by the vertices of an undirected graph $G=(\mathcal{N},E)$ with the intent that a matrix game is played between each pair of players $\{i,\,j\}\in E$; the pair of payoff matrices being denoted by $A^{i,j}\in\mathbb{R}^{S_{i}\times S_{j}}$ and $A^{j,i}\in\mathbb{R}^{S_{j}\times S_{i}}$. Players are allowed to randomize over their pure strategies and play a mixed strategy in the probability simplex of their action, which we denote by $\Delta(S_{i})$ for player $i$. Hence, a mixed strategy profile is some $x=(x_{1},\,x_{2},\,\ldots,\,x_{|\mathcal{N}|})\in\mathcal{X}\coloneqq\times_{i
\in\mathcal{N}}\Delta(S_{i})$. We also use the standard notation $x_{-i}$ to represent the mixed strategies of all players other than $i$. In polymatrix games, the utility $U_{i}:\mathcal{X}\rightarrow\mathbb{R}$ for player $i\in\mathcal{N}$ is the sum of her payoffs, so that

$$ $U_{i}(x)=\sum_{j:\{i,j\}\in E}x_{i}A^{i,j}x_{j}$ $$

where $x_{i}$ is understood to be $x_{i}^{\top}$: we drop the transpose when it is clear from the context for ease of presentation. As a well-defined class of games, polymatrix games always admit a Nash equilibrium []. In this work, we are interested in *approximate* Nash equilibria which we define next.

###### Definition 1 .

Let $\varepsilon\geq 0$ be an approximation guarantee. The mixed strategy profile $\widetilde{x}$ is an $\varepsilon$-approximate Nash equilibrium of the polymatrix game defined above if for any $i\in\mathcal{N}$,

$$ $U_{i}(x_{i},\widetilde{x}_{-i})\leq U_{i}(\widetilde{x}_{i},\widetilde{x}_{-i} )+\varepsilon\quad\forall x_{i}\in\Delta(S_{i})$ $$

In this paper, we focus on polymatrix games with a particular structure where players are grouped into two competing teams with players within teams sharing mutual interests.

###### Definition 2 (Two-team Polymatrix Zero-Sum Game) .

A two-team polymatrix zero-sum game is a polymatrix game $\{A^{i,j}\}_{i,j\in\mathcal{N}}$ where the players can be split into two teams $X\cup Y=\mathcal{N}$ so that any game between the two teams is zero-sum and any game within a team is a coordination game. More precisely for any $i,i^{\prime}\in X$ and $j,j^{\prime}\in Y$:

$$ $A^{i,i^{\prime}}=\big{(}A^{i^{\prime},i}\big{)}^{\top}\quad A^{j,j^{\prime}}= \big{(}A^{j^{\prime},j}\big{)}^{\top}\quad A^{i,j}=-\big{(}A^{j,i}\big{)}^{\top}$ $$

If there is no coordination within team $Y$, that is $A^{j,j^{\prime}}=0^{S_{j}\times S_{j^{\prime}}}$ for every $j,j^{\prime}\in Y$, we further say that it is a two-team zero-sum game with independent adversaries.

In the restricted context of two-teams games, another useful equilibrium concept is that of *team-maxmin equilibria* []. While originally defined for a single adversary only, it is generalizable to multiple independent adversaries in such a way that any team-maxmin equilibria can be converted to a Nash-equilibrium one efficiently. Unfortunately, similarly to the single-adversary case, such equilibriums suffer from intractability issues and are $\FNP$-hard to compute [, , ].

###### Definition 1 .

###### Definition 2 (Two-team Polymatrix Zero-Sum Game) .

### 2.2 KKT Points of Constrained Optimization Problems

We now turn our attention to solution concepts for optimization problems and in particular of Karush-Kuhn-Tucker (KKT) points. We only define the required notions for the special case where each variable is constrained to be in $[0,1]$, since this will be sufficient for us. Under those *box constraints* the expression of the Lagrangian simplifies greatly and we obtain the following definition of approximate KKT point for a minimization problem.

###### Definition 3 .

Let $\varepsilon\geq 0$ be an approximation parameter, $f:\mathbb{R}^{n}\to\mathbb{R}$ a continuously differentiable function and consider the optimization problem $\min\nolimits_{x\in[0,1]^{n}}f(x)$. The point $\widetilde{x}\in[0,1]^{n}$ is an $\varepsilon$-approximate KKT point of the formulation if the gradient $g\coloneqq\nabla f(\widetilde{x})$ satisfies for each $i\in[n]$:

- 1.
If $\widetilde{x}_{i}\in(0,1)$, then $|g_{i}|\leq\varepsilon$.
- 2.
If $\widetilde{x}_{i}=0$, then $g_{i}\geq-\varepsilon$.
- 3.
If $\widetilde{x}_{i}=1$, then $g_{i}\leq\varepsilon$.

Thus, an exact ($\varepsilon=0$) KKT point can be thought of as a fixed point of the gradient descent algorithm. Using this intuition, we can extend this to minmax problems as fixed points of the gradient *descent-ascent* algorithm. See Figure 2 for the geometric intuition of minmax KKT points.

###### Definition 4 .

Let $\varepsilon\geq 0$ be an approximation parameter, $f:\mathbb{R}^{n}\times\mathbb{R}^{n}\to\mathbb{R}$ a continuously differentiable function and consider the optimization problem $\min\nolimits_{x\in[0,1]^{n}}\max\nolimits_{y\in[0,1]^{n}}f(x,y)$. Let $(\widetilde{x},\widetilde{y})\in[0,1]^{2n}$ and let $(g,q)\coloneqq\nabla f(\widetilde{x},\widetilde{y})$, where $g$ is the gradient with respect to $x$-variables and $q$ with respect to $y$-variables. Then, $(\widetilde{x},\widetilde{y})$ is an *$\varepsilon$-approximate KKT point* if for each $i\in[n]$:

- 1.
If $x_{i}\in(0,1)$, then $|g_{i}|\leq\varepsilon$.
- 2.
If $x_{i}=0$, then $g_{i}\geq-\varepsilon$.
- 3.
If $x_{i}=1$, then $g_{i}\leq\varepsilon$.
- 4.
If $y_{i}\in(0,1)$, then $|q_{i}|\leq\varepsilon$.
- 5.
If $y_{i}=0$, then $q_{i}\leq\varepsilon$.
- 6.
If $y_{i}=1$, then $q_{i}\geq-\varepsilon$.

Figure: Figure 2: The intuition behind exact ($\varepsilon=0$) KKT points for minmax problems. The formulation features a min-variable $x$, a max-variable $y$ and the bounding box constraint $(x,y)\in[0,1]^{2}$. Some feasible points together with their respective gradient $(q^{x},q^{y})$ are depicted. Green points are valid KKT points whereas red ones are not. For instance, $(x_{1},y_{1})$ is not a KKT point because $q_{1}^{y}>0$ but $y<1$. On the other hand, $(x_{2},y_{2})$ is a valid KKT point because $q^{y}_{2}=0$ and $q^{x}_{2}<0$ with $x=1$.

###### Definition 3 .

###### Definition 4 .

### 2.3 Connection between two-team games and minmax optimization

Given a two-team polymatrix zero-sum game with matrices $\{A^{i,j}\}_{i,j\in\mathcal{N}}$, we can define the following common utility function

$$ $U(x,y)=-\sum_{i,i^{\prime}\in X:i<i^{\prime}}x_{i}A^{i,i^{\prime}}x_{i^{\prime }}-\sum_{i\in X,j\in Y}x_{i}A^{i,j}y_{j}$ $$

and the corresponding game where players on the $X$-team all have the same utility function $-U$, and players on the $Y$-team all have the same utility function $U$.
It is easy to check that this new game is equivalent to the previous one, namely a strategy profile $(x,y)$ is an $\varepsilon$-Nash equilibrium in the latter game if and only if it is in the former. Now, if we consider the minmax optimization problem

$$ $\min_{x\in\mathcal{X}}\max_{y\in\mathcal{Y}}U(x,y)$ $$

it is not hard to show that its KKT points exactly correspond to the set of Nash equilibria of the game with common utility, and thus also of the original polymatrix game. This connection also extends to approximate solutions. We develop this relation in greater detail in section Section 3, where we first prove a hardness result for a minmax problem and then use the equivalence above to extend it to polymatrix games.

## 3 \CLS \CLS \CLS -hardness of Two-Team Games with Independent Adversaries

In this section, we give a proof of our main hardness result which we re-state formally next.

###### Theorem 3.1 (Precise formulation of Theorem 1.1 ) .

It is $\CLS$-hard to find an $\varepsilon$-approximate Nash equilibrium of a two-team zero-sum polymatrix game with independent adversaries where $\varepsilon$ is inverse exponential in the description of the game.

We show that this is true even when each player can only choose from two pure strategies. This lower bound result is obtained by reducing from the problem of finding some KKT point of a quadratic minimization problem. In detail, an instance of $\MinQuadKKT$ consists of a quadratic polynomial $Q:\mathbb{R}^{n}\to\mathbb{R}$ together with an approximation parameter $\varepsilon>0$. A solution to such instance is any $\varepsilon$-approximate KKT point of $\min_{x\in[0,1]^{n}}Q(x)$ (see Definition 3). $\MinQuadKKT$ is known to be $\CLS$-complete for $\varepsilon$ inverse exponential in the description of the instance []. The reduction from $\MinQuadKKT$ to two-team games is performed in two stages which we describe next.

###### Theorem 3.1 (Precise formulation of Theorem 1.1 ) .

#### Stage I.

As a first step, we show how to reduce $\MinQuadKKT$ to the intermediate problem $\MinmaxIndKKT$. An instance of $\MinmaxIndKKT$ consists of an approximation parameter $\varepsilon>0$ together with a polynomial $M:\mathbb{R}^{2n}\to\mathbb{R}$ satisfying the following three properties:

- 1.
$M$ is multilinear.
- 2.
$M$ has degree at most 2.
- 3.
$M(x,y)$ has no monomial of type $y_{i}y_{j}$ for $i,j\in[n]$.

In this section, we conveniently refer to those three conditions as the *independence* property. A solution to such an instance is any $\varepsilon$-approximate KKT point of $\min_{x\in[0,1]^{n}}\max_{y\in[0,1]^{n}}M(x,y)$ (see Definition 4). Let us highlight that this step already establishes the $\CLS$-hardness of uncoupled minmax multilinear formulations for a simple class of objectives.

#### Stage II.

We exploit the independence property of the polynomial generated by the first stage reduction to reduce it further to a two-team zero-sum polymatrix game with independent adversaries. This is achieved through generalizing the equivalence between zero-sum games for two players and some class of minmax formulations.

### 3.1 Stage I: from quadratic to multilinear

###### Lemma 3.1 .

$\MinQuadKKT$ reduces to $\MinmaxIndKKT$

By “reduces to”, we mean the usual definition of polynomial-time $\TFNP$ reduction. We begin by describing the reduction in detail, then highlight that it yields an objective with the independence property and finally prove correctness. Let $Q:[0,1]^{n}\to\mathbb{R}$ and $\varepsilon>0$ be the $\MinQuadKKT$ instance. Write the coefficients of $Q$ explicitly as follows:

$$ $Q(x)=q+\sum\nolimits_{i\in[n]}q_{i}x_{i}+\sum\nolimits_{i\neq j}q_{ij}x_{i}x_{ j}+\sum\nolimits_{i\in[n]}q_{ii}x_{i}^{2}$ $$

Let $Z\geq 1$ be an upper bound on the sum of the absolute values of all coefficients of $Q$ and note that since $Q$ is a quadratic polynomial, it holds that for every $x\in[0,1]^{n}$ and $i\in[n]$:

$$ $|Q(x)|\leq Z\quad\text{and}\quad\left\lvert\frac{\partial Q(x)}{\partial x_{i} }\right\rvert\leq 2Z$ (1) $$

Fix $T\coloneqq 10Z$ and $\eta\coloneqq 2\varepsilon^{2}/Z$. For each min-variable $x_{i}$ of the $\MinQuadKKT$ instance, we introduce two min-variables $x_{i}$ and $x_{i}^{\prime}$ and a max-variable $y_{i}$ in the $\MinmaxIndKKT$ instance. We also define the following multilinear “copy” gadget:

$$ $\textsc{copy}(x_{i},x_{i}^{\prime},y_{i})\coloneqq\Big{(}x_{i}^{\prime}-x_{i} \cdot(1-2\eta)-\eta\Big{)}\cdot(y_{i}-1/2)$ $$

The role of copy is to force $x_{i}$ to be close to $x_{i}^{\prime}$ at any KKT point, thus effectively *duplicating* $x_{i}$ into $x_{i}^{\prime}$. This allows us to remove square terms of the objective function. To make this formal, let $Q^{\prime}:[0,1]^{2n}\to\mathbb{R}$ be a copy of $Q$ where every occurrence of the form $x_{i}^{2}$ is replaced by $x_{i}x_{i}^{\prime}$:

$$ $Q^{\prime}(x,x^{\prime})\coloneqq q+\sum\nolimits_{i\in[n]}q_{i}x_{i}+\sum \nolimits_{i\neq j}q_{ij}x_{i}x_{j}+\sum\nolimits_{i\in[n]}q_{ii}x_{i}x_{i}^{\prime}$ $$

The full formulation of the $\MinmaxIndKKT$ instance is stated below. We note that the objective $M$ of the formulation indeed satisfies the independence property.(^2^22Additional dummy max-variables can be added to ensure that the number of min- and max-variables are the same.) The proof of Lemma 3.1 now follows from 3.1.

$$ $\min_{x,x^{\prime}\in[0,1]^{n}}\max_{y\in[0,1]^{n}}M(x,x^{\prime},y)\quad\text {where}\quad M(x,x^{\prime},y)\coloneqq Q^{\prime}(x,x^{\prime})+\sum_{i\in[n] }T\cdot\textsc{copy}(x_{i},x_{i}^{\prime},y_{i})$ $$

###### Claim 3.1 .

For any $\varepsilon\in(0,1/13]$, if $(x,x^{\prime},y)$ is an $(\varepsilon^{2}/Z)$-approximate KKT point of the $\MinmaxIndKKT$ instance, then $x$ is an $\varepsilon$-approximate KKT point of the $\MinQuadKKT$ instance.

The proof relies crucially on $T$ being a large constant so that the copy gadgets dominate $Q^{\prime}(x,x^{\prime})$ and the objective $M$. This forces any KKT point $(x,x^{\prime},y)$ to have $y\in(0,1)^{n}$ and ultimately $x\approx x^{\prime}$. A second step shows that $\partial Q(x)/\partial x_{i}\approx\partial M(x,x^{\prime},y)/\partial x_{i}$, which is enough to conclude that $x$ is a KKT point of the $\MinQuadKKT$ instance.

###### Proof.

Let $\delta\coloneqq\varepsilon^{2}/Z$ be the $\MinmaxIndKKT$ approximation guarantee for the remainder of this argument. As a first step, we show that $y_{i}\in(0,1)$ for each $i\in[n]$. Towards contradiction, let us first suppose that $y_{i}=0$ and observe that:

$$ $\displaystyle\frac{\partial M(x,x^{\prime},y)}{\partial x_{i}}$ $\displaystyle=\frac{\partial Q^{\prime}(x,x^{\prime})}{\partial x_{i}}+T\cdot( 1-2\eta)\cdot(1/2-y_{i})$ $\displaystyle\geq\frac{\partial Q^{\prime}(x,x^{\prime})}{\partial x_{i}}+T \cdot(2/5)$ as $y_{i}=0$ and $\eta\leq 1/10$ $\displaystyle\geq-2Z+T\cdot(2/5)$ using ( 1 ) $\displaystyle>\delta$ as $T=10Z$ and $Z\geq 1$ $$

But as $(x,x^{\prime},y)$ is a $\delta$-approximate KKT point and $x_{i}$ is a min-variable, it must be that $x_{i}=0$ (see Definition 4). A similar computation shows that if $y_{i}=0$, then $x^{\prime}_{i}=1$ and so:

$$ $\frac{\partial M(x,x^{\prime},y)}{\partial y_{i}}=x_{i}^{\prime}-x_{i}\cdot(1- 2\eta)+\eta=1+\eta>\delta$ $$

Because $y_{i}$ is a max-variable and $(x,x^{\prime},y)$ a $\delta$-KKT point, it must be that $y_{i}=1$: a contradiction to the assumption that $y_{i}=0$. One can rule out the possibility of $y_{i}=1$ in a similar way and we may thus conclude that $y_{i}\in(0,1)$. This fact, together with the KKT conditions, further implies that the partial derivative of $M$ with respect to $y_{i}$ vanishes for each $i\in[n]$, and thus:

$$ $\left\lvert x_{i}^{\prime}-x_{i}\cdot(1-2\eta)-\eta\right\rvert=\left\lvert \frac{\partial M(x,x^{\prime},y)}{\partial y_{i}}\right\rvert\leq\delta$ (2) $$

This shows that $x_{i}^{\prime}\in[\eta-\delta,1-\eta+\delta]$ and combining with $\eta>\delta$ it follows that $x_{i}^{\prime}\in(0,1)$ and the KKT conditions imply:

$$ $\delta\geq\left\lvert\frac{\partial M(x,x^{\prime},y)}{\partial x_{i}^{\prime} }\right\rvert=\left\lvert\frac{\partial Q^{\prime}(x,x^{\prime})}{\partial x_{ i}^{\prime}}+T\cdot(y_{i}-1/2)\right\rvert\,\implies\,T\cdot(1/2-y_{i})=\frac{ \partial Q^{\prime}(x,x^{\prime})}{\partial x_{i}^{\prime}}\pm\delta$ $$

Where we use the notation $a=b\pm\delta$ to mean $a\in[b-\delta,b+\delta]$. We can now show that the partial derivative of $M$ at $(x,x^{\prime},y)$ is very close to the one of $Q$ at $x$ for all coordinates $x_{i}$:

$$ $\displaystyle\frac{\partial M(x,x^{\prime},y)}{\partial x_{i}}$ $\displaystyle=\frac{\partial Q^{\prime}(x,x^{\prime})}{\partial x_{i}}+(1-2 \eta)\cdot T\cdot(1/2-y_{i})$ $\displaystyle=\frac{\partial Q^{\prime}(x,x^{\prime})}{\partial x_{i}}+(1-2 \eta)\cdot\left(\frac{\partial Q^{\prime}(x,x^{\prime})}{\partial x_{i}^{ \prime}}\pm\delta\right)$ $\displaystyle=\frac{\partial Q^{\prime}(x,x^{\prime})}{\partial x_{i}}+\frac{ \partial Q^{\prime}(x,x^{\prime})}{\partial x_{i}^{\prime}}\pm\left(2\eta\left \lvert\frac{\partial Q^{\prime}(x,x^{\prime})}{\partial x_{i}^{\prime}}\right \rvert+\delta\right)$ $\displaystyle=\frac{\partial Q^{\prime}(x,x^{\prime})}{\partial x_{i}}+\frac{ \partial Q^{\prime}(x,x^{\prime})}{\partial x_{i}^{\prime}}\pm\left(4\eta Z+ \delta\right)$ $\displaystyle=\frac{\partial Q^{\prime}(x,x^{\prime})}{\partial x_{i}}+\frac{ \partial Q^{\prime}(x,x^{\prime})}{\partial x_{i}^{\prime}}\pm 9\varepsilon^{2}$ as $\eta=2\varepsilon^{2}/Z$ and $\delta\leq\varepsilon^{2}$ $$

Observe that (2) also implies that $x_{i}$ and $x_{i}^{\prime}$ must be close with $|x_{i}-x_{i}^{\prime}|\leq\delta+\eta$, hence:

$$ $\displaystyle\frac{\partial Q^{\prime}(x,x^{\prime})}{\partial x_{i}}+\frac{ \partial Q^{\prime}(x,x^{\prime})}{\partial x_{i}^{\prime}}$ $\displaystyle=q_{i}+\sum_{j\neq i}q_{ij}x_{j}+q_{ii}x_{i}+q_{ii}x_{i}^{\prime}$ $\displaystyle=\frac{\partial Q(x)}{\partial x_{i}}+q_{ii}(x_{i}^{\prime}-x_{i})$ $\displaystyle=\frac{\partial Q(x)}{\partial x_{i}}\pm 3\varepsilon^{2}$ as $|q_{ii}|\leq Z$ and $\delta+\eta=3\varepsilon^{2}/Z$ $$

Combining the two previous observations, we have $\partial Q(x)/\partial x_{i}=\partial M(x,x^{\prime},y)/\partial x_{i}\pm 12
\varepsilon^{2}$. With this fact established, we may finally show that $x$ is indeed an $\varepsilon$-KKT point of the $\MinQuadKKT$ formulation. If $x_{i}=0$, then note that:

$$ $\frac{\partial Q(x)}{\partial x_{i}}\geq\frac{\partial M(x,x^{\prime},y)}{ \partial x_{i}}-12\varepsilon^{2}\geq-\delta-12\varepsilon^{2}\geq-13 \varepsilon^{2}\geq-\varepsilon$ $$

A similar computation shows that the KKT conditions are also satisfied if $x_{i}=1$. On the other hand, if $x_{i}\in(0,1)$:

$$ $\left\lvert\frac{\partial Q(x)}{\partial x_{i}}\right\rvert\leq\left\lvert \frac{\partial M(x,x^{\prime},y)}{\partial x_{i}}\right\rvert+12\varepsilon^{2 }\leq\delta+12\varepsilon^{2}\leq\varepsilon.\qed$ $$

###### Lemma 3.1 .

###### Claim 3.1 .

###### Proof.

### 3.2 Stage II: from minmax to two-team games

To prove Theorem 1.1, we use stage I (Lemma 3.1) and show how to reduce an instance of $\MinmaxIndKKT$ to a two-team zero-sum game with independent adversaries. Let $\varepsilon>0$ be the approximation parameter of the instance and its objective be $M:\mathbb{R}^{2n}\to\mathbb{R}$. Since $M$ has the independence property, we can explicitly write its coefficient as:

$$ $M(x,y)\coloneqq\alpha+\sum\nolimits_{i\in[n]}\beta_{i}x_{i}+\sum\nolimits_{i \neq j}\gamma_{ij}x_{i}x_{j}+\sum\nolimits_{i\in[n]}\zeta_{i}y_{i}+\sum \nolimits_{i,j\in[n]}\theta_{ij}x_{i}y_{j}$ $$

We construct a polymatrix game with two teams, each consisting of $n$ players. In the first (cooperative) team, there is one player $a_{i}$ corresponding to each variable $x_{i}$. The second team consists of $n$ independent adversaries, where player $b_{i}$ corresponds to variable $y_{i}$. The intent is that an optimal strategy profile of the players roughly corresponds to a KKT point $(x,y)$ of $M$. As stated earlier, we reduce to a very restricted setting where each player only has two actions. We thus specify the utility matrices of the game as elements of $\mathbb{R}^{2\times 2}$ with:

$$ $\displaystyle A^{a_{i},a_{j}}$ $\displaystyle=A^{a_{j},a_{i}}=\begin{bmatrix}-\gamma_{ij}&0\\ 0&0\end{bmatrix}$ for all $i,j\in[n]$ with $i\neq j$ (3) $\displaystyle A^{b_{j},a_{i}}$ $\displaystyle=-(A^{a_{i},b_{j}})^{\top}=\begin{bmatrix}\theta_{ij}+\zeta_{j}/n +\beta_{i}/n&\zeta_{j}/n\\ \beta_{i}/n&0\end{bmatrix}$ for all $i,j\in[n]$ (4) $$

Any other utility matrix is set to $0^{2\times 2}$. Observe that this payoff setting indeed yields a proper two-team zero-sum polymatrix game with independent adversaries. Let $Z\geq 1$ be an upper bound on the sum of absolute coefficients of $M$ and let $\delta\coloneqq\varepsilon^{2}/(4Z)$ be the target approximation ratio for the polymatrix game. If $(p,q)$ is a $\delta$-approximate Nash equilibrium of the polymatrix game, we define a candidate KKT point $(x,y)\in\mathbb{R}^{2n}$ as follows:

$$ $\displaystyle x_{i}=\begin{cases}0&\quad\text{if $p_{i}<\varepsilon/(2Z)$}\\ 1&\quad\text{if $p_{i}>1-\varepsilon/(2Z)$}\\ a_{i}&\quad\text{else}\end{cases}\quad\quad\text{and}\quad\quad y_{i}=\begin{ cases}0&\quad\text{if $q_{i}<\varepsilon/(2Z)$}\\ 1&\quad\text{if $q_{i}>1-\varepsilon/(2Z)$}\\ d_{i}&\quad\text{else}\end{cases}$ $$

Here $p_{i}\in[0,1]$ represents the probability that player $a_{i}$ plays its first action, and similarly $q_{i}$ for player $b_{i}$. The correctness of the reduction is treated in 3.2 and thus Theorem 1.1 follows.

###### Claim 3.2 .

$(x,y)$ is an $\varepsilon$-approximate KKT point of the $\MinmaxIndKKT$ instance.

###### Proof.

We only show that $x$-variables satisfy the KKT conditions as the proof is similar for the $y$-variables. It follows from (3) and (4) that for any $\widetilde{p}_{i}\in[0,1]$ the utility for player $a_{i}$ can be written as:

$$ $\begin{split}U_{a_{i}}(\widetilde{p}_{i},p_{-i},q)&=\sum\nolimits_{j\neq i} \begin{bmatrix}\widetilde{p}_{i}\\ 1-\widetilde{p}_{i}\end{bmatrix}^{\top}A^{a_{i},a_{j}}\begin{bmatrix}p_{j}\\ 1-p_{j}\end{bmatrix}+\sum\nolimits_{j\in[n]}\begin{bmatrix}\widetilde{p}_{i}\\ 1-\widetilde{p}_{i}\end{bmatrix}^{\top}A^{a_{i},b_{j}}\begin{bmatrix}q_{j}\\ 1-q_{j}\end{bmatrix}\\ &=-\widetilde{p}_{i}\cdot\left(\beta_{i}+\sum\nolimits_{j\neq i}\gamma_{ij}p_{ j}+\sum\nolimits_{j\in[n]}\theta_{ij}q_{j}\right)-\sum\nolimits_{j\in[n]}\zeta _{j}q_{j}/n\end{split}$ $$

Since $(p,q)$ is a $\delta$-approximate Nash equilibrium, we can use the above expression twice and Definition 1 to get that:

$$ $(p_{i}-\widetilde{p}_{i})\cdot\left(\beta_{i}+\sum\nolimits_{j\neq i}\gamma_{ ij}p_{j}+\sum\nolimits_{j\in[n]}\theta_{ij}q_{j}\right)\leq\delta\quad\forall \,\widetilde{p}_{i}\in[0,1]$ (5) $$

Fix some variable $x_{i}$ and let us verify that it satisfies the $\varepsilon$-approximate KKT condition. The partial derivative of $M$ with respect to $x_{i}$ is:

$$ $\displaystyle\frac{\partial M(x,y)}{\partial x_{i}}$ $\displaystyle=\beta_{i}+\sum_{j\neq i}\gamma_{ij}x_{j}+\sum_{j\in[n]}\theta_{ ij}y_{j}$ $\displaystyle=\beta_{i}+\sum_{j\neq i}\gamma_{ij}\cdot(p_{j}+x_{j}-p_{j})+\sum _{j\in[n]}\theta_{ij}\cdot(q_{j}+y_{j}-q_{j})$ $\displaystyle=\beta_{i}+\sum_{j\neq i}\gamma_{ij}p_{j}+\sum_{j\in[n]}\theta_{ ij}q_{j}\pm\Bigg{(}\sum_{j\neq i}|\gamma_{ij}|\cdot|x_{j}-p_{j}|+\sum_{j\in[n] }|\theta_{ij}|\cdot|y_{j}-q_{j}|\Bigg{)}$ $\displaystyle=\beta_{i}+\sum_{j\neq i}\gamma_{ij}p_{j}+\sum_{j\in[n]}\theta_{ ij}q_{j}\pm\frac{\varepsilon}{2Z}\cdot Z$ $$

Where in the last equality, we used the fact that $x$ (respectively $y$) is close to $p$ (respectively $q$).

We now finish the proof by considering two cases for $x_{i}$. First, consider the case where $x_{i}<1$. By definition of $x_{i}$, this implies that $p_{i}\leq 1-\varepsilon/2Z$. Thus, setting $\widetilde{p}_{i}\coloneqq 1$ in (5), we get:

$$ $\displaystyle(1-p_{i})\cdot\left(\beta_{i}+\sum\nolimits_{j\neq i}\gamma_{ij}p _{j}+\sum\nolimits_{j\in[n]}\theta_{ij}q_{j}\right)\geq-\delta$ $\displaystyle\quad\implies\beta_{i}+\sum\nolimits_{j\neq i}\gamma_{ij}p_{j}+ \sum\nolimits_{j\in[n]}\theta_{ij}q_{j}\geq-\frac{\delta}{1-p_{i}}\geq-\frac{2 Z\cdot\delta}{\varepsilon}\geq-\varepsilon/2$ $$

and thus $\partial M(x,y)/\partial x_{i}\geq-\varepsilon/2-\varepsilon/2\geq-\varepsilon$. Next, consider the case where $x_{i}>0$. By definition of $x_{i}$, this implies that $p_{i}\geq\varepsilon/2Z$. Now, setting $\widetilde{p}_{i}\coloneqq 0$ in (5), we get:

$$ $\displaystyle p_{i}\cdot\left(\beta_{i}+\sum\nolimits_{j\neq i}\gamma_{ij}p_{j }+\sum\nolimits_{j\in[n]}\theta_{ij}q_{j}\right)\leq\delta$ $\displaystyle\quad\implies\beta_{i}+\sum\nolimits_{j\neq i}\gamma_{ij}p_{j}+ \sum\nolimits_{j\in[n]}\theta_{ij}q_{j}\leq\frac{\delta}{p_{i}}\leq\frac{2Z \cdot\delta}{\varepsilon}\leq\varepsilon/2$ $$

and thus $\partial M(x,y)/\partial x_{i}\leq\varepsilon/2+\varepsilon/2\leq\varepsilon$. This shows that $x_{i}$ always satisfies the $\varepsilon$-KKT conditions. In particular, when $x_{i}\in(0,1)$, $|\partial M(x,y)/\partial x_{i}|\leq\varepsilon$.
∎

###### Claim 3.2 .

###### Proof.

## 4 \CLS \CLS \CLS -membership for Independent Adversaries

In this section we prove the following.

###### Theorem 4.1 .

The problem of computing a Nash equilibrium in two-team zero-sum polymatrix games with independent adversaries lies in $\CLS$.

In particular, this implies that the $\CLS$-hardness result proved in the previous section is tight for such games.

###### Theorem 4.1 .

#### Reformulation as a minimization problem.

The main idea to prove the theorem is to start from the minmax formulation of the problem and to rewrite it as a minimization problem by using duality. Let a two-team polymatrix zero-sum game with independent adversaries be given. Without loss of generality, we assume that every player has exactly $m$ strategies. Recall that by the structure of the game we have $A^{i,i^{\prime}}=(A^{i^{\prime},i})^{\top}$, $A^{i,j}=-(A^{j,i})^{\top}$, and $A^{j,j^{\prime}}=0$ for all $i,i^{\prime}\in X$, $j,j^{\prime}\in Y$ with $i\neq i^{\prime}$ and $j\neq j^{\prime}$. We can write

$$ $\begin{split}&\min_{x\in\mathcal{X}}\max_{y\in\mathcal{Y}}-\sum_{i,i^{\prime} \in X:i<i^{\prime}}x_{i}A^{i,i^{\prime}}x_{i^{\prime}}-\sum_{i\in X,j\in Y}x_{ i}A^{i,j}y_{j}\\ =&\min_{x\in\mathcal{X}}\max_{y\in\mathcal{Y}}-\sum_{i,i^{\prime}\in X:i<i^{ \prime}}x_{i}A^{i,i^{\prime}}x_{i^{\prime}}+\sum_{i\in X,j\in Y}y_{j}A^{j,i}x_ {i}\\ =&\min_{x\in\mathcal{X}}\left\{-\sum_{i,i^{\prime}\in X:i<i^{\prime}}x_{i}A^{i ,i^{\prime}}x_{i^{\prime}}+\max_{y\in\mathcal{Y}}\sum_{i\in X,j\in Y}y_{j}A^{j ,i}x_{i}\right\}\end{split}$ (6) $$

Now consider the “max” part of the above objective written as the following LP in $y$ variables:

$$ $\displaystyle\begin{split}\max\;\;&\sum_{j\in Y}c_{j}^{\top}y_{j}\\ \;\;&\sum_{k=1}^{m}y_{jk}=1\;\;\forall j\in Y\\ \;\;&y_{jk}\geq 0\;\;\forall j\in Y\;\;\text{and}\;\;\forall k\in[m]\end{split}$ $$

where $c_{j}=\sum_{i\in X}A^{j,i}x_{i}$ for all $j\in Y$. Then the dual of the above program can be written as:

$$ $\displaystyle\begin{split}\min\;\;&\sum_{j\in Y}\gamma_{j}\\ \;\;&\gamma_{j}\geq c_{jk}\;\;\forall j\in Y\;\;\text{and}\;\;\forall k\in[m] \end{split}$ $$

Thus replacing the max part in (6) by the equivalent dual formulation we obtain:

$$ $\begin{split}\min\quad&-\sum_{i,i^{\prime}\in X:i<i^{\prime}}x_{i}A^{i,i^{ \prime}}x_{i^{\prime}}+\sum_{j\in Y}\gamma_{j}\\ \text{s.t. }&\gamma_{j}\geq\sum_{i\in X}e_{k}^{\top}A^{j,i}x_{i}\;\;\forall j \in Y\;\;\text{and}\;\;\forall k\in[m]\\ &\gamma_{j}\leq M\;\;\forall j\in Y\\ &\gamma\in\mathbb{R}^{|Y|}\\ &x\in\mathcal{X}\end{split}$ (7) $$

where $e_{k}\in\mathbb{R}^{m}$ is the $k$th unit vector. We have introduced an additional set of constraints $\gamma_{j}\leq M$ to ensure that the feasible region is bounded. $M$ is chosen to be sufficiently large such that $M>\max_{x\in\mathcal{X},j\in Y,k\in[m]}\sum_{i\in X}e_{k}^{\top}A^{j,i}x_{i}$. Note that in order to obtain the formulation (7) we have crucially used the fact that the original game is polymatrix and has independent adversaries.

For what comes next, we will need the following definition of KKT points, which generalizes Definition 3 to arbitrary linear constraints.

###### Definition 5 .

Consider an optimization problem of the form

$$ $\begin{split}\min\quad&f(x)\\ \text{s.t. }&Ax\leq b\\ &x\in\mathbb{R}^{n}\end{split}$ $$

where $f:\mathbb{R}^{n}\to\mathbb{R}$ is continuously differentiable, $A\in\mathbb{R}^{m\times n}$, and $b\in\mathbb{R}^{m}$. A point $x^{*}\in\mathbb{R}^{n}$ is a KKT point of this problem if there exists $\mu\in\mathbb{R}^{m}$ such that

- 1.
$\nabla f(x^{*})+A^{\top}\mu=0$
- 2.
$Ax^{*}\leq b$
- 3.
$\mu\geq 0$
- 4.
$\mu^{\top}(b-Ax)=0$

We can now continue with our proof of Theorem 4.1.
The problem of finding an exact KKT point of (7) lies in \CLS. Indeed, it is known that finding an approximate KKT point of such a program lies in \CLS [, Theorem 5.1], and, given that the objective function is a quadratic polynomial, an approximate KKT point (with sufficiently small approximation error) can be turned into an exact one in polynomial time (see, e.g., [, Lemma A.1]).

Theorem 4.1 now simply follows from the following claim.

###### Claim 4.1 .

Given a KKT point of (7), we can compute a Nash equilibrium of the original game in polynomial time.

###### Proof.

Let $(x^{*},\gamma^{*})$ be a KKT point of (7). We define notation for the following multipliers:

- •
For all $j\in Y$ and $k\in[m]$, $\mu_{jk}^{*}\in\mathbb{R}_{\geq 0}$ corresponding to the constraint $\gamma_{j}\geq\sum_{i\in X}e_{k}^{\top}A^{j,i}x_{i}$.
- •
For all $i\in X$, $\lambda_{i}^{*}\in\mathbb{R}$ corresponding to the constraint $\sum_{k\in[m]}x_{ik}=1$.
- •
For all $i\in X$ and $k\in[m]$, $\nu_{ik}^{*}\in\mathbb{R}_{\geq 0}$ corresponding to the constraint $x_{ik}\geq 0$.

Note that we have not included multipliers for the constraints $\gamma_{j}\leq M$. This is because none of these constraints will ever be tight at a KKT point $(x^{*},\gamma^{*})$ by construction of $M$.

Now, since $(x^{*},\gamma^{*})$ is a KKT point, we can compute such multipliers that satisfy the following KKT conditions (which are derived from Definition 5) in polynomial time(^3^33Indeed, it is easy to check that given $(x^{*},\gamma^{*})$ such multipliers can then be found by solving an LP.):

- 1.
For all $i\in X$
$-\sum_{i^{\prime}\neq i}A^{i,i^{\prime}}x_{i^{\prime}}^{*}-\sum_{j\in Y}A^{i,j
}\mu_{j}^{*}+\lambda_{i}^{*}\cdot 1_{m}-\nu_{i}^{*}=0$
where $1_{m}$ denotes a vector of $m$ ones, and where we used the fact that $A^{i,j}=-(A^{j,i})^{\top}$. Additionally, we have that for all $k\in[m]$, $\nu_{ik}^{*}>0\implies x_{ik}^{*}=0$.
- 2.
For all $j\in Y$
$1-\sum_{k\in[m]}\mu_{jk}^{*}=0.$
- 3.
For all $j\in Y$ and $k\in[m]$, $\mu_{jk}^{*}>0\implies\gamma_{j}^{*}=\sum_{i\in X}e_{k}A^{j,i}x_{i}^{*}$.

Now, we claim that $(x^{*},\mu^{*})$ forms a Nash equilibrium of the original game. First of all, note that by property 2 we have $\sum_{k\in[m]}\mu_{jk}^{*}=1$ and thus $\mu_{j}^{*}$ is indeed a valid mixed strategy for player $j\in Y$. Next, property 3 can be rewritten as

$$ $\mu_{jk}^{*}>0\implies U_{j}(x^{*},\mu_{-j}^{*},e_{k})=\sum_{i\in X}e_{k}A^{j, i}x_{i}^{*}=\gamma_{j}^{*}\geq\max_{k^{\prime}\in[m]}\sum_{i\in X}e_{k^{\prime }}A^{j,i}x_{i}^{*}=\max_{k^{\prime}\in[m]}U_{j}(x^{*},\mu_{-j}^{*},e_{k^{ \prime}})$ $$

which means that the strategy of player $j$, namely $\mu_{j}^{*}$, is a best-response. Finally, property 1 can be reinterpreted as saying that $x_{i}^{*}$ is a KKT point of the following optimization problem (in variables $x_{i}$)

$$ $\begin{split}\min\quad&-\sum_{i^{\prime}\neq i}x_{i}A^{i,i^{\prime}}x_{i^{ \prime}}^{*}-\sum_{j\in Y}x_{i}A^{i,j}\mu_{j}^{*}\quad[=U_{i}(x_{i},x_{-i}^{*} ,\mu^{*})]\\ \text{s.t. }&x_{i}\in\mathcal{X}_{i}\end{split}$ $$

Since this is an LP, any KKT point is also a global solution. Thus, $x_{i}^{*}$ is a global minimum of this LP, which means that player $i$ is also playing a best-response.
∎

###### Definition 5 .

###### Claim 4.1 .

###### Proof.

## 5 Open Problems

Our work leaves some interesting open questions for future work:

- •
What is the complexity of the two-team polymatrix setting when there is a single adversary? The \CLS-membership of course still applies, but no hardness result is known.
- •
Our \CLS-membership result only applies to the setting where the adversaries are independent. If interactions between adversaries are allowed then the problem is only known to lie in \PPAD, so there is a gap with the \CLS-hardness that we show. Is the problem \CLS-complete, \PPAD-complete, or neither?
- •
Our hardness result provides strong evidence that no algorithm with running time $O(\poly(\allowbreak\log(\allowbreak 1/\varepsilon)))$ exists. However, there are gradient-based approaches that yield algorithms with running time $O(\poly(1/\varepsilon))$. What is the optimal polynomial dependence in $1/\varepsilon$ for such algorithms?

### Acknowledgements

AH and GM were supported by the Swiss State Secretariat for Education, Research and Innovation (SERI) under contract number MB22.00026. SGN would like to thank Ioannis Panageas and colleagues at ZIB for discussions pertaining to this project.

## Peer Reviews

confidence: 4
contribution: 3
initial_rating: 8
presentation: 3
questions: - **Line 386**: In the reduction from MinmaxIndKKT, the authors define the candidate KKT point $(x_i, y_i)$ for the case where neither $x_i$ nor $y_i$ is in ${0, 1\}$ as $x_i = a_i$ and $y_i = d_i$. I assume that $a_i$ is simply a typo, as $a_i$ is already used to denote player $i$ on the first team. I think the authors likely intended to use $p_i$ and $q_i$ for $x_i$ and $y_i$, which would also align with the statement in line 415 indicating that these variables are close to their respective counterparts, $p_i$ and $q_i$.

References  
[1] The complexity of computing KKT solutions of quadratic programs.

[2] Constantinos Daskalakis, Stratis Skoulakis, and Manolis Zampetakis. The complexity of constrained min-max optimization.
soundness: 4
strengths: The paper is generally well-written, though there are areas where phrasing could be improved. The problem under consideration is quite interesting and represents a step forward in establishing complexity results for two-team (zero-sum) games, i.e., min-max optimization problems beyond the case of having coupled constraints as in [2]. Of course, the more general case of having dependent adversaries (or that of a single adversary) remains open, as the authors highlight in Section 5.
summary: In this work, the authors investigate the computational complexity of computing a Nash equilibrium in two-team zero-sum polymatrix games where one team consists of independent players (i.e., players who do not interact with one another). Specifically, they prove that this problem is complete for the complexity class CLS. To demonstrate hardness, they first reduce from MinQuadraticKKT—the problem of computing a KKT point of a quadratic function with box constraints—to MinmaxIndKKT, a min-max problem with an independence property they define. In a second step, they reduce this problem to a two-team zero-sum polymatrix game. Membership in CLS follows fairly straightforwardly from the recent result that QuadraticKKT is complete for the class CLS, as shown in [1], and using LP duality for transforming a min-max problem into a minimization.
weaknesses: I cannot identify any obvious weaknesses. Although the techniques and ideas are not particularly complex—as is often the case in results of this kind—this should not in itself be considered a weakness. However, the simplicity of the proof and the lack of novel ideas makes me more skeptical about my final score.

---

confidence: 3
contribution: 3
initial_rating: 8
presentation: 4
questions: Could you add some discussion about the broader landscape of team games, why we might care about them (if not necessarily the two-player polymatrix team games), and about the best-known algorithmic results in this space, particularly in the context of learning dynamics?
soundness: 4
strengths: The paper solves a well formulated problem about the complexity of finding Nash equilibria. This problem is a natural continuation of prior results about team polymatrix games. The technical proofs and reductions are interesting and well written.
summary: The paper studies the problem of finding Nash Equilibria in two-team polymatrix games. Polymatrix games are a special class of n-player games with a succinct representation of the payoff functions. Each player's payoff is a sum of payoffs resulting from two-player games played with all the other players. This problem is known to be tractable when all interactions are zero-sum, and to be PPAD-hard in general. A special subclass of these games are team games, where each pair of interactions are either zero-sum (different teams) or coordination games (same team). Three team games are known to be PPAD complete. The main result of the paper is in showing that two team games are CLS hard (CLS is a structured subclass of PPAD).  This result holds even when one of the team consists of independent adversaries (their games consist of the zero matrix for all the payoffs). They also show that computing the minimax/ KKT point of a bilinear polynomial is also CLS hard.
weaknesses: The main weakness is in the lack of appeal to a broader ICLR audience. The paper has solid results in complexity theory and game theory but requires some connection to the machine learning audience. That such a connection exists is not in itself in question, there are a plethora of papers about learning equilibria in team games, but the paper offers no discussion about the broader significance of studying team games. The open problems section also mentions gradient based methods that converge to equilibria in time poly(1/epsilon), but there is not further discussion.

---

confidence: 3
contribution: 3
initial_rating: 8
presentation: 4
questions: Perhaps the most obvious gap in this paper is the CLS-membership without the independent adversaries assumption. Do you think there is any hope to extend your techniques to that case?
soundness: 4
strengths: I think this is a good paper and vote to accept. The paper is clearly written and presents an interesting result. The hardness result about minimax KKT points is also rather clean, and may be of independent interest as a CLS-complete problem that may be relatively easy to make reductions from. The concerns below are very minor.
summary: This paper studies the complexity of finding a Nash equilibrium in two-team polymatrix zero-sum games. They show that this problem is CLS-hard, and is in CLS if the adversaries are independent (thus establishing CLS-completeness in the latter case).
weaknesses: The section about ex-ante coordination contains some strange choices of phrasing. For example, all of the papers in that paragraph study extensive-form games (not just the last one), and the paper that shows "efficient algorithms exist under some assumptions about the players’ information set" is Zhang and Sandholm (2022), not Zhang et al. (2021).

To get parenthetical citations like (Lastname et al. 2023) instead of Lastname et al. (2023), use \citep.

Meta-review: This paper looks at the complexity of computing teams equilibria in game.

It is a good theoretic contribution that the reviewers and I enjoyed reading. It is well written and rather insightful.

Happy to recommend acceptance.

Decision: Accept (Oral)