# Query-Efficient Algorithm to Find all Nash Equilibria in a Two-Player Zero-Sum Matrix Game
**Authors**: Arnab Maiti, Ross Boczar, Kevin Jamieson, Lillian J. Ratliff, University of Washington
## Abstract
We study the query complexity of finding the set of all Nash equilibria $X_⋆×Y_⋆$ in two-player zero-sum matrix games. Fearnley and Savani [17] showed that for any randomized algorithm, there exists an $n× n$ input matrix where it needs to query $Ω(n^2)$ entries in expectation to compute a single Nash equilibrium. On the other hand, Bienstock et al. [5] showed that there is a special class of matrices for which one can query $O(n)$ entries and compute its set of all Nash equilibria. However, these results do not fully characterize the query complexity of finding the set of all Nash equilibria in two-player zero-sum matrix games.
In this work, we characterize the query complexity of finding the set of all Nash equilibria $X_⋆×Y_⋆$ in terms of the number of rows $n$ of the input matrix $A∈ℝ^n× n$ , row support size $k_1:=|\bigcup\limits_x∈X_⋆\operatorname*{supp}(x)|$ , and column support size $k_2:=|\bigcup\limits_y∈Y_⋆\operatorname*{supp}(y)|$ . We design a simple yet non-trivial randomized algorithm that, with probability $1-δ$ , returns the set of all Nash equilibria $X_⋆×Y_⋆$ by querying at most $O(nk^5·polylog(n/δ))$ entries of the input matrix $A∈ℝ^n× n$ , where $k:=\max\{k_1,k_2\}$ . This upper bound is tight up to a factor of $poly(k)$ , as we show that for any randomized algorithm, there exists an $n× n$ input matrix with $\min\{k_1,k_2\}=1$ , for which it needs to query $Ω(nk)$ entries in expectation in order to find the set of all Nash equilibria $X_⋆×Y_⋆$ .
## 1 Introduction
Von Neumann’s celebrated minimax theorem [22] initiated the study of two-player zero-sum matrix games by demonstrating the existence of a Nash equilibrium. Subsequently, it was established that two-player zero-sum matrix games are equivalent to linear programming [12, 1, 8]. With the development of polynomial-time algorithms for linear programming, it became evident that one can compute a Nash equilibrium for a two-player zero-sum matrix game in polynomial time. This implication has motivated key works at the intersection of game theory and theoretical computer science [9, 13, 14, 15, 4].
One of these works was the development of query-efficient algorithms for finding equilibrium solutions. In the context of two-player zero-sum games, a surprising result was demonstrated by Bienstock et al. [5]. They presented a deterministic algorithm that finds the strict saddle point (if it exists) by querying $O(n)$ entries of the input matrix $A∈ℝ^n× n$ . A strict saddle point is an entry of a matrix that is uniquely the smallest in its row and uniquely the largest in its column. In game theory, such an entry is referred to as a strict Pure Strategy Nash equilibrium. In contrast, Fearnley and Savani [17] showed that for any randomized algorithm, there exists an $n× n$ input matrix $A∈ℝ^n× n$ from which the algorithm needs to query $Ω(n^2)$ entries in expectation to compute a single Nash equilibrium. This lower bound arises when the Nash equilibrium is a mixed strategy with all rows and columns in the support of this mixed strategy. The results of Bienstock et al. [5] and Fearnley and Savani [17] represent two extremes on the spectrum of solution sizes, highlighting a significant gap in the existing literature. Recently, Auger et al. [2] attempted to address this gap by studying a class of matrices with unique Nash equilibrium and binary entries, characterizing the query complexity in terms of the support size of the Nash equilibrium strategy. However, such a characterization for arbitrary matrices in $ℝ^n× n$ that may have multiple Nash equilibria remains unaddressed in prior work. This leads us to the following question:
Can we characterize the query complexity of finding the set of all Nash equilibria of a matrix $A∈ℝ^n× n$ in terms of an appropriate notion of the Nash equilibria solution size?
In this work, we address the above question. To this end, let us briefly review two-player zero-sum games on an input matrix $A∈ℝ^n× n$ . Let $\mathchoice{∈cludegraphics[height=6.02773pt,trim=0.0pt 30.0pt 0.0pt 0.0pt]{ graphics/simplex.pdf}}{∈cludegraphics[height=6.02773pt,trim=0.0pt 25.0pt 0.0 pt 0.0pt]{graphics/simplex.pdf}}{∈cludegraphics[height=4.73611pt,trim=0.0pt 30.0pt 0.0pt 0.0pt]{graphics/simplex.pdf}}{∈cludegraphics[height=3.44444pt,t rim=0.0pt 30.0pt 0.0pt 0.0pt]{graphics/simplex.pdf}}_n$ denote the $(n-1)$ -dimensional probability simplex. A pair $(x_⋆,y_⋆)∈\mathchoice{∈cludegraphics[height=6.02773pt,trim=0.0 pt 30.0pt 0.0pt 0.0pt]{graphics/simplex.pdf}}{∈cludegraphics[height=6.02773 pt,trim=0.0pt 25.0pt 0.0pt 0.0pt]{graphics/simplex.pdf}}{∈cludegraphics[heig ht=4.73611pt,trim=0.0pt 30.0pt 0.0pt 0.0pt]{graphics/simplex.pdf}}{ ∈cludegraphics[height=3.44444pt,trim=0.0pt 30.0pt 0.0pt 0.0pt]{graphics/ simplex.pdf}}_n×\mathchoice{∈cludegraphics[height=6.02773pt,trim=0.0 pt 30.0pt 0.0pt 0.0pt]{graphics/simplex.pdf}}{∈cludegraphics[height=6.02773 pt,trim=0.0pt 25.0pt 0.0pt 0.0pt]{graphics/simplex.pdf}}{∈cludegraphics[heig ht=4.73611pt,trim=0.0pt 30.0pt 0.0pt 0.0pt]{graphics/simplex.pdf}}{ ∈cludegraphics[height=3.44444pt,trim=0.0pt 30.0pt 0.0pt 0.0pt]{graphics/ simplex.pdf}}_n$ is a Nash equilibrium of an input matrix $A∈ℝ^n× n$ if and only if the following holds for all $(x,y)∈\mathchoice{∈cludegraphics[height=6.02773pt,trim=0.0pt 30.0pt 0.0pt 0.0pt]{graphics/simplex.pdf}}{∈cludegraphics[height=6.02773pt,trim=0.0pt 25. 0pt 0.0pt 0.0pt]{graphics/simplex.pdf}}{∈cludegraphics[height=4.73611pt,trim =0.0pt 30.0pt 0.0pt 0.0pt]{graphics/simplex.pdf}}{∈cludegraphics[height=3.44 444pt,trim=0.0pt 30.0pt 0.0pt 0.0pt]{graphics/simplex.pdf}}_n× \mathchoice{∈cludegraphics[height=6.02773pt,trim=0.0pt 30.0pt 0.0pt 0.0pt]{ graphics/simplex.pdf}}{∈cludegraphics[height=6.02773pt,trim=0.0pt 25.0pt 0.0 pt 0.0pt]{graphics/simplex.pdf}}{∈cludegraphics[height=4.73611pt,trim=0.0pt 30.0pt 0.0pt 0.0pt]{graphics/simplex.pdf}}{∈cludegraphics[height=3.44444pt,t rim=0.0pt 30.0pt 0.0pt 0.0pt]{graphics/simplex.pdf}}_n$ :
$$
⟨ x,Ay_⋆⟩≤⟨ x_⋆,Ay_⋆⟩≤⟨ x
_⋆,Ay⟩. \tag{1}
$$
Von Neumann’s minimax theorem states that $\max_x∈\mathchoice{∈cludegraphics[height=4.2194pt,trim=0.0pt 30.0pt 0.0pt 0.0pt]{graphics/simplex.pdf}{∈cludegraphics[height=4.2194pt,trim=0.0pt 25. 0pt 0.0pt 0.0pt]{graphics/simplex.pdf}}{∈cludegraphics[height=3.31529pt,trim =0.0pt 30.0pt 0.0pt 0.0pt]{graphics/simplex.pdf}}{∈cludegraphics[height=2.41 112pt,trim=0.0pt 30.0pt 0.0pt 0.0pt]{graphics/simplex.pdf}}_n}\min_y∈ \mathchoice{∈cludegraphics[height=4.2194pt,trim=0.0pt 30.0pt 0.0pt 0.0pt]{ graphics/simplex.pdf}{∈cludegraphics[height=4.2194pt,trim=0.0pt 25.0pt 0.0 pt 0.0pt]{graphics/simplex.pdf}}{∈cludegraphics[height=3.31529pt,trim=0.0pt 30.0pt 0.0pt 0.0pt]{graphics/simplex.pdf}}{∈cludegraphics[height=2.41112pt,t rim=0.0pt 30.0pt 0.0pt 0.0pt]{graphics/simplex.pdf}}_n}⟨ x,Ay⟩= \min_y∈\mathchoice{∈cludegraphics[height=4.2194pt,trim=0.0pt 30.0pt 0.0pt 0.0pt]{graphics/simplex.pdf}{∈cludegraphics[height=4.2194pt,trim=0.0pt 25. 0pt 0.0pt 0.0pt]{graphics/simplex.pdf}}{∈cludegraphics[height=3.31529pt,trim =0.0pt 30.0pt 0.0pt 0.0pt]{graphics/simplex.pdf}}{∈cludegraphics[height=2.41 112pt,trim=0.0pt 30.0pt 0.0pt 0.0pt]{graphics/simplex.pdf}}_n}\max_x∈ \mathchoice{∈cludegraphics[height=4.2194pt,trim=0.0pt 30.0pt 0.0pt 0.0pt]{ graphics/simplex.pdf}{∈cludegraphics[height=4.2194pt,trim=0.0pt 25.0pt 0.0 pt 0.0pt]{graphics/simplex.pdf}}{∈cludegraphics[height=3.31529pt,trim=0.0pt 30.0pt 0.0pt 0.0pt]{graphics/simplex.pdf}}{∈cludegraphics[height=2.41112pt,t rim=0.0pt 30.0pt 0.0pt 0.0pt]{graphics/simplex.pdf}}_n}⟨ x,Ay⟩$ (denoted as the value of the game $V_A^⋆$ ). Thus, $(x_⋆,y_⋆)$ is a Nash equilibrium of the matrix $A$ if and only if
$$
x_⋆∈X_⋆:=\arg\max_x∈\mathchoice{∈cludegraphics[he
ight=4.2194pt,trim=0.0pt 30.0pt 0.0pt 0.0pt]{graphics/simplex.pdf}{
∈cludegraphics[height=4.2194pt,trim=0.0pt 25.0pt 0.0pt 0.0pt]{graphics/
simplex.pdf}}{∈cludegraphics[height=3.31529pt,trim=0.0pt 30.0pt 0.0pt 0.0pt]
{graphics/simplex.pdf}}{∈cludegraphics[height=2.41112pt,trim=0.0pt 30.0pt 0.
0pt 0.0pt]{graphics/simplex.pdf}}_n}\min_y∈\mathchoice{∈cludegraphics[h
eight=4.2194pt,trim=0.0pt 30.0pt 0.0pt 0.0pt]{graphics/simplex.pdf}{
∈cludegraphics[height=4.2194pt,trim=0.0pt 25.0pt 0.0pt 0.0pt]{graphics/
simplex.pdf}}{∈cludegraphics[height=3.31529pt,trim=0.0pt 30.0pt 0.0pt 0.0pt]
{graphics/simplex.pdf}}{∈cludegraphics[height=2.41112pt,trim=0.0pt 30.0pt 0.
0pt 0.0pt]{graphics/simplex.pdf}}_n}⟨ x,Ay⟩ and y
_⋆∈Y_⋆:=\arg\min_y∈\mathchoice{∈cludegraphics[hei
ght=4.2194pt,trim=0.0pt 30.0pt 0.0pt 0.0pt]{graphics/simplex.pdf}{
∈cludegraphics[height=4.2194pt,trim=0.0pt 25.0pt 0.0pt 0.0pt]{graphics/
simplex.pdf}}{∈cludegraphics[height=3.31529pt,trim=0.0pt 30.0pt 0.0pt 0.0pt]
{graphics/simplex.pdf}}{∈cludegraphics[height=2.41112pt,trim=0.0pt 30.0pt 0.
0pt 0.0pt]{graphics/simplex.pdf}}_n}\max_x∈\mathchoice{∈cludegraphics[h
eight=4.2194pt,trim=0.0pt 30.0pt 0.0pt 0.0pt]{graphics/simplex.pdf}{
∈cludegraphics[height=4.2194pt,trim=0.0pt 25.0pt 0.0pt 0.0pt]{graphics/
simplex.pdf}}{∈cludegraphics[height=3.31529pt,trim=0.0pt 30.0pt 0.0pt 0.0pt]
{graphics/simplex.pdf}}{∈cludegraphics[height=2.41112pt,trim=0.0pt 30.0pt 0.
0pt 0.0pt]{graphics/simplex.pdf}}_n}⟨ x,Ay⟩.
$$
An important property of the sets $X_⋆$ and $Y_⋆$ is that they are convex, closed, and bounded polytopes (see [6]). In any zero-sum game, there is either exactly one Nash equilibrium $(x_⋆,y_⋆)$ or infinitely many. However, the value $⟨ x_⋆,Ay_⋆⟩$ is unique and equal to $V_A^⋆$ . We refer the reader to Section 2 for additional properties of Nash equilibrium, as well as for details on how to efficiently represent the sets $X_⋆$ and $Y_⋆$ .
Our work diverges from prior work as we focus on finding the set of all Nash equilibria $X_⋆×Y_⋆$ . This allows us to perform a full strategic analysis of a game, whereas finding only a single equilibrium provides merely a partial view. For example, finding the set of all Nash equilibria allows us to identify all non-degenerate parts of the game that contain equilibrium solutions. Such a non-degenerate part is typically a square submatrix with a unique Nash equilibrium. Additionally, finding the set of all Nash equilibria helps us determine which rows (resp. columns) are suboptimal, in the sense that these rows (resp. columns) are not best response strategies to some Nash equilibrium strategy of the column (resp. row) player.
In the rest of this section, we outline the appropriate notion of Nash equilibria solution size, detail our contributions and techniques, discuss related works, and introduce important notations.
### 1.1 Appropriate notion of the Nash equilibria solution size
Recall that $V_A^⋆:=\max_x∈\mathchoice{∈cludegraphics[height=4.2194pt,trim=0.0 pt 30.0pt 0.0pt 0.0pt]{graphics/simplex.pdf}{∈cludegraphics[height=4.2194pt ,trim=0.0pt 25.0pt 0.0pt 0.0pt]{graphics/simplex.pdf}}{∈cludegraphics[height =3.31529pt,trim=0.0pt 30.0pt 0.0pt 0.0pt]{graphics/simplex.pdf}}{ ∈cludegraphics[height=2.41112pt,trim=0.0pt 30.0pt 0.0pt 0.0pt]{graphics/ simplex.pdf}}_n}\min_y∈\mathchoice{∈cludegraphics[height=4.2194pt,trim= 0.0pt 30.0pt 0.0pt 0.0pt]{graphics/simplex.pdf}{∈cludegraphics[height=4.219 4pt,trim=0.0pt 25.0pt 0.0pt 0.0pt]{graphics/simplex.pdf}}{∈cludegraphics[hei ght=3.31529pt,trim=0.0pt 30.0pt 0.0pt 0.0pt]{graphics/simplex.pdf}}{ ∈cludegraphics[height=2.41112pt,trim=0.0pt 30.0pt 0.0pt 0.0pt]{graphics/ simplex.pdf}}_n}⟨ x,Ay⟩=\min_y∈\mathchoice{∈cludegraphics[h eight=4.2194pt,trim=0.0pt 30.0pt 0.0pt 0.0pt]{graphics/simplex.pdf}{ ∈cludegraphics[height=4.2194pt,trim=0.0pt 25.0pt 0.0pt 0.0pt]{graphics/ simplex.pdf}}{∈cludegraphics[height=3.31529pt,trim=0.0pt 30.0pt 0.0pt 0.0pt] {graphics/simplex.pdf}}{∈cludegraphics[height=2.41112pt,trim=0.0pt 30.0pt 0. 0pt 0.0pt]{graphics/simplex.pdf}}_n}\max_x∈\mathchoice{∈cludegraphics[h eight=4.2194pt,trim=0.0pt 30.0pt 0.0pt 0.0pt]{graphics/simplex.pdf}{ ∈cludegraphics[height=4.2194pt,trim=0.0pt 25.0pt 0.0pt 0.0pt]{graphics/ simplex.pdf}}{∈cludegraphics[height=3.31529pt,trim=0.0pt 30.0pt 0.0pt 0.0pt] {graphics/simplex.pdf}}{∈cludegraphics[height=2.41112pt,trim=0.0pt 30.0pt 0. 0pt 0.0pt]{graphics/simplex.pdf}}_n}⟨ x,Ay⟩$ , $X_⋆:=\arg\max_x∈\mathchoice{∈cludegraphics[height=4.2194 pt,trim=0.0pt 30.0pt 0.0pt 0.0pt]{graphics/simplex.pdf}{∈cludegraphics[heig ht=4.2194pt,trim=0.0pt 25.0pt 0.0pt 0.0pt]{graphics/simplex.pdf}}{ ∈cludegraphics[height=3.31529pt,trim=0.0pt 30.0pt 0.0pt 0.0pt]{graphics/ simplex.pdf}}{∈cludegraphics[height=2.41112pt,trim=0.0pt 30.0pt 0.0pt 0.0pt] {graphics/simplex.pdf}}_n}\min_y∈\mathchoice{∈cludegraphics[height=4.21 94pt,trim=0.0pt 30.0pt 0.0pt 0.0pt]{graphics/simplex.pdf}{∈cludegraphics[he ight=4.2194pt,trim=0.0pt 25.0pt 0.0pt 0.0pt]{graphics/simplex.pdf}}{ ∈cludegraphics[height=3.31529pt,trim=0.0pt 30.0pt 0.0pt 0.0pt]{graphics/ simplex.pdf}}{∈cludegraphics[height=2.41112pt,trim=0.0pt 30.0pt 0.0pt 0.0pt] {graphics/simplex.pdf}}_n}⟨ x,Ay⟩$ , and $Y_⋆:=\arg\min_y∈\mathchoice{∈cludegraphics[height=4.2194 pt,trim=0.0pt 30.0pt 0.0pt 0.0pt]{graphics/simplex.pdf}{∈cludegraphics[heig ht=4.2194pt,trim=0.0pt 25.0pt 0.0pt 0.0pt]{graphics/simplex.pdf}}{ ∈cludegraphics[height=3.31529pt,trim=0.0pt 30.0pt 0.0pt 0.0pt]{graphics/ simplex.pdf}}{∈cludegraphics[height=2.41112pt,trim=0.0pt 30.0pt 0.0pt 0.0pt] {graphics/simplex.pdf}}_n}\max_x∈\mathchoice{∈cludegraphics[height=4.21 94pt,trim=0.0pt 30.0pt 0.0pt 0.0pt]{graphics/simplex.pdf}{∈cludegraphics[he ight=4.2194pt,trim=0.0pt 25.0pt 0.0pt 0.0pt]{graphics/simplex.pdf}}{ ∈cludegraphics[height=3.31529pt,trim=0.0pt 30.0pt 0.0pt 0.0pt]{graphics/ simplex.pdf}}{∈cludegraphics[height=2.41112pt,trim=0.0pt 30.0pt 0.0pt 0.0pt] {graphics/simplex.pdf}}_n}⟨ x,Ay⟩$ . This work aims to characterize the query complexity of finding the set of all Nash equilibria $X_⋆×Y_⋆$ in terms of the dimension $n$ of the input matrix $A∈ℝ^n× n$ and the support sizes $k_1:=|\bigcup\limits_x∈X_⋆\operatorname*{supp}(x)|$ and $k_2:=|\bigcup\limits_y∈Y_⋆\operatorname*{supp}(y)|$ . To motivate why these are appropriate notions of Nash equilibria solution size, we first present the following important result by Bohnenblust et al. [7].
**Lemma 1 (Bohnenblust et al. [7])**
*Consider an input matrix $A∈ℝ^n× n$ . Let $I_x=\{j∈[n]:V_A^⋆=⟨ x,Ae_j⟩\}$ and $I_y=\{i∈[n]:V_A^⋆=⟨ e_i,Ay⟩\}$ , where $e_i$ denotes the vector with a $1$ in the $i$ -th coordinate and $0 0$ ’s elsewhere. For any $v∈ℝ^n$ , let $\operatorname*{supp}(v):=\{i∈[n]\mid v_i≠ 0\}$ . Then we have the following:
$$
\bigcup\limits_x∈X_⋆\operatorname*{supp}(x)=\bigcap\limits
_y∈Y_⋆I_y and \bigcup\limits_y∈
Y_⋆\operatorname*{supp}(y)=\bigcap\limits_x∈X_
⋆I_x
$$*
The above lemma suggests that rows not in $\bigcup\limits_x∈X_⋆\operatorname*{supp}(x)$ are strictly worse than the rows in $\bigcup\limits_x∈X_⋆\operatorname*{supp}(x)$ . This is because for all $y^*∈Y^⋆$ and $i∈\bigcup\limits_x∈X_⋆\operatorname*{supp}(x)$ , we have $V_A^⋆=⟨ e_i,Ay^*⟩$ . In contrast, there exists a $\hat{y}∈Y^⋆$ such that for all $i∉\bigcup\limits_x∈X_⋆\operatorname*{supp}(x)$ , $V_A^⋆>⟨ e_i,A\hat{y}⟩$ . Hence, the number of optimal rows $|\bigcup\limits_x∈X_⋆\operatorname*{supp}(x)|$ is an appropriate measure of the solution size for the row player. Using similar logic, we can justify that the number of optimal columns $|\bigcup\limits_y∈Y_⋆\operatorname*{supp}(y)|$ is an appropriate measure of the solution size for the column player.
Moreover, it is easy to observe that changing the value of the entries $(i,j)$ where $i∉\bigcup\limits_x∈X_⋆\operatorname*{supp}(x)$ and $j∉\bigcup\limits_y∈Y_⋆\operatorname*{supp}(y)$ does not affect the set of all Nash equilibria $X_⋆×Y_⋆$ . This implies that only $O(n·\max\{k_1,k_2\})$ elements are important in determining the set of all Nash equilibria $X_⋆×Y_⋆$ , which further highlights why $k_1$ and $k_2$ are appropriate notions of the solution size.
### 1.2 Our contributions and innovative techniques
Let $k:=\max\{k_1,k_2\}$ , where $k_1:=|\bigcup\limits_x∈X_⋆\operatorname*{supp}(x)|$ and $k_2:=|\bigcup\limits_y∈Y_⋆\operatorname*{supp}(y)|$ . Our main technical contribution in this paper is the following upper bound result.
**Theorem 1**
*There exists a randomized algorithm that, with probability at least $1-δ$ , queries $O(nk^5·\log n·\log(\frac{n}{δ}))$ entries of the input matrix $A∈ℝ^n× n$ and returns the set of all Nash equilibria $X_⋆×Y_⋆$ .*
We outline the innovative techniques used to achieve the result above. As discussed in the previous section, the results of Bohnenblust et al. [7] suggest a separation between the sub-matrix with row indices $\bigcup\limits_x∈X_⋆\operatorname*{supp}(x)$ and column indices $\bigcup\limits_y∈Y_⋆\operatorname*{supp}(y)$ (which we will refer to as the optimal sub-matrix) and the rest of the matrix. Our goal is to formalize this separation and therefore leverage it to identify the set of all Nash equilibria while minimizing the number of queries required. In the specific case of strict Pure Strategy Nash Equilibrium (strict PSNE), this separation is inherently present, as a strict PSNE is uniquely the least in its row and uniquely the highest in its column. Therefore, one possible approach involves constructing a large matrix with ${n\choose k_1}$ rows and ${n\choose k_2}$ columns, where each entry is bijectively mapped to a $k_1× k_2$ sub-matrix of $A$ . The values of these entries are determined by their corresponding sub-matrices in $A$ , and this large matrix possesses a strict PSNE that maps to the optimal sub-matrix of $A$ .
Assuming we can construct such a matrix, it remains unclear how to query the entries of this large matrix without significantly increasing the query complexity of our algorithm. The algorithm proposed by Bienstock et al. [5] is inadequate for this purpose because it queries entries diagonally. If we applied a similar diagonal querying strategy to our large matrix, we would end up querying all entries of the original matrix $A$ . Instead, we propose a randomized algorithm for finding strict PSNE that operates differently from the one described by Bienstock et al. [5]. Specifically, if we have access to query oracles where a single call returns either the entire row or the entire column, our algorithm can identify the strict PSNE by making $O(\log^2(r))$ oracle calls, where $r$ is the total number of rows and columns in the input matrix with a strict PSNE. We can also design a query oracle for the larger matrix that returns a row or column by querying at most $O(nk)$ entries of $A$ . Hence, the query complexity of finding the strict PSNE of the large matrix will be nearly $n·poly(k)$ .
One approach to creating such a large matrix is to compute the value of the game on the sub-matrix mapped to each entry and use that as the entry’s value. While this method ensures that the entry in the resulting matrix that maps to the optimal sub-matrix is a Pure Strategy Nash Equilibrium (PSNE)—an entry that is the smallest in its row and the largest in its column—it may not necessarily be a strict PSNE. However, if we are given a set of values $V$ that includes the value of the game $V_A^⋆$ , we can modify the previously constructed matrix to ensure that the PSNE becomes a strict PSNE. Our randomized algorithm for finding the strict PSNE has the additional advantage that, whenever the matrix contains a PSNE, it will, with high probability, compute a set that includes the value of the game $V_A^⋆$ .
Now, we describe how to make the PSNE that maps to the optimal sub-matrix (which we will refer to as the optimal PSNE) a strict PSNE. Consider an entry that is in the column of the optimal PSNE and has a value equal to $V_A^⋆$ . If this entry is not the optimal PSNE, using Lemma 1, we can show that the sub-matrix it maps to lacks a Nash equilibrium with all the rows in its support, although it does have a Nash equilibrium with all the columns in its support. Therefore, if we devise a method to decrease the values of all such entries by a very small amount $ε$ , the optimal PSNE will become strictly greater than all the entries in its column.
Although we do not know which column contains the optimal PSNE, we can decrease the values of entries by a very small amount $ε$ if the entry value is in the set $V$ , which includes $V_A^⋆$ , and the sub-matrix it maps to lacks a Nash equilibrium with all the rows in its support, but does have a Nash equilibrium with all the columns in its support. The values of entries corresponding to the optimal sub-matrix remain unchanged, as there exists a Nash equilibrium strategy with all rows and columns in its support. By modifying the entries in this way, we can ensure that the optimal PSNE is strictly larger than all other entries in its column. Similarly, we can make this PSNE strictly smaller than all other entries in its row. Note that while we modify other entries whose value is not equal to $V_A^⋆$ , we ensure that the relative ordering with respect to $V_A^⋆$ remains unchanged. Consequently, we implicitly construct a large matrix with a strict PSNE that maps to the optimal sub-matrix, and we can find this strict PSNE by querying nearly $n·poly(k)$ entries of $A$ .
In summary, our main innovative technique is to reduce the problem of finding the set of all Nash equilibria to finding a strict PSNE in a large matrix, and then to locate this strict PSNE in a query-efficient manner.
We also provide a simple lower bound to demonstrate that $k=\max\{k_1,k_2\}$ accurately captures the query complexity of the problem.
**Theorem 2**
*Let $A$ be any randomized algorithm that correctly computes the set of all Nash equilibria $X_⋆×Y_⋆$ . Let $τ(M)$ denote the number of entries queried from the matrix $M$ by $A$ . Then, there exists an input matrix $A∈ℝ^n× n$ with $\max\{k_1,k_2\}=k$ and $\min\{k_1,k_2\}=1$ such that $E[τ(A)]≥\frac{(n-1)(k+1)}{2}$ , where the randomness in $τ(A)$ is due to $A$ only.*
This result is not surprising, as changing the elements in the rows $\bigcup\limits_x∈X_⋆\operatorname*{supp}(x)$ and columns $\bigcup\limits_y∈Y_⋆\operatorname*{supp}(y)$ can alter the set of all Nash equilibria, making it necessary to observe them.
### 1.3 Related work
Unlike the computational complexity literature, which focuses on minimizing the number of computational steps for algorithms that compute equilibrium while knowing the payoffs, the works on query complexity consider a scenario where an algorithm aims to compute an equilibrium for a game without knowing the payoffs beforehand. The main focus of such works is to minimize the number of payoff queries used. We discuss some of these works here.
Query complexity of zero-sum games: Recently, there has been renewed interest in the topic of query complexity of zero-sum games. Under the assumption that input matrix $A∈\{0,1\}^n× n$ has a unique Nash equilibrium, Auger et al. [2] designed a randomized algorithm for finding the unique Nash equilibrium of $A$ by querying $O(n\log(n)· k^4k)$ entries of $A$ , where $k=|\operatorname*{supp}(x^⋆)|$ . Recall that for the special case when the input matrix has a strict PSNE, Bienstock et al. [5] presented a deterministic algorithm that finds the strict PSNE by querying $O(n)$ entries of the input matrix $A∈ℝ^n× n$ . Recently, Dallant et al. [10] improved this result by designing a deterministic algorithm that finds the strict PSNE in $O(n\log^*n)$ time by querying $O(n)$ entries of the input matrix $A∈ℝ^n× n$ . Parallel to our work, under the same special case, Dallant et al. [11] and Maiti et al. [21] designed randomized algorithms aimed at minimizing the time complexity and the statistical complexity (when the feedback on the payoff matrix is noisy) respectively.
Query complexity of general-sum games: The query complexity of finding various equilibrium concepts in games—including general-sum multi-player games—has been extensively studied; see the survey by Babichenko [4] for a comprehensive overview. For instance, Babichenko [3] demonstrated that the query complexity of computing an $ε$ -well-supported Nash equilibrium in an $n$ -player binary action game is $2^Ω(n)$ .
Fearnley et al. [18] showed that in an $n× n$ bimatrix game with payoffs in the range [0,1], a $\frac{1}{2}$ -approximate Nash equilibrium can be computed using at most $2n-1$ payoff queries. They complemented this result by showing that there is a constant $ε<\frac{1}{2}$ such that the query complexity of computing an $ε$ -approximate Nash equilibrium is more than $2n-1$ .
Goldberg and Roth [19] proved that for a game with $n$ players and $m$ actions, the query complexity of finding an $ε$ -approximate coarse correlated equilibrium is $O≤ft(\frac{nm\log m}{ε^2}\right)$ . A randomized algorithm was designed by Fearnley and Savani [17] that finds a $≤ft(\frac{3-√{5}}{2}+ε\right)$ -approximate Nash equilibrium in $n× n$ bimatrix games using $O≤ft(\frac{n\log n}{ε^2}\right)$ payoff queries. Later, Deligkas et al. [16] presented an algorithm that finds a $\frac{1}{2}+ε$ -well-supported Nash equilibrium in $n× n$ general-sum matrix games using $O≤ft(\frac{n\log n}{ε^4}\right)$ payoff queries.
### 1.4 Notation
We refer to the entry in the $i$ th row and $j$ th column of a matrix $M$ as entry $(i,j)$ of $M$ , and we denote its value by $M_i,j$ . Let $e_i$ denote the standard basis vector with the $i$ th entry equal to one and all other entries equal to zero. We use $1$ to represent the all-ones vector.
Let $[n]:=\{1,2,…,n\}$ , and let $\binom{[n]}{k_0}$ denote the set of all subsets of $[n]$ of size $k_0$ . For any $v∈ℝ^n$ , let $\operatorname*{supp}(v):=\{i∈[n]\mid v_i≠ 0\}$ denote the support of $v$ .
For any matrix $M∈ℝ^n× m$ , let $V_M^⋆:=\max_x∈\mathchoice{∈cludegraphics[height=4.2194pt,trim=0.0 pt 30.0pt 0.0pt 0.0pt]{graphics/simplex.pdf}{∈cludegraphics[height=4.2194pt ,trim=0.0pt 25.0pt 0.0pt 0.0pt]{graphics/simplex.pdf}}{∈cludegraphics[height =3.31529pt,trim=0.0pt 30.0pt 0.0pt 0.0pt]{graphics/simplex.pdf}}{ ∈cludegraphics[height=2.41112pt,trim=0.0pt 30.0pt 0.0pt 0.0pt]{graphics/ simplex.pdf}}_n}\min_y∈\mathchoice{∈cludegraphics[height=4.2194pt,trim= 0.0pt 30.0pt 0.0pt 0.0pt]{graphics/simplex.pdf}{∈cludegraphics[height=4.219 4pt,trim=0.0pt 25.0pt 0.0pt 0.0pt]{graphics/simplex.pdf}}{∈cludegraphics[hei ght=3.31529pt,trim=0.0pt 30.0pt 0.0pt 0.0pt]{graphics/simplex.pdf}}{ ∈cludegraphics[height=2.41112pt,trim=0.0pt 30.0pt 0.0pt 0.0pt]{graphics/ simplex.pdf}}_m}⟨ x,My⟩$ denote the value of the zero-sum game on matrix $M$ . We say an entry $(i_⋆,j_⋆)$ is a Pure Strategy Nash equilibrium (in short PSNE) of $M$ if $M_i,j_{⋆}≤ M_i_{⋆,j_⋆}≤ M_i_{⋆,j}$ for all $i≠ i_⋆,j≠ j_⋆$ . We say an entry $(i_⋆,j_⋆)$ is a strict PSNE of $M$ if $M_i,j_{⋆}<M_i_{⋆,j_⋆}<M_i_{⋆,j}$ for all $i≠ i_⋆,j≠ j_⋆$ .
Let $ℝ^I$ represent the space of all real-valued vectors indexed by the set of indices $I$ . The simplex over a set of indices $I$ , denoted $\mathchoice{∈cludegraphics[height=6.02773pt,trim=0.0pt 30.0pt 0.0pt 0.0pt]{ graphics/simplex.pdf}}{∈cludegraphics[height=6.02773pt,trim=0.0pt 25.0pt 0.0 pt 0.0pt]{graphics/simplex.pdf}}{∈cludegraphics[height=4.73611pt,trim=0.0pt 30.0pt 0.0pt 0.0pt]{graphics/simplex.pdf}}{∈cludegraphics[height=3.44444pt,t rim=0.0pt 30.0pt 0.0pt 0.0pt]{graphics/simplex.pdf}}_I$ , is defined as the set of vectors $x∈ℝ^I$ such that $∑_i∈Ix_i=1$ and $x_i≥ 0$ for all $i∈I$ .
For simplicity, we use $\log x$ to denote $\log_2x$ . Also for simplicity, unless otherwise noted, by number of entries queried, we mean the number of distinct entries queried.
Outline of the paper:
In Section 2, we discuss key properties of Nash equilibria. In Section 3, we present important technical lemmas that will be utilized throughout the paper. Section 4 introduces the randomized algorithm for finding strict PSNE, while Section 5 details the algorithm for finding the set of all Nash equilibria and provides a lower bound on query complexity.
## 2 Properties of Nash Equilibrium
We now state some properties of Nash equilibrium (see [20] and [6] for more details). Consider $A∈ℝ^n× n$ . The pair $(x_⋆,y_⋆)$ is a Nash equilibrium of $A$ if and only if the following hold simultaneously:
- The value of the game on $A$ satisfies $⟨ e_i,Ay_⋆⟩=V^⋆_A$ for any $i∈\operatorname*{supp}(x_⋆)$ and $⟨ x_⋆,Ae_j⟩=V^⋆_A$ for any $j∈\operatorname*{supp}(y_⋆)$ .
- The value of the game on $A$ satisfies $⟨ e_i,Ay_⋆⟩≤ V^⋆_A$ for any $i∉\operatorname*{supp}(x_⋆)$ and $⟨ x_⋆,Ae_j⟩≥ V^⋆_A$ for any $j∉\operatorname*{supp}(y_⋆)$ .
It is also easy to observe that $(x_⋆,y_⋆)$ is a Nash equilibrium of $A$ if and only if $⟨ x_⋆,Ay_⋆⟩=\max_i∈[n]⟨ e_i,Ay_⋆ ⟩=\min_j∈[n]⟨ x_⋆,Ae_j⟩$ . Now, recall that due to Von Neumann’s minimax theorem, we have
$$
V_A^⋆:=\max_x∈\mathchoice{∈cludegraphics[height=4.2194pt,trim=0.0
pt 30.0pt 0.0pt 0.0pt]{graphics/simplex.pdf}{∈cludegraphics[height=4.2194pt
,trim=0.0pt 25.0pt 0.0pt 0.0pt]{graphics/simplex.pdf}}{∈cludegraphics[height
=3.31529pt,trim=0.0pt 30.0pt 0.0pt 0.0pt]{graphics/simplex.pdf}}{
∈cludegraphics[height=2.41112pt,trim=0.0pt 30.0pt 0.0pt 0.0pt]{graphics/
simplex.pdf}}_n}\min_y∈\mathchoice{∈cludegraphics[height=4.2194pt,trim=
0.0pt 30.0pt 0.0pt 0.0pt]{graphics/simplex.pdf}{∈cludegraphics[height=4.219
4pt,trim=0.0pt 25.0pt 0.0pt 0.0pt]{graphics/simplex.pdf}}{∈cludegraphics[hei
ght=3.31529pt,trim=0.0pt 30.0pt 0.0pt 0.0pt]{graphics/simplex.pdf}}{
∈cludegraphics[height=2.41112pt,trim=0.0pt 30.0pt 0.0pt 0.0pt]{graphics/
simplex.pdf}}_n}⟨ x,Ay⟩=\min_y∈\mathchoice{∈cludegraphics[h
eight=4.2194pt,trim=0.0pt 30.0pt 0.0pt 0.0pt]{graphics/simplex.pdf}{
∈cludegraphics[height=4.2194pt,trim=0.0pt 25.0pt 0.0pt 0.0pt]{graphics/
simplex.pdf}}{∈cludegraphics[height=3.31529pt,trim=0.0pt 30.0pt 0.0pt 0.0pt]
{graphics/simplex.pdf}}{∈cludegraphics[height=2.41112pt,trim=0.0pt 30.0pt 0.
0pt 0.0pt]{graphics/simplex.pdf}}_n}\max_x∈\mathchoice{∈cludegraphics[h
eight=4.2194pt,trim=0.0pt 30.0pt 0.0pt 0.0pt]{graphics/simplex.pdf}{
∈cludegraphics[height=4.2194pt,trim=0.0pt 25.0pt 0.0pt 0.0pt]{graphics/
simplex.pdf}}{∈cludegraphics[height=3.31529pt,trim=0.0pt 30.0pt 0.0pt 0.0pt]
{graphics/simplex.pdf}}{∈cludegraphics[height=2.41112pt,trim=0.0pt 30.0pt 0.
0pt 0.0pt]{graphics/simplex.pdf}}_n}⟨ x,Ay⟩.
$$
Observe that this is also equivalent to
$$
V_A^⋆=\max_x∈\mathchoice{∈cludegraphics[height=4.2194pt,trim=0.0
pt 30.0pt 0.0pt 0.0pt]{graphics/simplex.pdf}{∈cludegraphics[height=4.2194pt
,trim=0.0pt 25.0pt 0.0pt 0.0pt]{graphics/simplex.pdf}}{∈cludegraphics[height
=3.31529pt,trim=0.0pt 30.0pt 0.0pt 0.0pt]{graphics/simplex.pdf}}{
∈cludegraphics[height=2.41112pt,trim=0.0pt 30.0pt 0.0pt 0.0pt]{graphics/
simplex.pdf}}_n}\min_j∈[n]⟨ x,Ae_j⟩=\min_y∈\mathchoice{
∈cludegraphics[height=4.2194pt,trim=0.0pt 30.0pt 0.0pt 0.0pt]{graphics/
simplex.pdf}{∈cludegraphics[height=4.2194pt,trim=0.0pt 25.0pt 0.0pt 0.0pt]{
graphics/simplex.pdf}}{∈cludegraphics[height=3.31529pt,trim=0.0pt 30.0pt 0.0
pt 0.0pt]{graphics/simplex.pdf}}{∈cludegraphics[height=2.41112pt,trim=0.0pt
30.0pt 0.0pt 0.0pt]{graphics/simplex.pdf}}_n}\max_i∈[n]⟨ e_i,Ay⟩.
$$
Also recall that $(x_⋆,y_⋆)$ is a Nash equilibrium of the matrix $A$ if and only if
$$
x_⋆∈X_⋆:=\arg\max_x∈\mathchoice{∈cludegraphics[he
ight=4.2194pt,trim=0.0pt 30.0pt 0.0pt 0.0pt]{graphics/simplex.pdf}{
∈cludegraphics[height=4.2194pt,trim=0.0pt 25.0pt 0.0pt 0.0pt]{graphics/
simplex.pdf}}{∈cludegraphics[height=3.31529pt,trim=0.0pt 30.0pt 0.0pt 0.0pt]
{graphics/simplex.pdf}}{∈cludegraphics[height=2.41112pt,trim=0.0pt 30.0pt 0.
0pt 0.0pt]{graphics/simplex.pdf}}_n}\min_y∈\mathchoice{∈cludegraphics[h
eight=4.2194pt,trim=0.0pt 30.0pt 0.0pt 0.0pt]{graphics/simplex.pdf}{
∈cludegraphics[height=4.2194pt,trim=0.0pt 25.0pt 0.0pt 0.0pt]{graphics/
simplex.pdf}}{∈cludegraphics[height=3.31529pt,trim=0.0pt 30.0pt 0.0pt 0.0pt]
{graphics/simplex.pdf}}{∈cludegraphics[height=2.41112pt,trim=0.0pt 30.0pt 0.
0pt 0.0pt]{graphics/simplex.pdf}}_n}⟨ x,Ay⟩ and y
_⋆∈Y_⋆:=\arg\min_y∈\mathchoice{∈cludegraphics[hei
ght=4.2194pt,trim=0.0pt 30.0pt 0.0pt 0.0pt]{graphics/simplex.pdf}{
∈cludegraphics[height=4.2194pt,trim=0.0pt 25.0pt 0.0pt 0.0pt]{graphics/
simplex.pdf}}{∈cludegraphics[height=3.31529pt,trim=0.0pt 30.0pt 0.0pt 0.0pt]
{graphics/simplex.pdf}}{∈cludegraphics[height=2.41112pt,trim=0.0pt 30.0pt 0.
0pt 0.0pt]{graphics/simplex.pdf}}_n}\max_x∈\mathchoice{∈cludegraphics[h
eight=4.2194pt,trim=0.0pt 30.0pt 0.0pt 0.0pt]{graphics/simplex.pdf}{
∈cludegraphics[height=4.2194pt,trim=0.0pt 25.0pt 0.0pt 0.0pt]{graphics/
simplex.pdf}}{∈cludegraphics[height=3.31529pt,trim=0.0pt 30.0pt 0.0pt 0.0pt]
{graphics/simplex.pdf}}{∈cludegraphics[height=2.41112pt,trim=0.0pt 30.0pt 0.
0pt 0.0pt]{graphics/simplex.pdf}}_n}⟨ x,Ay⟩.
$$
This implies that if there are strategies $x_⋆,y_⋆∈\mathchoice{∈cludegraphics[height=6.02773pt,trim=0.0pt 30.0pt 0.0pt 0.0pt]{graphics/simplex.pdf}}{∈cludegraphics[height=6.02773pt, trim=0.0pt 25.0pt 0.0pt 0.0pt]{graphics/simplex.pdf}}{∈cludegraphics[height= 4.73611pt,trim=0.0pt 30.0pt 0.0pt 0.0pt]{graphics/simplex.pdf}}{ ∈cludegraphics[height=3.44444pt,trim=0.0pt 30.0pt 0.0pt 0.0pt]{graphics/ simplex.pdf}}_n$ such that $\min_y∈\mathchoice{∈cludegraphics[height=4.2194pt,trim=0.0pt 30.0pt 0.0pt 0.0pt]{graphics/simplex.pdf}{∈cludegraphics[height=4.2194pt,trim=0.0pt 25. 0pt 0.0pt 0.0pt]{graphics/simplex.pdf}}{∈cludegraphics[height=3.31529pt,trim =0.0pt 30.0pt 0.0pt 0.0pt]{graphics/simplex.pdf}}{∈cludegraphics[height=2.41 112pt,trim=0.0pt 30.0pt 0.0pt 0.0pt]{graphics/simplex.pdf}}_n}⟨ x_ ⋆,Ay⟩=V_A^⋆$ and $\max_x∈\mathchoice{∈cludegraphics[height=4.2194pt,trim=0.0pt 30.0pt 0.0pt 0.0pt]{graphics/simplex.pdf}{∈cludegraphics[height=4.2194pt,trim=0.0pt 25. 0pt 0.0pt 0.0pt]{graphics/simplex.pdf}}{∈cludegraphics[height=3.31529pt,trim =0.0pt 30.0pt 0.0pt 0.0pt]{graphics/simplex.pdf}}{∈cludegraphics[height=2.41 112pt,trim=0.0pt 30.0pt 0.0pt 0.0pt]{graphics/simplex.pdf}}_n}⟨ x,Ay_ ⋆⟩=V_A^⋆$ , then $x_⋆∈X_⋆$ and $y_⋆∈Y_⋆$ . Also, convex combination of multiple Nash equilibria is a Nash equilibrium as $X_⋆,Y_⋆$ are compact convex sets.
The sets $X_⋆$ and $Y_⋆$ can be efficiently represented as the convex hulls of their extreme points, which are finite and non-zero in number. Let $E(X)$ denote the set of extreme points of a set $X$ . For any submatrix $\tilde{A}$ of $A$ , define $\tilde{x}$ and $\tilde{y}$ as the vectors formed by removing the components of $x$ and $y$ that correspond to the rows and columns missing from $\tilde{A}$ . The following lemma describes an important property of the extreme points of $X_⋆$ and $Y_⋆$ .
**Lemma 2 (Bohnenblust et al. [6])**
*A Nash equilibrium $(x_⋆,y_⋆)$ of $A$ is in the set $E(X_⋆)×E(Y_⋆)$ if and only if there is a square sub-matrix $\tilde{A}$ of $A$ such that
$$
\tilde{x}^⊤_⋆=\frac{1^⊤adj(\tilde{A})}{1^
⊤adj(\tilde{A})1}, \tilde{y}_⋆=\frac{adj(\tilde{A})\mathbf
{1}}{1^⊤adj(\tilde{A})1}, V_A^⋆=\frac{det(
\tilde{A})}{1^⊤adj(\tilde{A})1}
$$*
It is easy to observe that we can compute all the extreme points of $X_⋆$ and $Y_⋆$ by examining all the square submatrices $\tilde{A}$ of the input matrix $A$ and applying the above lemma. Let $I_x=\{j∈[n]:V_A^⋆=⟨ x,Ae_j⟩\}$ and $I_y=\{i∈[n]:V_A^⋆=⟨ e_i,Ay⟩\}$ . Since the sets $X_⋆$ and $Y_⋆$ are the convex hulls of $E(X_⋆)$ and $E(Y_⋆)$ , we have $\bigcup\limits_x_{⋆∈X_⋆}\operatorname*{supp}(x_⋆ )=\bigcup\limits_x_{⋆∈E(X_⋆)}\operatorname*{ supp}(x_⋆)$ , $\bigcup\limits_y_{⋆∈Y_⋆}\operatorname*{supp}(y_⋆ )=\bigcup\limits_y_{⋆∈E(Y_⋆)}\operatorname*{ supp}(y_⋆)$ , $\bigcap\limits_x_{⋆∈X_⋆}I_x=\bigcap\limits_x_{⋆ ∈E(X_⋆)}I_x$ , and $\bigcap\limits_y_{⋆∈Y_⋆}I_y=\bigcap\limits_y_{⋆ ∈E(Y_⋆)}I_y$ . This fact allows us to verify conditions involving $I_x$ , $I_y$ , and the union of supports, which is critical to our algorithm in later sections.
## 3 Technical Lemmas for Nash Equilibrium
Recall that for the input matrix $A∈ℝ^n× n$ , $X_⋆:=\arg\max_x∈\mathchoice{∈cludegraphics[height=4.2194 pt,trim=0.0pt 30.0pt 0.0pt 0.0pt]{graphics/simplex.pdf}{∈cludegraphics[heig ht=4.2194pt,trim=0.0pt 25.0pt 0.0pt 0.0pt]{graphics/simplex.pdf}}{ ∈cludegraphics[height=3.31529pt,trim=0.0pt 30.0pt 0.0pt 0.0pt]{graphics/ simplex.pdf}}{∈cludegraphics[height=2.41112pt,trim=0.0pt 30.0pt 0.0pt 0.0pt] {graphics/simplex.pdf}}_n}\min_y∈\mathchoice{∈cludegraphics[height=4.21 94pt,trim=0.0pt 30.0pt 0.0pt 0.0pt]{graphics/simplex.pdf}{∈cludegraphics[he ight=4.2194pt,trim=0.0pt 25.0pt 0.0pt 0.0pt]{graphics/simplex.pdf}}{ ∈cludegraphics[height=3.31529pt,trim=0.0pt 30.0pt 0.0pt 0.0pt]{graphics/ simplex.pdf}}{∈cludegraphics[height=2.41112pt,trim=0.0pt 30.0pt 0.0pt 0.0pt] {graphics/simplex.pdf}}_n}⟨ x,Ay⟩$ and $Y_⋆:=\arg\min_y∈\mathchoice{∈cludegraphics[height=4.2194 pt,trim=0.0pt 30.0pt 0.0pt 0.0pt]{graphics/simplex.pdf}{∈cludegraphics[heig ht=4.2194pt,trim=0.0pt 25.0pt 0.0pt 0.0pt]{graphics/simplex.pdf}}{ ∈cludegraphics[height=3.31529pt,trim=0.0pt 30.0pt 0.0pt 0.0pt]{graphics/ simplex.pdf}}{∈cludegraphics[height=2.41112pt,trim=0.0pt 30.0pt 0.0pt 0.0pt] {graphics/simplex.pdf}}_n}\max_x∈\mathchoice{∈cludegraphics[height=4.21 94pt,trim=0.0pt 30.0pt 0.0pt 0.0pt]{graphics/simplex.pdf}{∈cludegraphics[he ight=4.2194pt,trim=0.0pt 25.0pt 0.0pt 0.0pt]{graphics/simplex.pdf}}{ ∈cludegraphics[height=3.31529pt,trim=0.0pt 30.0pt 0.0pt 0.0pt]{graphics/ simplex.pdf}}{∈cludegraphics[height=2.41112pt,trim=0.0pt 30.0pt 0.0pt 0.0pt] {graphics/simplex.pdf}}_n}⟨ x,Ay⟩$ . Also recall that $\mathchoice{∈cludegraphics[height=6.02773pt,trim=0.0pt 30.0pt 0.0pt 0.0pt]{ graphics/simplex.pdf}}{∈cludegraphics[height=6.02773pt,trim=0.0pt 25.0pt 0.0 pt 0.0pt]{graphics/simplex.pdf}}{∈cludegraphics[height=4.73611pt,trim=0.0pt 30.0pt 0.0pt 0.0pt]{graphics/simplex.pdf}}{∈cludegraphics[height=3.44444pt,t rim=0.0pt 30.0pt 0.0pt 0.0pt]{graphics/simplex.pdf}}_I$ represents the simplex over a set of indices $I$ . For any vector $v$ and the set of indices $S=\{i_1,…,i_\ell\}$ , let $v_S$ denote the vector $(v_i_1,…,v_i_{\ell})$ . We now state an important lemma that provides the necessary and sufficient condition for a subset of rows and columns to be optimal.
**Lemma 3**
*Let $I$ and $J$ be two subsets of $[n]$ . Let $M_1$ be the submatrix of $A$ with row indices $I$ and column indices $[n]$ , and $M_2$ be the submatrix of $A$ with row indices $[n]$ and column indices $J$ . Let $X_M_1:=\arg\max_x∈\mathchoice{∈cludegraphics[height=4.2194 pt,trim=0.0pt 30.0pt 0.0pt 0.0pt]{graphics/simplex.pdf}{∈cludegraphics[heig ht=4.2194pt,trim=0.0pt 25.0pt 0.0pt 0.0pt]{graphics/simplex.pdf}}{ ∈cludegraphics[height=3.31529pt,trim=0.0pt 30.0pt 0.0pt 0.0pt]{graphics/ simplex.pdf}}{∈cludegraphics[height=2.41112pt,trim=0.0pt 30.0pt 0.0pt 0.0pt] {graphics/simplex.pdf}}_I}\min_y∈\mathchoice{∈cludegraphics[h eight=4.2194pt,trim=0.0pt 30.0pt 0.0pt 0.0pt]{graphics/simplex.pdf}{ ∈cludegraphics[height=4.2194pt,trim=0.0pt 25.0pt 0.0pt 0.0pt]{graphics/ simplex.pdf}}{∈cludegraphics[height=3.31529pt,trim=0.0pt 30.0pt 0.0pt 0.0pt] {graphics/simplex.pdf}}{∈cludegraphics[height=2.41112pt,trim=0.0pt 30.0pt 0. 0pt 0.0pt]{graphics/simplex.pdf}}_n}⟨ x,M_1y⟩$ and $Y_M_2:=\arg\min_y∈\mathchoice{∈cludegraphics[height=4.2194 pt,trim=0.0pt 30.0pt 0.0pt 0.0pt]{graphics/simplex.pdf}{∈cludegraphics[heig ht=4.2194pt,trim=0.0pt 25.0pt 0.0pt 0.0pt]{graphics/simplex.pdf}}{ ∈cludegraphics[height=3.31529pt,trim=0.0pt 30.0pt 0.0pt 0.0pt]{graphics/ simplex.pdf}}{∈cludegraphics[height=2.41112pt,trim=0.0pt 30.0pt 0.0pt 0.0pt] {graphics/simplex.pdf}}_J}\max_x∈\mathchoice{∈cludegraphics[h eight=4.2194pt,trim=0.0pt 30.0pt 0.0pt 0.0pt]{graphics/simplex.pdf}{ ∈cludegraphics[height=4.2194pt,trim=0.0pt 25.0pt 0.0pt 0.0pt]{graphics/ simplex.pdf}}{∈cludegraphics[height=3.31529pt,trim=0.0pt 30.0pt 0.0pt 0.0pt] {graphics/simplex.pdf}}{∈cludegraphics[height=2.41112pt,trim=0.0pt 30.0pt 0. 0pt 0.0pt]{graphics/simplex.pdf}}_n}⟨ x,M_2y⟩$ . Let $X_A:=\{x∈\mathchoice{∈cludegraphics[height=6.02773pt,trim=0.0 pt 30.0pt 0.0pt 0.0pt]{graphics/simplex.pdf}}{∈cludegraphics[height=6.02773 pt,trim=0.0pt 25.0pt 0.0pt 0.0pt]{graphics/simplex.pdf}}{∈cludegraphics[heig ht=4.73611pt,trim=0.0pt 30.0pt 0.0pt 0.0pt]{graphics/simplex.pdf}}{ ∈cludegraphics[height=3.44444pt,trim=0.0pt 30.0pt 0.0pt 0.0pt]{graphics/ simplex.pdf}}_n:x_I∈X_M_1\}$ and $Y_A:=\{y∈\mathchoice{∈cludegraphics[height=6.02773pt,trim=0.0 pt 30.0pt 0.0pt 0.0pt]{graphics/simplex.pdf}}{∈cludegraphics[height=6.02773 pt,trim=0.0pt 25.0pt 0.0pt 0.0pt]{graphics/simplex.pdf}}{∈cludegraphics[heig ht=4.73611pt,trim=0.0pt 30.0pt 0.0pt 0.0pt]{graphics/simplex.pdf}}{ ∈cludegraphics[height=3.44444pt,trim=0.0pt 30.0pt 0.0pt 0.0pt]{graphics/ simplex.pdf}}_n:y_J∈Y_M_2\}$ . The following holds:
1. If $I=\bigcup\limits_x∈X_⋆\operatorname*{supp}(x)$ and $J=\bigcup\limits_y∈Y_⋆\operatorname*{supp}(y)$ , then the following holds:
- $X_A=X_⋆$ and $Y_A=Y_⋆$
- $V_M_1^⋆=V_A^⋆$ and $\bigcap\limits_x∈X_AI_x=J$ where $I_x=\{j∈[n]:V_A^⋆=⟨ x,Ae_j⟩\}$ .
- $V_M_2^⋆=V_A^⋆$ and $\bigcap\limits_y∈Y_AI_y=I$ where $I_y=\{i∈[n]:V_A^⋆=⟨ e_i,Ay⟩\}$ .
1. Let $I_x^\prime=\{j∈[n]:V_M_1^⋆=⟨ x,Ae_j⟩\}$ and $I_y^\prime=\{i∈[n]:V_M_2^⋆=⟨ e_i,Ay⟩\}$ . If $V_M_1^⋆=V_M_2^⋆$ , $\bigcap\limits_x∈X_AI_x^\prime=J$ and $\bigcap\limits_y∈Y_AI_y^\prime=I$ then $X_A=X_⋆$ and $Y_A=Y_⋆$ .*
* Proof*
Let us assume that $I=\bigcup\limits_x∈X_⋆\operatorname*{supp}(x)$ and $J=\bigcup\limits_y∈Y_⋆\operatorname*{supp}(y)$ . First consider $\hat{x}∈X_A$ . Observe that $\operatorname*{supp}(\hat{x})⊆I$ . Now observe that $V_M_1^⋆=\min_y∈\mathchoice{∈cludegraphics[height=4.2194pt,trim= 0.0pt 30.0pt 0.0pt 0.0pt]{graphics/simplex.pdf}{∈cludegraphics[height=4.219 4pt,trim=0.0pt 25.0pt 0.0pt 0.0pt]{graphics/simplex.pdf}}{∈cludegraphics[hei ght=3.31529pt,trim=0.0pt 30.0pt 0.0pt 0.0pt]{graphics/simplex.pdf}}{ ∈cludegraphics[height=2.41112pt,trim=0.0pt 30.0pt 0.0pt 0.0pt]{graphics/ simplex.pdf}}_n}⟨\hat{x},Ay⟩≤\max_x∈\mathchoice{ ∈cludegraphics[height=4.2194pt,trim=0.0pt 30.0pt 0.0pt 0.0pt]{graphics/ simplex.pdf}{∈cludegraphics[height=4.2194pt,trim=0.0pt 25.0pt 0.0pt 0.0pt]{ graphics/simplex.pdf}}{∈cludegraphics[height=3.31529pt,trim=0.0pt 30.0pt 0.0 pt 0.0pt]{graphics/simplex.pdf}}{∈cludegraphics[height=2.41112pt,trim=0.0pt 30.0pt 0.0pt 0.0pt]{graphics/simplex.pdf}}_n}\min_y∈\mathchoice{ ∈cludegraphics[height=4.2194pt,trim=0.0pt 30.0pt 0.0pt 0.0pt]{graphics/ simplex.pdf}{∈cludegraphics[height=4.2194pt,trim=0.0pt 25.0pt 0.0pt 0.0pt]{ graphics/simplex.pdf}}{∈cludegraphics[height=3.31529pt,trim=0.0pt 30.0pt 0.0 pt 0.0pt]{graphics/simplex.pdf}}{∈cludegraphics[height=2.41112pt,trim=0.0pt 30.0pt 0.0pt 0.0pt]{graphics/simplex.pdf}}_n}⟨ x,Ay⟩=V_A^⋆$ . Next consider $x^⋆∈X_⋆$ . Observe that $\operatorname*{supp}(x^⋆)⊆I$ . Now observe that $V_A^⋆=\min_y∈\mathchoice{∈cludegraphics[height=4.2194pt,trim=0.0 pt 30.0pt 0.0pt 0.0pt]{graphics/simplex.pdf}{∈cludegraphics[height=4.2194pt ,trim=0.0pt 25.0pt 0.0pt 0.0pt]{graphics/simplex.pdf}}{∈cludegraphics[height =3.31529pt,trim=0.0pt 30.0pt 0.0pt 0.0pt]{graphics/simplex.pdf}}{ ∈cludegraphics[height=2.41112pt,trim=0.0pt 30.0pt 0.0pt 0.0pt]{graphics/ simplex.pdf}}_n}⟨ x^⋆_I,M_1y⟩≤\max_x∈ \mathchoice{∈cludegraphics[height=4.2194pt,trim=0.0pt 30.0pt 0.0pt 0.0pt]{ graphics/simplex.pdf}{∈cludegraphics[height=4.2194pt,trim=0.0pt 25.0pt 0.0 pt 0.0pt]{graphics/simplex.pdf}}{∈cludegraphics[height=3.31529pt,trim=0.0pt 30.0pt 0.0pt 0.0pt]{graphics/simplex.pdf}}{∈cludegraphics[height=2.41112pt,t rim=0.0pt 30.0pt 0.0pt 0.0pt]{graphics/simplex.pdf}}_I}\min_y∈ \mathchoice{∈cludegraphics[height=4.2194pt,trim=0.0pt 30.0pt 0.0pt 0.0pt]{ graphics/simplex.pdf}{∈cludegraphics[height=4.2194pt,trim=0.0pt 25.0pt 0.0 pt 0.0pt]{graphics/simplex.pdf}}{∈cludegraphics[height=3.31529pt,trim=0.0pt 30.0pt 0.0pt 0.0pt]{graphics/simplex.pdf}}{∈cludegraphics[height=2.41112pt,t rim=0.0pt 30.0pt 0.0pt 0.0pt]{graphics/simplex.pdf}}_n}⟨ x,M_1y ⟩=V_M_1^⋆$ . Hence, we have $V_A^⋆=V_M_1^⋆$ and therefore $\hat{x}∈X_⋆$ and $x^⋆∈X_A$ implying that $X_A=X_⋆$ . Analogously, one can show that $V_M_2^⋆=V_A^⋆$ and $Y_A=Y_⋆$ . Due to Lemma 1, we get that $\bigcap\limits_x∈X_AI_x=\bigcap\limits_x∈X_ ⋆I_x=\bigcup\limits_y∈Y_⋆\operatorname*{supp}(y)= J$ and $\bigcap\limits_y∈Y_AI_y=\bigcap\limits_y∈Y_ ⋆I_y=\bigcup\limits_x∈X_⋆\operatorname*{supp}(x)= I$ . Next let us assume that $V_M_1^⋆=V_M_2^⋆$ , $\bigcap\limits_x∈X_AI_x^\prime=J$ and $\bigcap\limits_y∈Y_AI_y^\prime=I$ . Consider $\hat{x}∈X_A$ and $\hat{y}∈Y_A$ . Observe that $\operatorname*{supp}(\hat{x})⊆I$ and $\operatorname*{supp}(\hat{y})⊆J$ . Now observe that $⟨\hat{x},A\hat{y}⟩≥\min_y∈\mathchoice{∈cludegraphics[heigh t=4.2194pt,trim=0.0pt 30.0pt 0.0pt 0.0pt]{graphics/simplex.pdf}{ ∈cludegraphics[height=4.2194pt,trim=0.0pt 25.0pt 0.0pt 0.0pt]{graphics/ simplex.pdf}}{∈cludegraphics[height=3.31529pt,trim=0.0pt 30.0pt 0.0pt 0.0pt] {graphics/simplex.pdf}}{∈cludegraphics[height=2.41112pt,trim=0.0pt 30.0pt 0. 0pt 0.0pt]{graphics/simplex.pdf}}_n}⟨\hat{x},Ay⟩=V_M_1^⋆$ . Next observe that $⟨\hat{x},A\hat{y}⟩≤\max_x∈\mathchoice{∈cludegraphics[heigh t=4.2194pt,trim=0.0pt 30.0pt 0.0pt 0.0pt]{graphics/simplex.pdf}{ ∈cludegraphics[height=4.2194pt,trim=0.0pt 25.0pt 0.0pt 0.0pt]{graphics/ simplex.pdf}}{∈cludegraphics[height=3.31529pt,trim=0.0pt 30.0pt 0.0pt 0.0pt] {graphics/simplex.pdf}}{∈cludegraphics[height=2.41112pt,trim=0.0pt 30.0pt 0. 0pt 0.0pt]{graphics/simplex.pdf}}_n}⟨ x,A\hat{y}⟩=V_M_2^⋆$ . Since $V_M_1^⋆=V_M_2^⋆$ , we have $⟨\hat{x},A\hat{y}⟩=V_M_1^⋆=V_M_2^⋆$ . This implies that $⟨\hat{x},A\hat{y}⟩=V_M_2^⋆=\max_x∈\mathchoice{ ∈cludegraphics[height=4.2194pt,trim=0.0pt 30.0pt 0.0pt 0.0pt]{graphics/ simplex.pdf}{∈cludegraphics[height=4.2194pt,trim=0.0pt 25.0pt 0.0pt 0.0pt]{ graphics/simplex.pdf}}{∈cludegraphics[height=3.31529pt,trim=0.0pt 30.0pt 0.0 pt 0.0pt]{graphics/simplex.pdf}}{∈cludegraphics[height=2.41112pt,trim=0.0pt 30.0pt 0.0pt 0.0pt]{graphics/simplex.pdf}}_n}⟨ x,A\hat{y}⟩$ and $⟨\hat{x},A\hat{y}⟩=V_M_1^⋆=\min_y∈\mathchoice{ ∈cludegraphics[height=4.2194pt,trim=0.0pt 30.0pt 0.0pt 0.0pt]{graphics/ simplex.pdf}{∈cludegraphics[height=4.2194pt,trim=0.0pt 25.0pt 0.0pt 0.0pt]{ graphics/simplex.pdf}}{∈cludegraphics[height=3.31529pt,trim=0.0pt 30.0pt 0.0 pt 0.0pt]{graphics/simplex.pdf}}{∈cludegraphics[height=2.41112pt,trim=0.0pt 30.0pt 0.0pt 0.0pt]{graphics/simplex.pdf}}_n}⟨\hat{x},Ay⟩$ . Hence $(\hat{x},\hat{y})$ is a Nash equilibrium of $A$ and $V_A^⋆=⟨\hat{x},A\hat{y}⟩=V_M_1^⋆=V_M_2^⋆$ . This implies that $X_A⊆X_⋆$ and $Y_A⊆Y_⋆$ . Consider $x^⋆∈X_⋆$ . Due to Lemma 1, we have $\operatorname*{supp}(x^⋆)⊆\bigcap\limits_y∈Y_⋆ I_y⊆\bigcap\limits_y∈Y_AI_y^\prime=I$ . Now we have $\min_y∈\mathchoice{∈cludegraphics[height=4.2194pt,trim=0.0pt 30.0pt 0.0pt 0.0pt]{graphics/simplex.pdf}{∈cludegraphics[height=4.2194pt,trim=0.0pt 25. 0pt 0.0pt 0.0pt]{graphics/simplex.pdf}}{∈cludegraphics[height=3.31529pt,trim =0.0pt 30.0pt 0.0pt 0.0pt]{graphics/simplex.pdf}}{∈cludegraphics[height=2.41 112pt,trim=0.0pt 30.0pt 0.0pt 0.0pt]{graphics/simplex.pdf}}_n}⟨ x^ ⋆_I,M_1y⟩=\min_y∈\mathchoice{∈cludegraphics[heig ht=4.2194pt,trim=0.0pt 30.0pt 0.0pt 0.0pt]{graphics/simplex.pdf}{ ∈cludegraphics[height=4.2194pt,trim=0.0pt 25.0pt 0.0pt 0.0pt]{graphics/ simplex.pdf}}{∈cludegraphics[height=3.31529pt,trim=0.0pt 30.0pt 0.0pt 0.0pt] {graphics/simplex.pdf}}{∈cludegraphics[height=2.41112pt,trim=0.0pt 30.0pt 0. 0pt 0.0pt]{graphics/simplex.pdf}}_n}⟨ x^⋆,Ay⟩=V_A^⋆ =V_M_1^⋆$ . Hence, $x^⋆_I∈X_M_1$ which implies $X_⋆⊆X_A$ . Analogously, one can show that $Y_⋆⊆Y_A$ . Hence, we have $X_A=X_⋆$ and $Y_A=Y_⋆$ . ∎
The following lemma states that a matrix can have at most one strict PSNE.
**Lemma 4**
*Any matrix $M∈ℝ^n× m$ can have at most one strict PSNE.*
* Proof*
Consider a matrix $M$ with a strict PSNE at $(i_⋆,j_⋆)$ . Since $(i_⋆,j_⋆)$ is a strict PSNE, we have $M_i,j_{⋆}<M_i_{⋆,j}$ for all $(i,j)≠(i_⋆,j_⋆)$ . Suppose there is another entry $(i^\prime,j^\prime)≠(i_⋆,j_⋆)$ that is also a strict PSNE. Since $(i^\prime,j^\prime)$ is a PSNE, we would have $M_i_{⋆,j^\prime}≤ M_i^\prime,j^{\prime}≤ M_i^\prime,j_ ⋆$ . However, this contradicts the inequality $M_i^\prime,j_⋆<M_i_{⋆,j^\prime}$ . Therefore, the matrix $M$ cannot have more than one strict PSNE. ∎
## 4 An important subroutine for PSNE
A key part of our algorithm for finding the set of all Nash equilibria is a query-efficient subroutine for a matrix $M∈ℝ^n× m$ that has a PSNE and potentially a strict PSNE. Moreover, we assume that we have access to the matrix $M$ through a query oracle $Q$ which operates as follows:
- A single call to query oracle $Q$ with input $(row,i)$ returns the entire $i$ -th row of $M$ .
- A single call to query oracle $Q$ with input $(column,j)$ returns the entire $j$ -th column of $M$ .
In this section, we work with a matrix $M∈ℝ^n× m$ and we aim to achieve the following goals by making $O(\log^2(n+m))$ calls to the query oracle $Q$ :
- If the matrix $M$ has a PSNE, we construct a set of distinct real numbers that contains $V_M^⋆$ with high probability.
- If the matrix $M$ has a strict PSNE, we find the strict PSNE with high probability.
### 4.1 A Randomized Algorithm to Find the Strict PSNE
In this section, we assume that the input matrix $M∈ℝ^n× m$ has a strict PSNE $(i_⋆,j_⋆)$ . By definition, we have that $M_i,j_{⋆}<M_i_{⋆,j_⋆}<M_i_{⋆,j}$ for all $i∈[n]∖\{i_⋆\}$ and $j∈[m]∖\{j_⋆\}$ . We use this crucial fact to design a randomized algorithm, FindPsne (Algorithm 1), for finding the strict PSNE.
We first describe our procedure, FindPsne, intuitively. The procedure progresses through a logarithmic number of stages. In each stage, it aims to eliminate half of the sub-optimal rows and columns. At any given stage where the goal is to eliminate half of the sub-optimal rows, we begin by sampling a logarithmic number of row indices and querying all entries in each sampled row. Next, we examine the highest values among the queried entries in each column and select the column $\widehat{j}$ with the lowest of these values. We then sample all entries in column $\widehat{j}$ and remove rows where the corresponding entries in the column $\widehat{j}$ are below the median value of that column. An analogous process exists to eliminate half of the sub-optimal columns. This process of sampling, querying, and reducing the search space continues until only one row and one column remain, which together form the strict PSNE. For a formal description of the procedure FindPsne, please refer to Algorithm 1.
1 $n←$ number of rows of $M$ , $m←$ number of columns of $M$ , $X_1←[n],\>Y_1←[m],\>V_1←∅$
2 for $t=1,2,…$ do
3 if $|X_t|=1$ and $|Y_t|=1$ then
4 $V←V_t∪\{M_\widehat{i,\widehat{j}}\}$ , where $X_t=\{ \widehat{i} \}$ and $Y_t=\{ \widehat{j} \}$
5 return $( \widehat{i},\>\widehat{j} )$ and $V$
6 if $|X_t|=1$ then
7 Query all the elements of row $\widehat{i}$ , where $X_t=\{ \widehat{i} \}$
8 Choose the argument $\widehat{j}∈\operatorname*{arg min}_j∈Y_tM_\widehat{i,j}$ and set $V←V_t∪\{M_\widehat{i,\widehat{j}}\}$
9 return $( \widehat{i},\>\widehat{j} )$ and $V$
10 if $|Y_t|=1$ then
11 Query all the elements of column $\widehat{j}$ , where $Y_t=\{ \widehat{j} \}$
12 Choose the argument $\widehat{i}∈\operatorname*{arg max}_i∈X_tM_i,\widehat{j}$ and set $V←V_t∪\{M_\widehat{i,\widehat{j}}\}$
13 return $( \widehat{i},\>\widehat{j} )$ and $V$
14 $n_t←|X_t|$ , $m_t←|Y_t|$ and $\ell←≤ft\lceil 2\log≤ft(\frac{2(n+m)^2}{δ}\right)\right\rceil$
15 $\overline{X}_t←\{x_1,x_2,…,x_\ell\}$ ; $x_i$ ’s are drawn independently and uniformly at random from $X_t$
16 $\overline{Y}_t←\{y_1,y_2,…,y_\ell\}$ ; $y_j$ ’s are drawn independently and uniformly at random from $Y_t$
17 Query all the entries of $M$ in $\{(i,j):i∈X_t,j∈\overline{Y}_t\}∪\{(i,j):i∈\overline{X} _t,j∈Y_t\}$
18
19 Choose the arguments $\widehat{i}∈\operatorname*{arg max}_i∈X_t\min_j∈ \overline{Y_t}M_i,j$ and $\widehat{j}∈\operatorname*{arg min}_j∈Y_t\max_i∈ \overline{X_t}M_i,j$
20 $V_t+1←V_t∪\{\max_i∈X_t\min _j∈\overline{Y_t}M_i,j,\min_j∈Y_t\max_i∈\overline{X _t}M_i,j\}$
21 Query all the entries of $M$ in $\{({i,\widehat{j}}):i∈X_t\}∪\{({\widehat{i},\>j}):j∈ Y_t\}$
22
23 $X_t+1←\{i_1,i_2,…,i_\lfloor n_{t/2\rfloor}\} ⊆X_t=\{i_1,…,i_n_{t}\}$ , where $M_i_{1,\widehat{j}}≥ M_i_{2,\widehat{j}}≥…≥ M_i_{n_{t}, \widehat{j}}$
24 $Y_t+1←\{j_1,j_2,…,j_\lfloor m_{t/2\rfloor}\} ⊆Y_t=\{j_1,…,j_m_{t}\}$ , where $M_\widehat{i,j_1}≤ M_\widehat{i,j_2}≤…≤ M_\widehat{i,j _m_{t}}$
25
Algorithm 1 FindPsne ( $M,δ$ )
We now begin the analysis of Algorithm 1 with the following proposition.
**Proposition 1**
*Fix $c,k∈ℕ$ with $k≥ 2$ . Consider a set $S=\{a_1,a_2,…,a_k\}$ , and let $S_1=\{a_1,a_2,…,a_\lfloor k/2\rfloor\}$ . Let $\ell=\lceil 2\log(\frac{c}{δ})\rceil$ , and let $X=\{x_1,x_2,…,x_\ell\}$ where $x_i$ ’s are drawn independently and uniformly at random from $S$ . Then, $X∩ S_1≠∅$ with probability at least $1-\frac{δ}{c}$ .*
* Proof*
As the events $\{x_i∉ S_1\}$ are independent,
$$
\displaystyleℙ(X∩ S_1=∅)=∏_i=1^\ellℙ(x_
{i}∉ S_1)=≤ft\lparen\tfrac{k-\lfloor k/2\rfloor}{k}\right\rparen^
\ell≤≤ft\lparen\tfrac{2}{3}\right\rparen^2\log(\frac{c{δ})}<≤ft
\lparen\tfrac{1}{2}\right\rparen^\log(\frac{c{δ})}=\tfrac{δ}{c}. \tag{23}
$$
∎
We now establish the query complexity of FindPsne in the following lemma.
**Lemma 5**
*FindPsne $(A,δ)$ can be executed by calling the query oracle $Q$ at most $O(\log(n+m)·\log(\frac{n+m}{δ}))$ times.*
* Proof*
Observe that the algorithm terminates at a fixed iteration $t_⋆$ which is at most $\min\{\log(n),\log(m)\}+1$ . In each iteration $t<t_⋆$ , line 1 requires at most $2\ell$ calls to the query oracle $Q$ and line 1 requires two calls to the query oracle $Q$ . Final iteration $t_⋆$ requires at most one call to the query oracle $Q$ . Hence, FindPsne $(A,δ)$ can be executed by calling the query oracle $Q$ at most $O(\log(n+m)·\log(\frac{n+m}{δ}))$ times. ∎
Finally, we establish the correctness of FindPsne in the following lemma.
**Lemma 6**
*If $M$ has a strict PSNE, then FindPsne $(M,δ)$ returns the strict PSNE with probability at least $1-δ$ .*
* Proof*
Let $(i_⋆,j_⋆)$ be the strict PSNE of $M$ . Consider an iteration $t$ such that $\min\{|X_t|,|Y_t|\}≥ 2$ . Let us assume that $i_⋆∈X_t$ and $j_⋆∈Y_t$ . Under this assumption, we will show that $i_⋆∈X_t+1$ and $j_⋆∈Y_t+1$ with probability at least $1-\frac{δ}{n+m}$ . For each $j∈Y_t$ , let us relabel the indices in $X_t$ as $\{i_1,i_2,…,i_n_{t}\}$ such that $M_i_{1,j}≥ M_i_{2,j}≥…≥ M_i_{n_{t},j}$ and define $R_t,j:=\{i_1,i_2,…,i_\lfloor n_{t/2\rfloor}\}$ . Recall that $\overline{X}_t$ is a random subset of $X_t$ . By Proposition 1 we have $ℙ(\overline{X}_t∩R_t,j≠∅)≥ 1-\frac{ δ}{2(n+m)^2}$ for a fixed $j$ . By the union bound, we then have that with probability at least $1-\frac{δ}{2(n+m)}$ , the event $E_t:=\{\overline{X}_t∩R_t,j≠∅\>∀ \>j∈Y_t\}$ holds. Note that if $E_t$ holds, for each $j∈Y_t$ we have $\operatorname*{arg max}_i∈\overline{X_t}M_i,j∩R_t,j≠∅$ . Assume $E_t$ holds, and let $v^⋆_y=\min_j∈Y_t\max_i∈\overline{X_t}M_i,j$ . Recall that $\widehat{j}∈\arg\min_j∈Y_t\max_i∈\overline{X_t}M_i,j$ . If $\widehat{j}=j_⋆$ , then $i_⋆∈R_t,\widehat{j}=X_t+1$ , as $M_i_{⋆,j_⋆}$ is the unique highest element of column $j_⋆$ . Next, let us consider the case where $\widehat{j}≠ j_⋆$ . As $E_t$ holds, $\operatorname*{arg max}_i∈\overline{X_t}M_i,\widehat{j}∩R _t,\widehat{j}≠∅$ . We also see that $v^⋆_y=\min_j∈Y_t\max_i∈\overline{X_t}M_i,j≤ \max_i∈\overline{X_t}M_i,j_{⋆}≤ M_i_{⋆,j_⋆}$ . Recall that for all $j∈Y_t∖\{j_⋆\}$ , we have $M_i_{⋆,j}>M_i_{⋆,j_⋆}$ . Now for all $i∈X_t∖R_t,\widehat{j}$ , we have $M_i,\widehat{j}≤ v_y^⋆≤ M_i_{⋆,j_⋆}<M_i_{⋆, \widehat{j}}$ . Hence, $i_⋆∈R_t,\widehat{j}=X_t+1$ . By an identical argument, we have $j_⋆∈Y_t+1$ with probability at least $1-\frac{δ}{2(n+m)}$ . Hence, by the union bound, with probability at least $1-\frac{δ}{n+m}$ we have $i_⋆∈X_t+1$ and $j_⋆∈Y_t+1$ . Observe that the algorithm terminates at a fixed iteration $t_⋆$ which is at most $\min\{\log(n),\log(m)\}+1$ . Now observe that FindPsne $(M,δ)$ returns $(i_⋆,j_⋆)$ if $i_⋆∈X_t_{⋆}$ and $j_⋆∈Y_t_{⋆}$ as by definition the entry $(i_⋆,j_⋆)$ is the unique least element in the row $i_⋆$ and unique highest element in the column $j_⋆$ . Let $p_t=ℙ(i_⋆∈X_t,j_⋆∈Y_t|i_ ⋆∈X_t-1,j_⋆∈Y_t-1)$ . Now we have the following due to the chain rule and Bernoulli’s inequality,
$$
ℙ(i_⋆∈X_t_{⋆},j_⋆∈Y_t_{
⋆})=∏_t=2^t_⋆p_t≥≤ft(1-\frac{δ}{n+m}\right)^t_
{⋆}≥ 1-δ.
$$
∎
### 4.2 Important property of FindPsne for Non-Strict PSNE
Let us assume we are given an input matrix $M$ with a PSNE $(i_⋆,j_⋆)$ . By definition, we have $M_i,j_{⋆}≤ M_i_{⋆,j_⋆}≤ M_i_{⋆,j}$ for all $i∈[n]∖\{i_⋆\}$ and $j∈[m]∖\{j_⋆\}$ . In the following lemma, we state an important property of FindPsne, applicable even when the PSNE is not strict.
**Lemma 7**
*Consider an input matrix $M$ which has a PSNE $(i_⋆,j_⋆)$ . With probability at least $1-δ$ , $\textsc{FindPsne}(M,δ)$ returns a set $V$ of distinct real numbers such that $V_M^⋆∈V$ .*
* Proof*
Let $(i_⋆,j_⋆)$ be a PSNE of $M$ . Observe that the algorithm terminates at a fixed iteration $t_⋆$ which is at most $\min\{\log(n),\log(m)\}+1$ . Consider an iteration $t<t_⋆$ . Let us assume that $i_⋆∈X_t$ and $j_⋆∈Y_t$ . Under this assumption, we will show that with probability at least $1-\frac{δ}{n+m}$ either $i_⋆∈X_t+1$ and $j_⋆∈Y_t+1$ or $V_M^⋆∈V_t+1$ . For each $j∈Y_t$ , let us relabel the indices in $X_t$ as $\{i_1,i_2,…,i_n_{t}\}$ such that $M_i_{1,j}≥ M_i_{2,j}≥…≥ M_i_{n_{t},j}$ and define $R_t,j:=\{i_1,i_2,…,i_\lfloor n_{t/2\rfloor}\}$ . Recall that $\overline{X}_t$ is a random subset of $X_t$ . By Proposition 1 we have $ℙ(\overline{X}_t∩R_t,j≠∅)≥ 1-\frac{ δ}{2(n+m)^2}$ for a fixed $j$ . By the union bound, we then have that with probability at least $1-\frac{δ}{2(n+m)}$ , the event $E_t:=\{\overline{X}_t∩R_t,j≠∅\>∀ \>j∈Y_t\}$ holds. Note that if $E_t$ holds, for each $j∈Y_t$ we have $\operatorname*{arg max}_i∈\overline{X_t}M_i,j∩R_t,j≠∅$ . Assume $E_t$ holds, and let $v^⋆_y=\min_j∈Y_t\max_i∈\overline{X_t}M_i,j$ . Recall that $\widehat{j}∈\arg\min_j∈Y_t\max_i∈\overline{X_t}M_i,j$ . As $E_t$ holds, $\operatorname*{arg max}_i∈\overline{X_t}M_i,\widehat{j}∩R _t,\widehat{j}≠∅$ . We also see that $v^⋆_y=\min_j∈Y_t\max_i∈\overline{X_t}M_i,j≤ \max_i∈\overline{X_t}M_i,j_{⋆}≤ M_i_{⋆,j_⋆}=V_M^⋆$ . If $v^⋆_y=V_M^⋆$ , then $V_M^⋆∈V_t+1$ as $\min_j∈Y_t\max_i∈\overline{X_t}M_i,j$ is added to $V_t$ to create $V_t+1$ . Recall that for all $j∈Y_t$ , we have $M_i_{⋆,j}≥ M_i_{⋆,j_⋆}$ . Now if $v^⋆_y<V_M^⋆$ , then for all $i∈X_t∖R_t,\widehat{j}$ , we have $M_i,\widehat{j}≤ v_y^⋆<M_i_{⋆,j_⋆}≤ M_i_{⋆, \widehat{j}}$ . Hence, in this case we have $i_⋆∈R_t,\widehat{j}=X_t+1$ . By an identical argument, with probability at least $1-\frac{δ}{2(n+m)}$ , either $j_⋆∈Y_t+1$ or $V_M^⋆∈V_t+1$ . Hence, by the union bound, with probability at least $1-\frac{δ}{n+m}$ , either $i_⋆∈X_t+1$ and $j_⋆∈Y_t+1$ or $V_M^⋆∈V_t+1$ . For the last iteration $t_⋆$ , if $i_⋆∈X_t_{⋆}$ and $j_⋆∈Y_t_{⋆}$ , then $V_M^⋆∈V$ as the entry $(i_⋆,j_⋆)$ is the highest element of column $j_⋆$ and the least element of row $i_⋆$ . Let $p_t=ℙ(i_⋆∈X_t and j_⋆∈Y _t or V_M^⋆∈V_t|i_⋆∈X_t-1 and j_⋆∈Y_t-1 or V_M^⋆∈V _t-1)$ . Now we have the following due to the chain rule and Bernoulli’s inequality,
$$
ℙ(V_M^⋆∈V)=∏_t=2^t_⋆p_t≥≤ft(
1-\frac{δ}{n+m}\right)^t_⋆≥ 1-δ.
$$
∎
## 5 Results for finding the set of all Nash equilibria
Consider an input matrix $A∈ℝ^n× n$ . Recall that $X_⋆:=\arg\max_x∈\mathchoice{∈cludegraphics[height=4.2194 pt,trim=0.0pt 30.0pt 0.0pt 0.0pt]{graphics/simplex.pdf}{∈cludegraphics[heig ht=4.2194pt,trim=0.0pt 25.0pt 0.0pt 0.0pt]{graphics/simplex.pdf}}{ ∈cludegraphics[height=3.31529pt,trim=0.0pt 30.0pt 0.0pt 0.0pt]{graphics/ simplex.pdf}}{∈cludegraphics[height=2.41112pt,trim=0.0pt 30.0pt 0.0pt 0.0pt] {graphics/simplex.pdf}}_n}\min_y∈\mathchoice{∈cludegraphics[height=4.21 94pt,trim=0.0pt 30.0pt 0.0pt 0.0pt]{graphics/simplex.pdf}{∈cludegraphics[he ight=4.2194pt,trim=0.0pt 25.0pt 0.0pt 0.0pt]{graphics/simplex.pdf}}{ ∈cludegraphics[height=3.31529pt,trim=0.0pt 30.0pt 0.0pt 0.0pt]{graphics/ simplex.pdf}}{∈cludegraphics[height=2.41112pt,trim=0.0pt 30.0pt 0.0pt 0.0pt] {graphics/simplex.pdf}}_n}⟨ x,Ay⟩$ , $Y_⋆:=\arg\min_y∈\mathchoice{∈cludegraphics[height=4.2194 pt,trim=0.0pt 30.0pt 0.0pt 0.0pt]{graphics/simplex.pdf}{∈cludegraphics[heig ht=4.2194pt,trim=0.0pt 25.0pt 0.0pt 0.0pt]{graphics/simplex.pdf}}{ ∈cludegraphics[height=3.31529pt,trim=0.0pt 30.0pt 0.0pt 0.0pt]{graphics/ simplex.pdf}}{∈cludegraphics[height=2.41112pt,trim=0.0pt 30.0pt 0.0pt 0.0pt] {graphics/simplex.pdf}}_n}\max_x∈\mathchoice{∈cludegraphics[height=4.21 94pt,trim=0.0pt 30.0pt 0.0pt 0.0pt]{graphics/simplex.pdf}{∈cludegraphics[he ight=4.2194pt,trim=0.0pt 25.0pt 0.0pt 0.0pt]{graphics/simplex.pdf}}{ ∈cludegraphics[height=3.31529pt,trim=0.0pt 30.0pt 0.0pt 0.0pt]{graphics/ simplex.pdf}}{∈cludegraphics[height=2.41112pt,trim=0.0pt 30.0pt 0.0pt 0.0pt] {graphics/simplex.pdf}}_n}⟨ x,Ay⟩$ , $k_1:=|\bigcup\limits_x∈X_⋆\operatorname*{supp}(x)|$ , $k_2:=|\bigcup\limits_y∈Y_⋆\operatorname*{supp}(y)|$ , and $k:=\max\{k_1,k_2\}$ . First, in Section 5.1, we design an algorithm that requires nearly $n·poly(k)$ queries to identify $X_⋆$ and $Y_⋆$ with high probability. We complement this result by showing in Section 5.2 that $Ω(nk)$ queries are required in expectation to identify $X_⋆$ and $Y_⋆$ even when $\min\{k_1,k_2\}=1$ .
### 5.1 Randomized Algorithm
We begin with restating our main result. See 1
Here is the outline of our randomized algorithm. We begin by designing a randomized procedure called SetV in Section 5.1.1, which takes the values $k_1$ and $k_2$ as input and finds a set $V$ of value of the game candidates that includes $V_A^⋆$ . Next, we design a randomized procedure called Nash in Section 5.1.2 that also takes the values $k_1$ and $k_2$ as input, calls the procedure SetV, constructs a high dimensional matrix and finds its strict PSNE which maps to $X_⋆×Y_⋆$ . Finally, as we show in Section 5.1.3, it is straightforward to relax the assumptions on knowing $k_1$ and $k_2$ by sequentially trying all possible combinations, starting from $k_1=1$ and $k_2=1$ , and stopping when we identify $X_⋆×Y_⋆$ . Throughout this process, we use the procedure FindPsne to either find the strict PSNE or compute the set $V$ using appropriate query oracles, ensuring that the query complexity remains nearly $n·poly(k)$ .
#### 5.1.1 Finding the value of the game candidates with the knowledge of $k_1$ and $k_2$
This section involves three key steps: defining a large matrix, defining the query oracle, and identifying a set $V$ of value of the game candidates.
We begin by assuming that we know the values $k_1:=|\bigcup\limits_x∈X_⋆\operatorname*{supp}(x)|$ and $k_2:=|\bigcup\limits_y∈Y_⋆\operatorname*{supp}(y)|$ . Let $A∈ℝ^n× n$ be the input matrix. We construct a matrix $A^(k_1,k_2)∈ℝ^\binom{n{k_1}×\binom{n}{k_2}}$ as follows. First, we consider two bijections $f_1:[\binom{n}{k_1}]→\binom{[n]}{k_1}$ and $f_2:[\binom{n}{k_2}]→\binom{[n]}{k_2}$ . Next, we consider indices $i∈[\binom{n}{k_1}]$ and $j∈[\binom{n}{k_2}]$ . Let $M$ be the submatrix of $A$ with row indices $f_1(i)$ and column indices $f_2(j)$ . We now define $A_i,j^(k_1,k_2):=V_M^⋆$ . Now we prove the following lemma.
**Lemma 8**
*Let $i_⋆:=f_1^-1(\bigcup\limits_x∈X_⋆\operatorname*{ supp}(x))$ and $j_⋆:=f_2^-1(\bigcup\limits_y∈Y_⋆\operatorname*{ supp}(y))$ . Then $(i_⋆,j_⋆)$ is a PSNE of $A^(k_1,k_2)$ and $A^(k_1,k_2)_i_{⋆,j_⋆}=V_A^⋆$ .*
* Proof*
For the sake of simplicity in presentation, let $\widehat{A}$ denote the matrix $A^(k_1,k_2)$ . Recall that $\mathchoice{∈cludegraphics[height=6.02773pt,trim=0.0pt 30.0pt 0.0pt 0.0pt]{ graphics/simplex.pdf}}{∈cludegraphics[height=6.02773pt,trim=0.0pt 25.0pt 0.0 pt 0.0pt]{graphics/simplex.pdf}}{∈cludegraphics[height=4.73611pt,trim=0.0pt 30.0pt 0.0pt 0.0pt]{graphics/simplex.pdf}}{∈cludegraphics[height=3.44444pt,t rim=0.0pt 30.0pt 0.0pt 0.0pt]{graphics/simplex.pdf}}_I$ represents the simplex over a set of indices $I$ . Let $(x_⋆,y_⋆)$ be a Nash equilibrium of $A$ such that $\operatorname*{supp}(x_⋆)=\bigcup\limits_x∈X_⋆ \operatorname*{supp}(x)$ and $\operatorname*{supp}(y_⋆)=\bigcup\limits_y∈Y_⋆ \operatorname*{supp}(y)$ . Such an equilibrium exists due to the fact that convex combination of multiple Nash equilibria is also a Nash equilibrium. Let $\widehat{x}∈\mathchoice{∈cludegraphics[height=6.02773pt,trim=0.0pt 30.0pt 0.0pt 0.0pt]{graphics/simplex.pdf}}{∈cludegraphics[height=6.02773pt,trim=0.0 pt 25.0pt 0.0pt 0.0pt]{graphics/simplex.pdf}}{∈cludegraphics[height=4.73611 pt,trim=0.0pt 30.0pt 0.0pt 0.0pt]{graphics/simplex.pdf}}{∈cludegraphics[heig ht=3.44444pt,trim=0.0pt 30.0pt 0.0pt 0.0pt]{graphics/simplex.pdf}}_f_{1(i_ ⋆)},\widehat{y}∈\mathchoice{∈cludegraphics[height=6.02773pt,trim=0.0 pt 30.0pt 0.0pt 0.0pt]{graphics/simplex.pdf}}{∈cludegraphics[height=6.02773 pt,trim=0.0pt 25.0pt 0.0pt 0.0pt]{graphics/simplex.pdf}}{∈cludegraphics[heig ht=4.73611pt,trim=0.0pt 30.0pt 0.0pt 0.0pt]{graphics/simplex.pdf}}{ ∈cludegraphics[height=3.44444pt,trim=0.0pt 30.0pt 0.0pt 0.0pt]{graphics/ simplex.pdf}}_f_{2(j_⋆)}$ be strategies such that for all $i∈ f_1(i_⋆)$ we have $\widehat{x}_i=(x_⋆)_i$ and for all $j∈ f_2(j_⋆)$ we have $\widehat{y}_j=(y_⋆)_j$ . First we claim that $\widehat{A}_i_{⋆,j_⋆}=V_A^⋆$ . Consider the submatrix $M$ of $A$ with row indices $f_1(i_⋆)$ and column indices $f_2(j_⋆)$ . As $(x_⋆,y_⋆)$ is a Nash equilibrium of $A$ , and $\operatorname*{supp}(x_⋆)=f_1(i_⋆)$ and $\operatorname*{supp}(y_⋆)=f_2(j_⋆)$ , we have $⟨ x,M\widehat{y}⟩=V_A^⋆$ for all $x∈\mathchoice{∈cludegraphics[height=6.02773pt,trim=0.0pt 30.0pt 0.0pt 0.0 pt]{graphics/simplex.pdf}}{∈cludegraphics[height=6.02773pt,trim=0.0pt 25.0pt 0.0pt 0.0pt]{graphics/simplex.pdf}}{∈cludegraphics[height=4.73611pt,trim=0. 0pt 30.0pt 0.0pt 0.0pt]{graphics/simplex.pdf}}{∈cludegraphics[height=3.44444 pt,trim=0.0pt 30.0pt 0.0pt 0.0pt]{graphics/simplex.pdf}}_f_{1(i_⋆)}$ and $⟨\widehat{x},My⟩=V_A^⋆$ for all $y∈\mathchoice{∈cludegraphics[height=6.02773pt,trim=0.0pt 30.0pt 0.0pt 0.0 pt]{graphics/simplex.pdf}}{∈cludegraphics[height=6.02773pt,trim=0.0pt 25.0pt 0.0pt 0.0pt]{graphics/simplex.pdf}}{∈cludegraphics[height=4.73611pt,trim=0. 0pt 30.0pt 0.0pt 0.0pt]{graphics/simplex.pdf}}{∈cludegraphics[height=3.44444 pt,trim=0.0pt 30.0pt 0.0pt 0.0pt]{graphics/simplex.pdf}}_f_{2(j_⋆)}$ . Hence $(\widehat{x},\widehat{y})$ is the Nash equilibrium of $M$ which implies that $\widehat{A}_i_{⋆,j_⋆}=V_M^⋆=⟨\widehat{x},M\widehat{y }⟩=V_A^⋆$ . Next consider an index $i∈[\binom{n}{k_1}]$ . Now we claim that $\widehat{A}_i,j_{⋆}≤ V_A^⋆$ . Consider the submatrix $M$ of $A$ with row indices $f_1(i)$ and column indices $f_2(j_⋆)$ . Now we have the following:
$$
\widehat{A}_i,j_{⋆}=V_M^⋆=\min_y∈\mathchoice{∈cludegraphics
[height=4.2194pt,trim=0.0pt 30.0pt 0.0pt 0.0pt]{graphics/simplex.pdf}{
∈cludegraphics[height=4.2194pt,trim=0.0pt 25.0pt 0.0pt 0.0pt]{graphics/
simplex.pdf}}{∈cludegraphics[height=3.31529pt,trim=0.0pt 30.0pt 0.0pt 0.0pt]
{graphics/simplex.pdf}}{∈cludegraphics[height=2.41112pt,trim=0.0pt 30.0pt 0.
0pt 0.0pt]{graphics/simplex.pdf}}_f_{2(j_⋆)}}\max_i∈ f_{1(i)}
⟨ e_i,My⟩≤\max_i∈ f_{1(i)}⟨ e_i,M\widehat{y}
⟩≤ V_A^⋆.
$$
The last inequality follows from the definition of $\widehat{y}$ and the fact that $\max_i∈[n]⟨ e_i,Ay_⋆⟩=V_A^⋆$ . Similarly we can show that for any $j∈[\binom{n}{k_2}]$ , we have $\widehat{A}_i_{⋆,j}≥ V_A^⋆$ . Hence, $(i_⋆,j_⋆)$ is a PSNE. ∎
Now we describe the query oracle to observe the rows and columns of $A^(k_1,k_2)$ .
Query oracle $Q$ to observe row $\hat{i}$ and column $\hat{j}$ of $A^(k_1,k_2)$ : Recall that $A^(k_1,k_2)_i,j$ only depends on the entries in the submatrix $M$ with row indices $f_1(i)$ and column indices $f_2(j)$ . Hence, if we want to observe the values in the set $\{A^(k_1,k_2)_\hat{i,j}:j∈\{1,2,…,\binom{n}{k_2}\}\}$ , then it suffices to query the entries of $A$ from the set $S_1=\{(i,j):i∈ f_1(\hat{i}),j∈[n]\}$ . Since $|f_1(\hat{i})|=k_1$ , we have that $|S_1|=k_1· n$ . Analogously, if we want to observe the values in the set $\{A^(k_1,k_2)_i,\hat{j}:i∈\{1,2,…,\binom{n}{k_1}\}\}$ , then it suffices to query the entries of $A$ from the set $S_2=\{(i,j):i∈[n],j∈ f_2(\hat{j})\}$ . Since $|f_2(\hat{j})|=k_2$ , we have $|S_2|=k_2· n$ .
Now we describe SetV, a randomized algorithm that aims to find a set $V$ that includes $V_A^⋆$ .
Description of the randomized procedure SetV $(A,δ,k_1,k_2)$ : Let $A∈ℝ^n× n$ be the input matrix. Recall the construction of the matrix $A^(k_1,k_2)∈ℝ^\binom{n{k_1}×\binom{n}{k_2}}$ from above. We now call the procedure FindPsne ( $A^(k_1,k_2),δ$ ), where we use the query oracle $Q$ to observe a row or column of $A^(k_1,k_2)$ . Let $V$ be the set of values returned by FindPsne ( $A^(k_1,k_2),δ$ ). We return the set $V$ .
Now, we prove the following lemma regarding the procedure SetV.
**Lemma 9**
*Consider a matrix game $A∈ℝ^n× n$ . Now we have the following:
- The procedure SetV $(A,δ,k_1,k_2)$ queries at most $O(nk^3·\log n·\log(\frac{n}{δ}))$ entries of $A$ .
- With probability at least $1-δ$ , the procedure SetV $(A,δ,k_1,k_2)$ returns a set $V$ of distinct real numbers such that $V_A^⋆∈V$ .*
* Proof*
Due to Lemma 5, the number of calls made by FindPsne ( $A^(k_1,k_2),δ$ ) to the query oracle $Q$ is at most $O(\log(n^k)·\log(\frac{n^k}{δ}))≤ O(k^2·\log(n)·\log (\frac{n}{δ}))$ . Each call to the query oracle $Q$ takes $O(nk)$ queries from the input matrix $A$ . Hence, the procedure FindPsne ( $A^(k_1,k_2),δ$ ) queries at most $O(nk^3·\log n·\log(\frac{n}{δ}))$ entries of $A$ and returns a set $V$ . Due to Lemmas 7 and 8, with probability at least $1-δ$ , $V_A^⋆∈V$ . ∎
#### 5.1.2 Algorithm for finding all Nash equilibria with the knowledge of $k_1$ and $k_2$
This section involves three key steps: modifying the large matrix from the previous section, defining the query oracle, and identifying the set of all Nash equilibria.
We begin by assuming that we know the values $k_1:=|\bigcup\limits_x∈X_⋆\operatorname*{supp}(x)|$ and $k_2:=|\bigcup\limits_y∈Y_⋆\operatorname*{supp}(y)|$ . Let $A∈ℝ^n× n$ be the input matrix. Let $V$ be a set of distinct real numbers. Recall that $\mathchoice{∈cludegraphics[height=6.02773pt,trim=0.0pt 30.0pt 0.0pt 0.0pt]{ graphics/simplex.pdf}}{∈cludegraphics[height=6.02773pt,trim=0.0pt 25.0pt 0.0 pt 0.0pt]{graphics/simplex.pdf}}{∈cludegraphics[height=4.73611pt,trim=0.0pt 30.0pt 0.0pt 0.0pt]{graphics/simplex.pdf}}{∈cludegraphics[height=3.44444pt,t rim=0.0pt 30.0pt 0.0pt 0.0pt]{graphics/simplex.pdf}}_I$ represents the simplex over a set of indices $I$ . We construct a matrix $A^(k_1,k_2,V)∈ℝ^\binom{n{k_1}×\binom{n}{k_ {2}}}$ as follows. First, we consider two bijections $f_1:[\binom{n}{k_1}]→\binom{[n]}{k_1}$ and $f_2:[\binom{n}{k_2}]→\binom{[n]}{k_2}$ . Next, we consider indices $i∈[\binom{n}{k_1}]$ and $j∈[\binom{n}{k_2}]$ . Let $M$ be the submatrix of $A$ with row indices $f_1(i)$ and column indices $f_2(j)$ . Let $X_M:=\arg\max_x∈\mathchoice{∈cludegraphics[height=4.2194pt,tr im=0.0pt 30.0pt 0.0pt 0.0pt]{graphics/simplex.pdf}{∈cludegraphics[height=4. 2194pt,trim=0.0pt 25.0pt 0.0pt 0.0pt]{graphics/simplex.pdf}}{∈cludegraphics[ height=3.31529pt,trim=0.0pt 30.0pt 0.0pt 0.0pt]{graphics/simplex.pdf}}{ ∈cludegraphics[height=2.41112pt,trim=0.0pt 30.0pt 0.0pt 0.0pt]{graphics/ simplex.pdf}}_f_{1(i)}}\min_y∈\mathchoice{∈cludegraphics[height=4.2194 pt,trim=0.0pt 30.0pt 0.0pt 0.0pt]{graphics/simplex.pdf}{∈cludegraphics[heig ht=4.2194pt,trim=0.0pt 25.0pt 0.0pt 0.0pt]{graphics/simplex.pdf}}{ ∈cludegraphics[height=3.31529pt,trim=0.0pt 30.0pt 0.0pt 0.0pt]{graphics/ simplex.pdf}}{∈cludegraphics[height=2.41112pt,trim=0.0pt 30.0pt 0.0pt 0.0pt] {graphics/simplex.pdf}}_f_{2(j)}}⟨ x,My⟩$ and $Y_M:=\arg\min_y∈\mathchoice{∈cludegraphics[height=4.2194pt,tr im=0.0pt 30.0pt 0.0pt 0.0pt]{graphics/simplex.pdf}{∈cludegraphics[height=4. 2194pt,trim=0.0pt 25.0pt 0.0pt 0.0pt]{graphics/simplex.pdf}}{∈cludegraphics[ height=3.31529pt,trim=0.0pt 30.0pt 0.0pt 0.0pt]{graphics/simplex.pdf}}{ ∈cludegraphics[height=2.41112pt,trim=0.0pt 30.0pt 0.0pt 0.0pt]{graphics/ simplex.pdf}}_f_{2(j)}}\max_x∈\mathchoice{∈cludegraphics[height=4.2194 pt,trim=0.0pt 30.0pt 0.0pt 0.0pt]{graphics/simplex.pdf}{∈cludegraphics[heig ht=4.2194pt,trim=0.0pt 25.0pt 0.0pt 0.0pt]{graphics/simplex.pdf}}{ ∈cludegraphics[height=3.31529pt,trim=0.0pt 30.0pt 0.0pt 0.0pt]{graphics/ simplex.pdf}}{∈cludegraphics[height=2.41112pt,trim=0.0pt 30.0pt 0.0pt 0.0pt] {graphics/simplex.pdf}}_f_{1(j)}}⟨ x,My⟩$ . Let $k_1,M:=|\bigcup\limits_x∈X_M\operatorname*{supp}(x)|$ and $k_2,M:=|\bigcup\limits_y∈Y_M\operatorname*{supp}(y)|$ . If $V_M^⋆∉V$ then we define $A_i,j^(k_1,k_2,V):=V_M^⋆$ . If $V_M^⋆∈V$ then we define $A_i,j^(k_1,k_2,V)$ as follows:
- If $k_1,M=k_1$ and $k_2,M=k_2$ then $A_i,j^(k_1,k_2,V)=V_M^⋆$
- If $k_1,M≠ k_1$ and $k_2,M≠ k_2$ then $A_i,j^(k_1,k_2,V)=V_M^⋆$
- If $k_1,M=k_1$ and $k_2,M≠ k_2$ then $A_i,j^(k_1,k_2,V)=V_M^⋆+\frac{ε}{4}$
- If $k_1,M≠ k_1$ and $k_2,M=k_2$ then $A_i,j^(k_1,k_2,V)=V_M^⋆-\frac{ε}{4}$
where $ε=\min\limits_v_{1,v_2∈V:v_1≠ v_2}|v_1-v_2|$ . If $|V|=1$ , then $ε=1$ . Now we prove the following lemma.
**Lemma 10**
*Let $i_⋆:=f_1^-1(\bigcup\limits_x∈X_⋆\operatorname*{ supp}(x))$ and $j_⋆:=f_2^-1(\bigcup\limits_y∈Y_⋆\operatorname*{ supp}(y))$ . If $V_A^⋆∈V$ , then $(i_⋆,j_⋆)$ is the only strict PSNE of $A^(k_1,k_2,V)$ .*
* Proof*
Let us assume that $V_A^⋆∈V$ . For the sake of simplicity in presentation, let $\widehat{A}$ denote the matrix $A^(k_1,k_2,V)$ . Now due to Lemma 4 it suffices to show that $\widehat{A}_i,j_{⋆}<\widehat{A}_i_{⋆,j_⋆}<\widehat{A}_i_{ ⋆,j}$ for all $i∈[\binom{n}{k_1}]∖\{i_⋆\}$ and $j∈[\binom{n}{k_2}]∖\{j_⋆\}$ . Let $(x_⋆,y_⋆)$ be a Nash equilibrium of $A$ such that the following holds:
- $\operatorname*{supp}(x_⋆)=\bigcup\limits_x∈X_⋆ \operatorname*{supp}(x)$ and $\operatorname*{supp}(y_⋆)=\bigcup\limits_y∈Y_⋆ \operatorname*{supp}(y)$
- For all $i∈\operatorname*{supp}(x_⋆)$ , we have $⟨ e_i,Ay_⋆⟩=V_A^⋆$ , and for all $i∉\operatorname*{supp}(x_⋆)$ , we have $⟨ e_i,Ay_⋆⟩<V_A^⋆$
- For all $j∈\operatorname*{supp}(y_⋆)$ , we have $⟨ x_⋆,Ae_j⟩=V_A^⋆$ , and for all $j∉\operatorname*{supp}(y_⋆)$ , we have $⟨ x_⋆,Ae_j⟩>V_A^⋆$
Such an equilibrium exists due to Lemma 1 and the fact that convex combination of multiple Nash equilibria is also a Nash equilibrium. Let $\widehat{x}∈\mathchoice{∈cludegraphics[height=6.02773pt,trim=0.0pt 30.0pt 0.0pt 0.0pt]{graphics/simplex.pdf}}{∈cludegraphics[height=6.02773pt,trim=0.0 pt 25.0pt 0.0pt 0.0pt]{graphics/simplex.pdf}}{∈cludegraphics[height=4.73611 pt,trim=0.0pt 30.0pt 0.0pt 0.0pt]{graphics/simplex.pdf}}{∈cludegraphics[heig ht=3.44444pt,trim=0.0pt 30.0pt 0.0pt 0.0pt]{graphics/simplex.pdf}}_f_{1(i_ ⋆)},\widehat{y}∈\mathchoice{∈cludegraphics[height=6.02773pt,trim=0.0 pt 30.0pt 0.0pt 0.0pt]{graphics/simplex.pdf}}{∈cludegraphics[height=6.02773 pt,trim=0.0pt 25.0pt 0.0pt 0.0pt]{graphics/simplex.pdf}}{∈cludegraphics[heig ht=4.73611pt,trim=0.0pt 30.0pt 0.0pt 0.0pt]{graphics/simplex.pdf}}{ ∈cludegraphics[height=3.44444pt,trim=0.0pt 30.0pt 0.0pt 0.0pt]{graphics/ simplex.pdf}}_f_{2(j_⋆)}$ be strategies such that for all $i∈ f_1(i_⋆)$ we have $\widehat{x}_i=(x_⋆)_i$ and for all $j∈ f_2(j_⋆)$ we have $\widehat{y}_j=(y_⋆)_j$ . First we claim that $\widehat{A}_i_{⋆,j_⋆}=V_A^⋆$ . Consider the submatrix $M$ of $A$ with row indices $f_1(i_⋆)$ and column indices $f_2(j_⋆)$ . As $\operatorname*{supp}(x_⋆)=f_1(i_⋆)$ and $\operatorname*{supp}(y_⋆)=f_2(j_⋆)$ , we have $⟨ x,M\widehat{y}⟩=V_A^⋆$ for all $x∈\mathchoice{∈cludegraphics[height=6.02773pt,trim=0.0pt 30.0pt 0.0pt 0.0 pt]{graphics/simplex.pdf}}{∈cludegraphics[height=6.02773pt,trim=0.0pt 25.0pt 0.0pt 0.0pt]{graphics/simplex.pdf}}{∈cludegraphics[height=4.73611pt,trim=0. 0pt 30.0pt 0.0pt 0.0pt]{graphics/simplex.pdf}}{∈cludegraphics[height=3.44444 pt,trim=0.0pt 30.0pt 0.0pt 0.0pt]{graphics/simplex.pdf}}_f_{1(i_⋆)}$ and $⟨\widehat{x},My⟩=V_A^⋆$ for all $y∈\mathchoice{∈cludegraphics[height=6.02773pt,trim=0.0pt 30.0pt 0.0pt 0.0 pt]{graphics/simplex.pdf}}{∈cludegraphics[height=6.02773pt,trim=0.0pt 25.0pt 0.0pt 0.0pt]{graphics/simplex.pdf}}{∈cludegraphics[height=4.73611pt,trim=0. 0pt 30.0pt 0.0pt 0.0pt]{graphics/simplex.pdf}}{∈cludegraphics[height=3.44444 pt,trim=0.0pt 30.0pt 0.0pt 0.0pt]{graphics/simplex.pdf}}_f_{2(j_⋆)}$ . Hence $(\widehat{x},\widehat{y})$ is the Nash equilibrium of $M$ which implies that $V_M^⋆=⟨\widehat{x},M\widehat{y}⟩=V_A^⋆$ . As $|\operatorname*{supp}(\widehat{x})|=k_1$ and $|\operatorname*{supp}(\widehat{y})|=k_2$ we have $\widehat{A}_i_{⋆,j_⋆}=V_A^⋆$ . Next consider an index $i∈[\binom{n}{k_1}]$ such that $f_1(i)∩ f_1(i_⋆)=∅$ . Now we claim that $\widehat{A}_i,j_{⋆}<V_A^⋆$ . Consider the submatrix $M$ of $A$ with row indices $f_1(i)$ and column indices $f_2(j_⋆)$ . Now we have the following:
$$
V_M^⋆=\min_y∈\mathchoice{∈cludegraphics[height=4.2194pt,trim=0.0
pt 30.0pt 0.0pt 0.0pt]{graphics/simplex.pdf}{∈cludegraphics[height=4.2194pt
,trim=0.0pt 25.0pt 0.0pt 0.0pt]{graphics/simplex.pdf}}{∈cludegraphics[height
=3.31529pt,trim=0.0pt 30.0pt 0.0pt 0.0pt]{graphics/simplex.pdf}}{
∈cludegraphics[height=2.41112pt,trim=0.0pt 30.0pt 0.0pt 0.0pt]{graphics/
simplex.pdf}}_f_{2(j_⋆)}}\max_i∈ f_{1(i)}⟨ e_i,My⟩
≤\max_i∈ f_{1(i)}⟨ e_i,M\widehat{y}⟩<V_A^⋆.
$$
The last inequality follows from our choice of $(x_⋆,y_⋆)$ above and $f_1(i)∩ f_1(i_⋆)=∅$ . If $V_M^⋆∉V$ , then $\widehat{A}_i,j_{⋆}=V_M^⋆<V_A^⋆$ . If $V_M^⋆∈V$ , then $\widehat{A}_i,j_{⋆}≤ V_M^⋆+\frac{ε}{4}<V_A^⋆$ . The last inequality follows from the definition $ε$ . Analogously, we can show that for any $j∈[\binom{n}{k_2}]$ such that $f_2(j)∩ f_2(j_⋆)=∅$ , we have $\widehat{A}_i_{⋆,j}>V_A^⋆$ . Next consider an index $i∈[\binom{n}{k_1}]∖\{i_⋆\}$ such that $f_1(i)∩ f_1(i_⋆)≠∅$ . Now we claim that $\widehat{A}_i,j_{⋆}<V_A^⋆$ . Consider the submatrix $M$ of $A$ with row indices $f_1(i)$ and column indices $f_2(j_⋆)$ . Now we have the following:
$$
V_M^⋆=\min_y∈\mathchoice{∈cludegraphics[height=4.2194pt,trim=0.0
pt 30.0pt 0.0pt 0.0pt]{graphics/simplex.pdf}{∈cludegraphics[height=4.2194pt
,trim=0.0pt 25.0pt 0.0pt 0.0pt]{graphics/simplex.pdf}}{∈cludegraphics[height
=3.31529pt,trim=0.0pt 30.0pt 0.0pt 0.0pt]{graphics/simplex.pdf}}{
∈cludegraphics[height=2.41112pt,trim=0.0pt 30.0pt 0.0pt 0.0pt]{graphics/
simplex.pdf}}_f_{2(j_⋆)}}\max_i∈ f_{1(i)}⟨ e_i,My⟩
≤\max_i∈ f_{1(i)}⟨ e_i,M\widehat{y}⟩=V_A^⋆.
$$
Recall the definition of $X_M,Y_M,k_1,M$ and $k_2,M$ . If $V_M^⋆<V_A^⋆$ and $V_M^⋆∉V$ , then we have $\widehat{A}_i,j_{⋆}=V_M^⋆<V_A^⋆$ . If $V_M^⋆<V_A^⋆$ and $V_M^⋆∈V$ , then we have $\widehat{A}_i,j_{⋆}≤ V_M^⋆+\frac{ε}{4}<V_A^⋆$ . Let us consider the case when $V_M^⋆=V_A^⋆$ . In this case, we have $\widehat{y}∈Y_M$ which implies that $k_2,M=k_2$ . Consider $x∈X_M$ . For any $i∉ f_1(i)∩ f_1(i_⋆)$ we have $⟨ e_i,M\widehat{y}⟩<V_A^⋆$ . This implies that $\operatorname*{supp}(x)⊆ f_1(i)∩ f_1(i_⋆)$ . As $x$ was chosen arbitrarily, we have $\bigcup\limits_x∈X_M\operatorname*{supp}(x)⊆ f_1(i) ∩ f_1(i_⋆)$ . As $f_1(i)≠ f_1(i_⋆)$ this implies $|f_1(i)∩ f_1(i_⋆)|<k_1$ . This implies that $k_1,M≠ k_1$ . Hence due to our construction, we have $\widehat{A}_i,j_{⋆}=V_A^⋆-\frac{ε}{4}<V_A^⋆$ . Analogously, we can show that for any $j∈[\binom{n}{k_2}]∖\{j_⋆\}$ such that $f_2(j)∩ f_2(j_⋆)≠∅$ , we have $\widehat{A}_i_{⋆,j}>V_A^⋆$ . Combining all the cases above, we have $\widehat{A}_i,j_{⋆}<\widehat{A}_i_{⋆,j_⋆}<\widehat{A}_i_{ ⋆,j}$ for all $i∈[\binom{n}{k_1}]∖\{i_⋆\}$ and $j∈[\binom{n}{k_2}]∖\{j_⋆\}$ . ∎
Now we describe the query oracle to observe the rows and columns of $A^(k_1,k_2,V)$ .
Query oracle $Q$ to observe row $\hat{i}$ and column $\hat{j}$ of $A^(k_1,k_2,V)$ : Recall that $A^(k_1,k_2,V)_i,j$ only depends on the set $V$ and the entries in the submatrix $M$ with row indices $f_1(i)$ and column indices $f_2(j)$ . Hence, if we want to observe the values in the set $\{A^(k_1,k_2,V)_\hat{i,j}:j∈\{1,2,…,\binom{n}{k_2}\}\}$ , then it suffices to query the entries of $A$ from the set $S_1=\{(i,j):i∈ f_1(\hat{i}),j∈[n]\}$ . Since $|f_1(\hat{i})|=k_1$ , we have that $|S_1|=k_1· n$ . Analogously, if we want to observe the values in the set $\{A^(k_1,k_2,V)_i,\hat{j}:i∈\{1,2,…,\binom{n}{k_1}\}\}$ , then it suffices to query the entries of $A$ from the set $S_2=\{(i,j):i∈[n],j∈ f_2(\hat{j})\}$ . Since $|f_2(\hat{j})|=k_2$ , we have $|S_2|=k_2· n$ .
Now we describe Nash, a randomized algorithm that finds $X_⋆$ and $Y_⋆$ when provided with the values $k_1$ and $k_2$ .
Description of the randomized procedure Nash $(A,δ,k_1,k_2)$ : Let $A∈ℝ^n× n$ be the input matrix. First, we call the procedure SetV $(A,δ/2,k_1,k_2)$ . Let $V$ be the set returned by this procedure. Recall the construction of the matrix $A^(k_1,k_2,V)∈ℝ^\binom{n{k_1}×\binom{n}{k_ {2}}}$ from above. We now call the procedure FindPsne ( $A^(k_1,k_2,V),δ/2$ ), where we use the query oracle $Q$ to observe a row or column of $A^(k_1,k_2,V)$ .
Let $(\hat{i},\hat{j})$ be the pair returned by the procedure FindPsne $(A^(k_1,k_2,V),δ/2)$ . Let $M_1$ be the submatrix of $A$ with row indices $f_1(\hat{i})$ and column indices $[n]$ , and $M_2$ be the submatrix of $A$ with row indices $[n]$ and column indices $f_2(\hat{j})$ . Let $X_M_1:=\arg\max_x∈\mathchoice{∈cludegraphics[height=4.2194 pt,trim=0.0pt 30.0pt 0.0pt 0.0pt]{graphics/simplex.pdf}{∈cludegraphics[heig ht=4.2194pt,trim=0.0pt 25.0pt 0.0pt 0.0pt]{graphics/simplex.pdf}}{ ∈cludegraphics[height=3.31529pt,trim=0.0pt 30.0pt 0.0pt 0.0pt]{graphics/ simplex.pdf}}{∈cludegraphics[height=2.41112pt,trim=0.0pt 30.0pt 0.0pt 0.0pt] {graphics/simplex.pdf}}_f_{1(\hat{i})}}\min_y∈\mathchoice{ ∈cludegraphics[height=4.2194pt,trim=0.0pt 30.0pt 0.0pt 0.0pt]{graphics/ simplex.pdf}{∈cludegraphics[height=4.2194pt,trim=0.0pt 25.0pt 0.0pt 0.0pt]{ graphics/simplex.pdf}}{∈cludegraphics[height=3.31529pt,trim=0.0pt 30.0pt 0.0 pt 0.0pt]{graphics/simplex.pdf}}{∈cludegraphics[height=2.41112pt,trim=0.0pt 30.0pt 0.0pt 0.0pt]{graphics/simplex.pdf}}_n}⟨ x,M_1y⟩$ and $Y_M_2:=\arg\min_y∈\mathchoice{∈cludegraphics[height=4.2194 pt,trim=0.0pt 30.0pt 0.0pt 0.0pt]{graphics/simplex.pdf}{∈cludegraphics[heig ht=4.2194pt,trim=0.0pt 25.0pt 0.0pt 0.0pt]{graphics/simplex.pdf}}{ ∈cludegraphics[height=3.31529pt,trim=0.0pt 30.0pt 0.0pt 0.0pt]{graphics/ simplex.pdf}}{∈cludegraphics[height=2.41112pt,trim=0.0pt 30.0pt 0.0pt 0.0pt] {graphics/simplex.pdf}}_f_{2(\hat{j})}}\max_x∈\mathchoice{ ∈cludegraphics[height=4.2194pt,trim=0.0pt 30.0pt 0.0pt 0.0pt]{graphics/ simplex.pdf}{∈cludegraphics[height=4.2194pt,trim=0.0pt 25.0pt 0.0pt 0.0pt]{ graphics/simplex.pdf}}{∈cludegraphics[height=3.31529pt,trim=0.0pt 30.0pt 0.0 pt 0.0pt]{graphics/simplex.pdf}}{∈cludegraphics[height=2.41112pt,trim=0.0pt 30.0pt 0.0pt 0.0pt]{graphics/simplex.pdf}}_n}⟨ x,M_2y⟩$ . For any vector $v$ and the set of indices $S=\{i_1,…,i_\ell\}$ , let $v_S$ denote the vector $(v_i_1,…,v_i_{\ell})$ . Let $X_A:=\{x∈\mathchoice{∈cludegraphics[height=6.02773pt,trim=0.0 pt 30.0pt 0.0pt 0.0pt]{graphics/simplex.pdf}}{∈cludegraphics[height=6.02773 pt,trim=0.0pt 25.0pt 0.0pt 0.0pt]{graphics/simplex.pdf}}{∈cludegraphics[heig ht=4.73611pt,trim=0.0pt 30.0pt 0.0pt 0.0pt]{graphics/simplex.pdf}}{ ∈cludegraphics[height=3.44444pt,trim=0.0pt 30.0pt 0.0pt 0.0pt]{graphics/ simplex.pdf}}_n:x_f_{1(\hat{i})}∈X_M_1\}$ and $Y_A:=\{y∈\mathchoice{∈cludegraphics[height=6.02773pt,trim=0.0 pt 30.0pt 0.0pt 0.0pt]{graphics/simplex.pdf}}{∈cludegraphics[height=6.02773 pt,trim=0.0pt 25.0pt 0.0pt 0.0pt]{graphics/simplex.pdf}}{∈cludegraphics[heig ht=4.73611pt,trim=0.0pt 30.0pt 0.0pt 0.0pt]{graphics/simplex.pdf}}{ ∈cludegraphics[height=3.44444pt,trim=0.0pt 30.0pt 0.0pt 0.0pt]{graphics/ simplex.pdf}}_m:y_f_{2(\hat{j})}∈Y_M_2\}$ . We return $X_A×Y_A$ as the set of all Nash equilibria if the following conditions hold:
1. $V_M_1^⋆=V_M_2^⋆$ .
1. $\bigcap\limits_x∈X_AI_x^\prime=f_2(\hat{j})$ where $I_x^\prime=\{j∈[n]:V_M_1^⋆=⟨ x,Ae_j⟩\}$ .
1. $\bigcap\limits_y∈Y_AI_y^\prime=f_1(\hat{i})$ where $I_y^\prime=\{i∈[n]:V_M_2^⋆=⟨ e_i,Ay⟩\}$ .
The above conditions can be checked by querying all the entries of $A$ in the set $\{(i,j):i∈ f_1(\hat{i}),j∈[n]\}∪\{(i,j):i∈[n],j∈ f_2(\hat{j})\}$ . If any one of the conditions above does not hold, we return "failure" instead.
Now we state the guarantees of our randomized procedure.
**Lemma 11**
*Consider a matrix game $A∈ℝ^n× n$ . Now we have the following:
- The procedure Nash $(A,δ,k_1,k_2)$ queries at most $O(nk^3·\log n·\log(\frac{n}{δ}))$ entries of $A$ .
- With probability at least $1-δ$ , the procedure Nash $(A,δ,k_1,k_2)$ returns $X_⋆×Y_⋆$ .*
* Proof*
Due to Lemma 9, SetV $(A,δ/2,k_1,k_2)$ queries at most $O(nk^3·\log n·\log(\frac{n}{δ}))$ entries of $A$ . Next due to Lemma 5, the number of calls made by FindPsne ( $A^(k_1,k_2,V),δ/2$ ) to the query oracle $Q$ is at most $O(\log(n^k)·\log(\frac{n^k}{δ}))≤ O(k^2·\log(n)·\log (\frac{n}{δ}))$ . Each call to the query oracle $Q$ takes $O(nk)$ queries from the input matrix $A$ . Moreover, to check the conditions (C1), (C2) and (C3) it takes $O(nk)$ queries. Hence, the procedure Nash $(A,δ,k_1,k_2)$ queries at most $O(nk^3·\log n·\log(\frac{n}{δ}))$ entries of $A$ . Due Lemma 9, with probability at least $1-\frac{δ}{2}$ , SetV $(A,δ/2,k_1,k_2)$ returns a set $V$ such that $V_A^⋆∈V$ . Recall the construction of the sets $X_A$ and $Y_A$ . Due to Lemma 10 and Lemma 6, the procedure FindPsne $(A^(k_1,k_2,V),δ/2)$ returns the pair $(i_⋆,j_⋆)$ with probability at least $1-\frac{δ}{2}$ if $V_A^⋆∈V$ , where $i_⋆:=f_1^-1(\bigcup\limits_x∈X_⋆\operatorname*{ supp}(x))$ and $j_⋆:=f_2^-1(\bigcup\limits_y∈Y_⋆\operatorname*{ supp}(y))$ . The previous facts along with Lemma 3 imply that with probability at least $1-δ$ , we have $X_A=X_⋆$ and $Y_A=Y_⋆$ . As the set $X_⋆×Y_⋆$ satisfies the conditions (C1), (C2) and (C3) due to Lemma 3, with probability at least $1-δ$ , the procedure Nash $(A,δ,k_1,k_2)$ returns $X_⋆×Y_⋆$ . ∎
#### 5.1.3 Relaxing the assumption on the knowledge of $k_1$ and $k_2$ .
It is straightforward to relax the assumption on the knowledge of $k_1$ and $k_2$ . Beginning with $s=1$ , we call the procedure Nash ( $A,δ,s_1,s_2$ ) on all possible pairs $(s_1,s_2)$ such that $\max\{s_1,s_2\}=s$ . Note that the number of such pairs is $2s-1$ . If for any one of the pairs $(s_1,s_2)$ the procedure Nash ( $A,δ,s_1,s_2$ ) returns a set $X_A×Y_A$ , we return it as the set of all Nash equilibria and terminate the process. If for all the pairs $(s_1,s_2)$ the procedure Nash ( $A,δ,s_1,s_2$ ) returns "failure" then we increment $s$ by one and repeat the process. With probability $1-δ$ , this process terminates at $s=k$ and returns the set $X_⋆×Y_⋆$ . This is because the set $X_⋆×Y_⋆$ is the only set that satisfies the conditions (C1), (C2) and (C3) due to Lemma 3. Hence, with probability $1-δ$ , the total number of queries taken from $A$ is at most $(∑_s=1^k2s-1)· O(nk^3·\log n·\log(\frac{n}{δ}))=O(nk ^5·\log n·\log(\frac{n}{δ}))$ .
### 5.2 Lower bound
In this section, we prove the following lower bound result on the query complexity.
See 2
* Proof*
For each $\ell∈[n]$ , let $I_\ell$ be the set of all $n× n$ matrices such that the following holds:
1. all entries $(i,j)$ have a value two for $i∈[n]$ and $j∈[n]∖[k]$
1. for each $i∈[n]$ such that $i∉\{1\}∪\{\ell\}$ , there exists exactly one index $j∈[k]$ such that the entry $(i,j)$ has a value of zero.
1. rest of the entries of the matrix have a value of one.
Fix an index $\ell∈[n]$ . For any matrix in $I_\ell$ , it can be easily shown using Lemma 1 that $S_\ell:=\{(e_i,e_j):i∈\{1\}∪\{\ell\},j∈[k]\}$ is the set of all pure strategy nash equilibria, and that their convex combination is the set of all Nash equilibria. Also observe that for two distinct indices $\ell_1,\ell_2∈[n]$ , we have $S_\ell_1≠S_\ell_2$ . Let $D$ be a uniform distribution over the set of matrices in $I_1$ . Observe that for any matrix $A∈I_1$ , we have $\max\{k_1,k_2\}=k$ and $\min\{k_1,k_2\}=1$ . Let us assume that the randomized algorithm $A$ is a distribution over a set $T$ of deterministic algorithms. Fix a deterministic instance $∈T$ . Let $τ(,A)$ denote the number of queries taken by $$ from an input matrix $A$ . We now aim to show that $E_A∼D[τ(,A)]≥\frac{(n -1)(k+1)}{2}$ . For the sake of simplicity in presentation, let us assume that $$ does not query an entry more than once. Consider an input matrix $A∈I_1$ . As $$ correctly computes the set of all PSNEs of the input matrix, $$ has to query all those entries of $A$ that have a value of $0 0$ . For the sake of contradiction, let us assume that $$ does not query an entry $(i^\prime,j^\prime)$ that has a value of $0 0$ . One can create a matrix $B∈I_i^\prime$ such that for all $(i,j)≠(i^\prime,j^\prime)$ we have $B_i,j=A_i,j$ and $B_i^\prime,j^{\prime}=1$ . As $$ terminates without querying the entry $(i^\prime,j^\prime)$ it cannot distinguish between $A$ and $B$ and hence outputs the wrong set of PSNEs for at least one of the matrices which is contradiction to our assumption. Hence, all the $n-1$ zero-valued entries are always queried for all matrices in $I_1$ . We continue to focus on the input matrices $A$ in $I_1$ . Fix $i∈[n]∖\{1\}$ . Let $X_i,A$ denote the number of entries of the set $\{(i,j):j∈[k]\}$ that $$ queries before querying the zero-valued entry in row $i$ of an input matrix $A$ . Let $F_i$ be the family of functions $f:[n]∖\{1,i\}→[k]$ . Fix $f∈F_i$ . Let $I_1,f$ be the largest subset of $I_1$ such that for all $A∈I_1,f$ we have $A_\hat{i,f(\hat{i})}=0$ for all $\hat{i}∈[n]∖\{1,i\}$ . Let $(i,j_1)$ be the first entry to be queried from the set $\{(i,j):j∈[k]\}$ by $$ if input matrix $A$ is chosen from the set $I_1,f$ . Recursively for $\ell≥ 2$ , let $(i,j_\ell)$ be the $\ell$ -th entry to be queried from the set $\{(i,j):j∈[k]\}$ by $$ if input matrix $A$ is chosen from the set $I_1,f$ and the first $\ell-1$ entries queried from the set $\{(i,j):j∈[k]\}$ have a value of one. Note that the sequence $j_1,…,j_k$ is fixed as $$ behaves identically on all the matrices in $I_1,f$ until it queries the entry in row $i$ that has a value of $0 0$ . Fix $m∈\{0,…,k-1\}$ . Now observe that $ℙ_A∼D[X_i,A=m|A∈I_1,f]=ℙ_A ∼D[A_i,j_{m+1}=0|A∈I_1,f]=\frac{1}{k}$ as $|I_1,f|=k$ and there is exactly one matrix $A∈I_1,f$ such that $A_i,j_{m+1}=0$ . Now we have the following:
$$
\displaystyleℙ_A∼D[X_i,A=m] \displaystyle=∑_f∈F_iℙ_A∼D[X_i,A=
m|A∈I_1,f]·ℙ_A∼D[A∈I_1,
f] \displaystyle=\frac{1}{k}·∑_f∈F_iℙ_A∼
D[A∈I_1,f] \displaystyle=\frac{1}{k}
$$ Hence, $E_A∼D[X_i,A]=∑_m=0^k-1\frac{m}{k}=\frac{k-1}{2}$ . Now observe that $E_A∼D[τ(,A)]≥(n-1)+ ∑_i=2^nE_A∼D[X_i,A]=\frac{(n-1)(k+1)}{2}$ . Now due to Yao’s lemma, we have that
$$
\max_A∈I_1\operatorname*{E}[τ(A)]≥\min_
\operatorname*{E}_A∼
D[τ(,A)]≥\frac{(n-1)(k+1)}{2}.
$$
∎
## 6 Conclusion and Open Questions
This paper characterizes the query complexity of finding the set of all Nash equilibria, $X_⋆×Y_⋆$ , in two-player zero-sum matrix games. In Theorem 1, we demonstrated that with probability at least $1-δ$ , the set $X_⋆×Y_⋆$ can be found by querying at most $O(nk^5·\operatorname*{polylog}(\frac{n}{δ}))$ entries. Additionally, in Theorem 2, we established a lower bound of $Ω(nk)$ . Bridging the gap between this upper and lower bound remains an important open question.
Furthermore, note that our algorithm does not run in polynomial time. Therefore, designing a polynomial-time randomized algorithm that requires $o(n^2)$ queries and finds a Nash equilibrium presents another compelling open problem. We conjecture that such an algorithm would need to be strongly polynomial.
Finally, it is worth recalling that there exists a deterministic algorithm with a query complexity of $O(n)$ to find the strict PSNE. The question of whether a deterministic algorithm can be developed to find the set of all Nash equilibria with $o(n^2)$ queries is yet another important open question.
## ACKNOWLEDGEMENTS
This work was supported in part by NSF TRIPODS CCF Award #2023166 and a Northrop Grumman University Research Award. We thank Prof. Rahul Savani for his feedback on the paper.
## References
- Adler [2013] Ilan Adler. The equivalence of linear programs and zero-sum games. International Journal of Game Theory, 42(1):165, 2013.
- Auger et al. [2014] David Auger, Jialin Liu, Sylvie Ruette, David Lupien St-Pierre, and Olivier Teytaud. Sparse binary zero-sum games. In ACML, 2014.
- Babichenko [2016] Yakov Babichenko. Query complexity of approximate nash equilibria. Journal of the ACM (JACM), 63(4):1–24, 2016.
- Babichenko [2020] Yakov Babichenko. Informational bounds on equilibria (a survey). ACM SIGecom Exchanges, 17(2):25–45, 2020.
- Bienstock et al. [1991] Daniel Bienstock, Fan Chung, Michael L Fredman, Alejandro A Schäffer, Peter W Shor, and Subhash Suri. A note on finding a strict saddlepoint. The American mathematical monthly, 98(5):418–419, 1991.
- Bohnenblust et al. [1948] HF Bohnenblust, MA Girshick, RN Snow, Melvin Dresher, Olaf Helmer-Hirschberg, JCC McKinsey, Lloyd S Shapley, and Theodore Edward Harris. Mathematical theory of zero-sum two-person games with a finite number or a continuum of strategies. 1948.
- Bohnenblust et al. [1950] HF Bohnenblust, S Karlin, and LS Shapley. Solutions of discrete, two-person games. Contributions to the Theory of Games, 1:51–72, 1950.
- Brooks and Reny [2021] Benjamin Brooks and Philip J Reny. A canonical game–nearly 75 years in the making–showing the equivalence of matrix games and linear programming. Available at SSRN 3851583, 2021.
- Chen et al. [2009] Xi Chen, Xiaotie Deng, and Shang-Hua Teng. Settling the complexity of computing two-player nash equilibria. Journal of the ACM (JACM), 56(3):1–57, 2009.
- Dallant et al. [2024a] Justin Dallant, Frederik Haagensen, Riko Jacob, László Kozma, and Sebastian Wild. Finding the saddlepoint faster than sorting. In 2024 Symposium on Simplicity in Algorithms (SOSA), pages 168–178. SIAM, 2024a.
- Dallant et al. [2024b] Justin Dallant, Frederik Haagensen, Riko Jacob, László Kozma, and Sebastian Wild. An optimal randomized algorithm for finding the saddlepoint. arXiv preprint arXiv:2401.06512, 2024b.
- Dantzig [1951] George B Dantzig. A proof of the equivalence of the programming problem and the game problem. Activity analysis of production and allocation, 13, 1951.
- Daskalakis et al. [2007] Constantinos Daskalakis, Aranyak Mehta, and Christos Papadimitriou. Progress in approximate nash equilibria. In Proceedings of the 8th ACM Conference on Electronic Commerce, pages 355–358, 2007.
- Daskalakis et al. [2009] Constantinos Daskalakis, Aranyak Mehta, and Christos Papadimitriou. A note on approximate nash equilibria. Theoretical Computer Science, 410(17):1581–1588, 2009.
- Deligkas et al. [2022] Argyrios Deligkas, Michail Fasoulakis, and Evangelos Markakis. A polynomial-time algorithm for 1/3-approximate nash equilibria in bimatrix games. arXiv preprint arXiv:2204.11525, 2022.
- Deligkas et al. [2023] Argyrios Deligkas, Michail Fasoulakis, and Evangelos Markakis. A polynomial-time algorithm for 1/2-well-supported nash equilibria in bimatrix games. In Proceedings of the 2023 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 3777–3787. SIAM, 2023.
- Fearnley and Savani [2016] John Fearnley and Rahul Savani. Finding approximate nash equilibria of bimatrix games via payoff queries. ACM Transactions on Economics and Computation (TEAC), 4(4):1–19, 2016.
- Fearnley et al. [2013] John Fearnley, Martin Gairing, Paul Goldberg, and Rahul Savani. Learning equilibria of games via payoff queries. In Proceedings of the fourteenth ACM conference on Electronic commerce, pages 397–414, 2013.
- Goldberg and Roth [2016] Paul W Goldberg and Aaron Roth. Bounds for the query complexity of approximate equilibria. ACM Transactions on Economics and Computation (TEAC), 4(4):1–25, 2016.
- Karlin and Peres [2017] Anna R Karlin and Yuval Peres. Game theory, alive, volume 101. American Mathematical Soc., 2017.
- Maiti et al. [2024] Arnab Maiti, Ross Boczar, Kevin Jamieson, and Lillian Ratliff. Near-optimal pure exploration in matrix games: A generalization of stochastic bandits & dueling bandits. In International Conference on Artificial Intelligence and Statistics, pages 2602–2610. PMLR, 2024.
- v. Neumann [1928] J v. Neumann. Zur theorie der gesellschaftsspiele. Mathematische annalen, 100(1):295–320, 1928.