  We study the query complexity of identifying Nash equilibria in two-player
zero-sum matrix games. Grigoriadis and Khachiyan (1995) showed that any
deterministic algorithm needs to query $\Omega(n^2)$ entries in worst case from
an $n\times n$ input matrix in order to compute an $\varepsilon$-approximate
Nash equilibrium, where $\varepsilon<\frac{1}{2}$. Moreover, they designed a
randomized algorithm that queries $\mathcal O(\frac{n\log n}{\varepsilon^2})$
entries from the input matrix in expectation and returns an
$\varepsilon$-approximate Nash equilibrium when the entries of the matrix are
bounded between $-1$ and $1$. However, these two results do not completely
characterize the query complexity of finding an exact Nash equilibrium in
two-player zero-sum matrix games. In this work, we characterize the query
complexity of finding an exact Nash equilibrium for two-player zero-sum matrix
games that have a unique Nash equilibrium $(x_\star,y_\star)$. We first show
that any randomized algorithm needs to query $\Omega(nk)$ entries of the input
matrix $A\in\mathbb{R}^{n\times n}$ in expectation in order to find the unique
Nash equilibrium where $k=|\text{supp}(x_\star)|$. We complement this lower
bound by presenting a simple randomized algorithm that, with probability
$1-\delta$, returns the unique Nash equilibrium by querying at most $\mathcal
O(nk^4\cdot \text{polylog}(\frac{n}{\delta}))$ entries of the input matrix
$A\in\mathbb{R}^{n\times n}$. In the special case when the unique Nash
Equilibrium is a pure-strategy Nash equilibrium (PSNE), we design a simple
deterministic algorithm that finds the PSNE by querying at most $\mathcal O(n)$
entries of the input matrix.
