# A Polynomial-Time Algorithm for 1/2-Well-Supported Nash Equilibria in
Bimatrix Games

Argyrios Deligkas1, Michail Fasoulakis2,3, Evangelos Markakis3
Royal Holloway, University of London1
Foundation for Research and Technology-Hellas (FORTH)2
Athens University of Economics and Business3

###### Abstract

Since the seminal PPAD-completeness result for computing a Nash equilibrium
even in two-player games, an important line of research has focused on
relaxations achievable in polynomial time. In this paper, we consider the
notion of $\varepsilon$-well-supported Nash equilibrium, where
$\varepsilon\in[0,1]$ corresponds to the approximation guarantee. Put simply,
in an $\varepsilon$-well-supported equilibrium, every player chooses with
positive probability actions that are within $\varepsilon$ of the maximum
achievable payoff, against the other player’s strategy. Ever since the initial
approximation guarantee of 2/3 for well-supported equilibria, which was
established more than a decade ago, the progress on this problem has been
extremely slow and incremental. Notably, the small improvements to 0.6608, and
finally to 0.6528, were achieved by algorithms of growing complexity. Our main
result is a simple and intuitive algorithm, that improves the approximation
guarantee to 1/2. Our algorithm is based on linear programming and in
particular on exploiting suitably defined zero-sum games that arise from the
payoff matrices of the two players. As a byproduct, we show how to achieve the
same approximation guarantee in a query-efficient way.

##  1 Introduction

The computation of a Nash equilibrium has been one of the most fundamental
problems in the intersection of computer science and economics. The non-
constructive proof of existence by Nash for finite games [38], motivated a
significant volume of works to focus on the quest for efficient algorithms.
This quest was terminated by the landmark results of [17, 10], establishing
PPAD-completeness, even for two-player games.

The above intractability results naturally led to the study of polynomial-time
algorithms for approximate Nash equilibria. But as this is not a typical
optimization problem with a single objective to optimize, there exist in the
literature different ways of defining approximate solutions. Among them, the
two most prevalent notions of approximability are those of $\varepsilon$-Nash
equilibria and $\varepsilon$-well-supported Nash equilibria
($\varepsilon$-WSNE), for $\varepsilon>0$, assuming that all payoffs of the
game have been scaled to be in $[0,1]$. In an $\varepsilon$-Nash equilibrium,
the expected payoff of any player is at most $\varepsilon$ less than the best-
response payoff. In an $\varepsilon$-well-supported Nash equilibrium, any pure
strategy that is played with a positive probability, should have a payoff of
at most $\varepsilon$ less than the best-response payoff. It is easy to see
that the latter is a stronger approximation concept, as any
$\varepsilon$-well-supported Nash equilibrium is an $\varepsilon$-Nash
equilibrium, but the other direction does not always hold.

The research efforts on these two notions have not evolved equally well. For
$\varepsilon$-Nash equilibria, there was a steady progress, starting with a
$\frac{3}{4}$-approximation in [28], and gradual improvements to $\frac{1}{2}$
by [19], $0.382$ in [18], $0.364$ by [7], and $(0.3393+\delta)$ by [42], for
any constant $\delta>0$. Finally, a very recent improvement by [20], has
obtained the currently best approximation of $(\frac{1}{3}+\delta)$, for any
constant $\delta>0$. On the other hand, the first result for
$\varepsilon$-well-supported Nash equilibria was given by Kontogiannis and
Spirakis [29], with a $\frac{2}{3}$-approximation. This was obtained by a
quite “clean” and easy to implement algorithm, requiring only a single call to
a linear programming solver. After this, the progress on this front has been
very incremental and with algorithms of growing complexity. A refinement of
the algorithm by [29] was analyzed in [24], obtaining a
$0.6608$-approximation. Later on, a more involved algorithm was provided by
[14], achieving an additional improvement to 0.6528. The guarantee of 0.6528
has been the state of the art for the last 7 years [13].

For both approximation notions, it is well known that there exist quasi-
polynomial time algorithms [32, 29] for any constant $\varepsilon>0$, running
in time $n^{O(\log{n}/\epsilon^{2})}$, for a game with $n$ available pure
strategies per player. Quite interestingly, for well-supported equilibria,
there exists an improved quasi-polynomial time algorithm for computing a
$(\frac{1}{2}+\delta)$-approximation, for any constant $\delta>0$ [23], making
the exponent dependent on $\log{\log{n}}$, rather than $\log{n}$. This can be
viewed as supporting evidence that further improvements on the running time
might be feasible for obtaining a $(\frac{1}{2}+\delta)$-well-supported
approximation, and even a polynomial time algorithm could be anticipated.

Finally, regarding impossibility results, we know by the work of Rubinstein
[41] that, assuming the exponential-time hypothesis for PPAD, then
$\varepsilon$-Nash equilibria, and consequently $\varepsilon$-well-supported
equilibria as well, require quasi-polynomial time, when $\varepsilon$ is below
some very small, yet unspecified, constant. This rules out a PTAS for both
approximation notions. But especially for well-supported equilibria, it also
leaves open a very large gap from the 0.6528-approximation.

###  1.1 Our contribution

We improve upon the state of the art on the computation of approximate well-
supported Nash equilibria in two respects. Firstly, we derive a polynomial-
time algorithm (Algorithm 1) that, for every constant $\delta$, computes a
$(\frac{1}{2}+\delta)$-WSNE. Our algorithm is more intuitive and conceptually
much simpler compared to the algorithm of [14] that finds a $0.6528$-WSNE.
Then, we use Algorithm 1 as a basis for a query-efficient algorithm (Algorithm
2) that achieves the same approximation guarantee.

#### Algorithm 1 (main result):

To provide a high level description, the first step in Algorithm 1 is to
compute a Nash equilibrium in the zero-sum games $(R,-R)$ and $(-C,C)$, where
$R$ and $C$ are the payoff matrices of the row and column player respectively.
These equilibrium-strategies, and their corresponding payoffs, are utilized to
partition the remaining analysis into three cases that the algorithm considers
sequentially. The first and easier case occurs when the solutions of the two
zero-sum games induce a strategy profile, where the maximum possible payoff
for each player under the chosen strategy of their opponent is “low”, i.e., it
is bounded by $\frac{1}{2}$. This directly yields a $1/2$-approximation. The
remaining two cases (referred to as the low-high and the high-high cases) are
more interesting and in these cases we utilize either a linear system solver,
or a support enumeration argument, to construct the desirable strategy
profile.

#### Algorithm 2: query-efficient algorithm.

In order to convert Algorithm 1 into a query-efficient protocol we utilize the
fact that $\varepsilon$-WSNEs in zero-sum games can be found with
$O(\frac{n\cdot\log n}{\varepsilon^{2}})$ queries. Then, using the approximate
well-supported Nash equilirbia we found, we resort to sampling in order to
create a subgame with $O(\log n)$ rows and $O(n)$ columns (or the other way
around, depending on the case we are handling). This subgame is guaranteed to
have a strategy profile that is a $(\frac{1}{2}+\delta+3\varepsilon)$-WSNE for
the original game. In order to find such a profile the algorithm simply
queries the whole subgame and it proceeds as our main algorithm.

###  1.2 Further related work

Apart from results on general two-player games, there have been several
studies focusing on the approximability of Nash equilibria in specific classes
of games. For instance, for constant-rank games, where the matrix defined by
the sum of the two payoff matrices has constant rank [1, 27, 36]; for win-lose
games [11, 12, 33]; for sparse games [9, 5], for imitation games [34, 35, 37];
for random games [4, 39]; for symmetric games [15, 30] and for games with
symmetric payoff matrices [16].

There have also been results on new quasi-polynomial algorithms (QPTAS). We
mention three new QPTASs that have been obtained: [5] gave a refined,
parameterized, approximation scheme; [3] gave a QPTAS that can be applied to
multi-player games as well; [21] gave a more general approach for
approximation schemes for the existential theory of the reals. Furthermore,
more negative results for $\varepsilon$-NE were derived: [31] gave an
unconditional lower bound, based on the sum of squares hierarchy; [6] proved
PPAD-hardness in the smoothed analysis setting; [2, 8, 22] gave quasi-
polynomial time lower bounds for constrained $\varepsilon$-NE, under the
exponential time hypothesis.

##  2 Preliminaries

In what follows, for any natural number $n$, we denote by $[n]$ the set
$\\{1,2,\ldots,n\\}$ and by $\Delta^{n}$ the $(n-1)$-dimensional simplex. An
$n\times n$ bimatrix game $(R,C)$ is defined by two payoff matrices $R$ and
$C$ of size $n\times n$ each: $R$ defines the payoffs of the row player and
$C$ defines the payoffs of the column player. When the row player picks a row
$i\in[n]$ and the column player picks a column $j\in[n]$, then they receive a
payoff of $R_{ij}$ and $C_{ij}$, respectively. We follow the usual assumption
in the relevant literature that the matrices are normalized, so that all
entries are in $[0,1]$.

A mixed strategy is a probability distribution over $[n]$. We use
$\mathbf{x}\in\Delta^{n}$ to denote a mixed strategy for the row player and
$\mathbf{y}\in\Delta^{n}$ to denote a mixed strategy for the column player. If
$\mathbf{x}$ and $\mathbf{y}$ are mixed strategies for the row and the column
player respectively, then we call $(\mathbf{x},\mathbf{y})$ a strategy
profile. We denote by $e_{i}$ the $n$-dimensional vector that has 1 at index
$i$ and 0 elsewhere. Hence, $e_{i}$ corresponds to a pure strategy, where a
player assigns probability one to play the pure strategy $i$. A useful notion
in equilibrium computation is the support of a strategy $\mathbf{x}$, denoted
by $\mathrm{supp}(\mathbf{x})$, which is the set of pure strategies that are
played with positive probability under $\mathbf{x}$. Formally,
$\mathrm{supp}(\mathbf{x}):=\\{i\in[n]:\mathbf{x}(i)>0\\}$.

Given a strategy profile $(\mathbf{x},\mathbf{y})$, the expected payoff of the
row player is $\mathcal{R}(\mathbf{x},\mathbf{y}):=\mathbf{x}^{T}R\mathbf{y}$,
and the expected payoff of the column player is
$\mathcal{C}(\mathbf{x},\mathbf{y}):=\mathbf{x}^{T}C\mathbf{y}$. Hence, for a
pure strategy $e_{i}$, the term
$\mathcal{R}(e_{i},\mathbf{y}):=\sum_{j}R_{ij}y_{j}$, denotes the expected
payoff of the row player, when she plays the pure strategy $i$ against
strategy $\mathbf{y}$ of the column player. Similarly,
$\mathcal{C}(\mathbf{x},e_{j})$ is the expected payoff of the column player
when she plays the pure strategy $j$ against $\mathbf{x}$. A pure strategy is
a best-response strategy for a player against a chosen strategy of her
opponent, if it maximizes her expected payoff; a pure strategy is an
$\varepsilon$-best response, for $\varepsilon\in[0,1]$, if it achieves a
payoff that is at most $\varepsilon$ less than the maximum possible payoff
against the opponent’s chosen strategy.

Well-supported Nash equilibria. A strategy profile $(\mathbf{x},\mathbf{y})$
is an $\varepsilon$-well-supported Nash equilibrium, henceforth
$\varepsilon$-WSNE, for some $\varepsilon\in[0,1]$, if every player plays with
positive probability only pure strategies that are $\varepsilon$-best
responses. Put formally, $(\mathbf{x},\mathbf{y})$ is an $\varepsilon$-WSNE if
the following conditions are satisfied:

$\displaystyle\mathcal{R}(e_{i},\mathbf{y})\geq\max_{k\in[n]}\mathcal{R}(e_{k},\mathbf{y})-\varepsilon\quad\text{for
all}~{}i\in\mathrm{supp}(\mathbf{x});$
$\displaystyle\mathcal{C}(\mathbf{x},e_{j})\geq\max_{k\in[n]}\mathcal{C}(\mathbf{x},e_{k})-\varepsilon\quad\text{for
all}~{}j\in\mathrm{supp}(\mathbf{y}).$

If $\varepsilon=0$, then 0-WSNE is an exact Nash equilibrium.

$k$-uniform strategies. For any natural number $k$, a $k$-uniform strategy
plays each pure strategy with probability that is a multiple of $\frac{1}{k}$;
i.e. $\mathbf{x}$ is $k$-uniform if for every $i\in[n]$ it holds that
$\mathbf{x}(i)\in\\{0,\frac{1}{k},\frac{2}{k},\ldots,\frac{k-1}{k},1\\}$. If
both $\mathbf{x}$ and $\mathbf{y}$ are $k$-uniform strategies, then we will
say that $(\mathbf{x},\mathbf{y})$ is a $k$-uniform strategy profile. We will
use $k$-uniform strategies for different values of $k$ in several parts of our
algorithms. Observe that for any fixed value of $k$, the size of the support
of a $k$-uniform strategy is at most $k$. This implies that in a $n\times n$
bimatrix game, there are at most $O(n^{k})$ $k$-uniform strategy profiles. In
addition, $k$-uniform strategies are used to produce sampled strategies as
explained below.

Sampled strategies. Given a strategy $\mathbf{x}$, a $k$-uniform sampled
strategy $\mathbf{x}_{s}$ is produced by taking $k$ independent samples from
$[n]$ according to $\mathbf{x}$, and by setting $\mathbf{x}_{s}(i)$ equal to
the frequency with which pure strategy $i$ was sampled. Observe that
$\mathrm{supp}(\mathbf{x}_{s})\subseteq\mathrm{supp}(\mathbf{x})$. Sampled
strategies can approximate well any arbitrary strategy if enough samples are
taken; roughly, if the sampled strategy has to satisfy $m$ constraints with an
$\varepsilon$-additive error, then $O(\frac{\log
m}{\mathrm{poly}(\varepsilon)})$ samples suffice.

Next, we list some lemmas that involve $k$-uniform sampled strategies that
will be used later in the analysis of our algorithms.

######  Lemma 1 (Implied by the proof of Theorem 1 of [32]).

Let $(\mathbf{x},\mathbf{y})$ be a strategy profile of an $n\times n$ bimatrix
game. Then, there exist $O(\frac{\log n}{\varepsilon^{2}})$-uniform sampled
strategies $\mathbf{x}_{s},\mathbf{y}_{s}$ such that:

$\displaystyle|\mathcal{R}(\mathbf{x},\mathbf{y})-\mathcal{R}(\mathbf{x}_{s},\mathbf{y}_{s})|\leq\varepsilon\quad$
$\displaystyle\text{and}\quad|\mathcal{R}(e_{i},\mathbf{y})-\mathcal{R}(e_{i},\mathbf{y}_{s})|\leq\varepsilon\quad\forall
i\in[n];$
$\displaystyle|\mathcal{C}(\mathbf{x},\mathbf{y})-\mathcal{C}(\mathbf{x}_{s},\mathbf{y}_{s})|\leq\varepsilon\quad$
$\displaystyle\text{and}\quad|\mathcal{C}(\mathbf{x},e_{j})-\mathcal{C}(\mathbf{x}_{s},e_{j})|\leq\varepsilon\quad\forall
j\in[n].$

######  Lemma 2.

Let $(\mathbf{x},\mathbf{y})$ be an $\varepsilon$-WSNE of an $n\times n$
bimatrix game and let $\mathbf{x}_{s},\mathbf{y}_{s}$ be $O(\frac{\log
n}{\varepsilon^{2}})$-uniform strategies sampled from $\mathbf{x}$ and
$\mathbf{y}$ respectively. Then, $(\mathbf{x}_{s},\mathbf{y}_{s})$ is a
$3\varepsilon$-WSNE for the game.

###### Proof.

Assume that we are considering the bimatrix game $(R,C)$. We will focus on the
row player, since the analysis for the second player is identical. Recall that
since $\mathbf{x}_{s}$ is sampled from $\mathbf{x}$ it holds that
$\mathrm{supp}(\mathbf{x}_{s})\subseteq\mathrm{supp}(\mathbf{x})$. So,
consider an $i\in\mathrm{supp}(\mathbf{x}_{s})$:

$\displaystyle\mathcal{R}(e_{i},\mathbf{y}_{s})$
$\displaystyle\geq\mathcal{R}(e_{i},\mathbf{y})-\varepsilon$ (From Lemma 1)
$\displaystyle\geq\max_{k\in[n]}\mathcal{R}(e_{k},\mathbf{y})-2\varepsilon$
(Since $(\mathbf{x},\mathbf{y})$ is an $\varepsilon$-WSNE)
$\displaystyle\geq\mathcal{R}(e_{k^{*}},\mathbf{y})-2\varepsilon$
($k^{*}\in\text{argmax}_{k}{\mathcal{R}(e_{k},\mathbf{y}_{s})}$)
$\displaystyle\geq\mathcal{R}(e_{k^{*}},\mathbf{y}_{s})-3\varepsilon$ (From
Lemma 1).
$\displaystyle=\max_{k\in[n]}\mathcal{R}(e_{k},\mathbf{y}_{s})-3\varepsilon$

∎

##  3 The algorithm

In this section we provide our main algorithm, that computes a
$(\frac{1}{2}+\delta)$-WSNE in polynomial time. This algorithm will form the
basis for obtaining an additional algorithm that still computes a
$(\frac{1}{2}+\delta)$-WSNE and is also query efficient.

Algorithm 1: Main Algorithm for $(\frac{1}{2}+\delta)$-WSNE Input: A bimatrix
game $(R,C)$ and constants $\delta\in(0,1],$ and
$\kappa(\delta)=\left\lceil\frac{2\ln{(1/\delta)}}{\delta^{2}}\right\rceil$.
Output: A $(\frac{1}{2}+\delta)$-WSNE for $(R,C)$. 1. Compute a Nash
equilibrium $(\mathbf{x}^{*},\mathbf{y}^{*})$ for the zero-sum game $(R,-R)$.
2. Compute a Nash equilibrium $(\hat{\mathbf{x}},\hat{\mathbf{y}})$ for the
zero-sum game $(-C,C)$. 3. If
$\mathcal{R}(\mathbf{x}^{*},\mathbf{y}^{*})\geq\mathcal{C}(\hat{\mathbf{x}},\hat{\mathbf{y}})$:
(a) If $\mathcal{R}(\mathbf{x}^{*},\mathbf{y}^{*})\leq\frac{1}{2}$, then
return $(\hat{\mathbf{x}},\mathbf{y}^{*})$. (b) Else, if there exists a
strategy $\mathbf{x}^{\prime}$ such that
$\mathrm{supp}(\mathbf{x}^{\prime})\subseteq\mathrm{supp}(\mathbf{x}^{*})$,
and $\mathcal{C}(\mathbf{x}^{\prime},e_{j})\leq\frac{1}{2}$ for every
$j\in[n]$, then return $(\mathbf{x}^{\prime},\mathbf{y}^{*})$. (c) Else,
exhaustively search over all $\kappa(\delta)$-uniform strategy profiles and
find a $(\frac{1}{2}+\delta)$-WNSE. 4. Else if
$\mathcal{C}(\hat{\mathbf{x}},\hat{\mathbf{y}})>\mathcal{R}(\mathbf{x}^{*},\mathbf{y}^{*})$:
(a) If $\mathcal{C}(\hat{\mathbf{x}},\hat{\mathbf{y}})\leq\frac{1}{2}$, then
return $(\hat{\mathbf{x}},\mathbf{y}^{*})$. (b) Else if there exists a
strategy $\mathbf{y}^{\prime}$ such that
$\mathrm{supp}(\mathbf{y}^{\prime})\subseteq\mathrm{supp}(\hat{\mathbf{y}})$,
and $\mathcal{R}(e_{i},\mathbf{y}^{\prime})\leq\frac{1}{2}$ for every
$i\in[n]$, then return $(\hat{\mathbf{x}},\mathbf{y}^{\prime})$. (c) Else,
exhaustively search over all $\kappa(\delta)$-uniform strategy profiles and
find a $(\frac{1}{2}+\delta)$-WNSE.

######  Theorem 1.

For any constant $\delta>0$, Algorithm 1 computes in polynomial time a
$(\frac{1}{2}+\delta)$-WSNE.

Before proving Theorem 1, we provide first a high level description. Algorithm
1 partitions the solution space into three cases that considers then
sequentially. If the algorithm fails to find a solution within a specific
case, this rules out the existence of certain strategy profiles and proceeds
to the next case, where it exploits the extra constraints that are imposed
from the failure of the previous cases. Before reaching the case-analysis
though, the algorithm computes a Nash equilibrium
$(\mathbf{x}^{*},\mathbf{y}^{*})$ for the zero-sum game $(R,-R)$ and a Nash
equilibrium $(\hat{\mathbf{x}},\hat{\mathbf{y}})$ for the zero-sum game
$(-C,C)$. These equilibrium-strategies, and their corresponding payoffs, are
utilized to provide bounds for the payoffs in the game $(R,C)$.

  * •

Case (a): low payoffs. Firstly, the algorithm checks if the solutions of the
two zero-sum games can be used to produce a strategy profile,
$(\hat{\mathbf{x}},\mathbf{y}^{*})$, where the maximum payoff for every player
under the chosen strategy of their opponent is “low”, i.e., it is bounded by
$\frac{1}{2}$. If this is the case, then under the strategy profile
$(\hat{\mathbf{x}},\mathbf{y}^{*})$, the regret of any action is bounded by
$\frac{1}{2}$, and we have a $\frac{1}{2}$-WSNE.

  * •

Case (b): low-high payoffs. If the first case fails, then the algorithm
deduces that there is a strategy profile among
$(\mathbf{x}^{*},\mathbf{y}^{*})$ and $(\hat{\mathbf{x}},\hat{\mathbf{y}})$,
where at least one of the players is guaranteed a “high” payoff from every
action they play with positive probability, i.e., every action in her support
yields a payoff of at least $\frac{1}{2}$. Then, it formulates a linear-
feasibility system that seeks a strategy for the high-payoff player yielding
“low” maximum payoff for her opponent. For example, if the algorithm finds out
that under $(\mathbf{x}^{*},\mathbf{y}^{*})$, the row player is guaranteed to
get high payoff, it fixes the strategy $\mathbf{y}^{*}$ for the column player,
since every action that is assigned positive probability under
$\mathbf{x}^{*}$ is guaranteed to yield a payoff of at least $\frac{1}{2}$ for
the row player. Then, it formulates the linear-feasibility system that checks
if there is a strategy $\mathbf{x}^{\prime}$ that restricts the row player to
place probability only on actions in the support of $\mathbf{x}^{*}$ and at
the same time bounds the maximum payoff of the column player by $\frac{1}{2}$.
If the linear system has indeed a feasible solution, the algorithm returns the
profile $(\mathbf{x}^{\prime},\mathbf{y}^{*})$, and this will be a
$\frac{1}{2}$-WSNE, by the preceding discussion.

  * •

Case (c): high payoffs. If the previous two cases fail, then we can prove that
there exists a strategy profile $(\mathbf{x},\mathbf{y})$, under which both
players are playing only actions that yield a payoff of at least
$\frac{1}{2}$, thus $(\mathbf{x},\mathbf{y})$ is a $\frac{1}{2}$-WSNE. In
order to prove this, we first define a “subgame” of $(R,C)$ that depends on
the Nash equilibria we have computed for the zero-sum games $(R,-R)$ and
$(-C,C)$. Then, using the properties of Nash equilibria, and the fact that the
previous two cases of the algorithm failed, we prove that in any Nash
equilibrium $(\mathbf{x},\mathbf{y})$ of this subgame, both players get a
payoff of at least $\frac{1}{2}$. On the other hand though, it is not
straightforward to find such a strategy profile. Luckily, we can show that we
can approximate this by a strategy profile $(\mathbf{w},\mathbf{z})$, where
each player plays with positive probability constantly-many actions and every
such action yields a payoff of at least $\frac{1}{2}-\delta$. Thus, we obtain
a $(\frac{1}{2}+\delta)$-WSNE by exhaustively searching over the strategy
profiles with constant support.

###  3.1 Proof of Theorem 1

Firstly, observe that Steps 1 and 2 can be performed in polynomial since it is
known that zero-sum games can be solved via a linear program. The remaining
steps can also be performed in polynomial time, as we will argue in the
sequel. In what follows we will assume that without loss of generality
$\mathcal{C}(\hat{\mathbf{x}},\hat{\mathbf{y}})\leq\mathcal{R}(\mathbf{x}^{*},\mathbf{y}^{*})$
and thus we will focus on the analysis of Step 3, since the analysis of Step 4
is symmetric.

Before we proceed with the analysis of Steps 3(a) - 3(c), we state the
following simple observation for Nash equilibria of zero-sum games.

######  Observation 1.

Let $(\mathbf{x}^{*},\mathbf{y}^{*})$ be a Nash equilibrium of the zero-sum
game $(R,-R)$. Then, for any other strategy $\mathbf{y}$ of the column player,
we have:

$\mathcal{R}(\mathbf{x}^{*},\mathbf{y}^{*})\leq\mathcal{R}(\mathbf{x}^{*},\mathbf{y}).$

Similarly, for an equilibrium $(\hat{\mathbf{x}},\hat{\mathbf{y}})$ of the
zero-sum game $(-C,C)$ we have that for any strategy $\mathbf{x}$ of the row
player:

$\mathcal{C}(\hat{\mathbf{x}},\hat{\mathbf{y}})\leq\mathcal{C}(\mathbf{x},\hat{\mathbf{y}}).$

###### Proof.

This follows from the fact that when we have an equilibrium
$(\mathbf{x}^{*},\mathbf{y}^{*})$ in a zero-sum game, the strategy
$\mathbf{x}^{*}$ is a max-min strategy, and therefore the row player can
guarantee at least the value of the game by playing $\mathbf{x}^{*}$,
independently of the column player’s choice of strategy. The second inequality
is proved in the same way by applying the same argument for the column player
in the zero-sum game $(-C,C)$. ∎

Now we are ready to prove the correctness of our algorithm. We will consider
every case separately. For the cases 3(a) and 3(b), the analysis is rather
straightforward.

######  Lemma 3 (Case 3(a)).

If
$\mathcal{C}(\hat{\mathbf{x}},\hat{\mathbf{y}})\leq\mathcal{R}(\mathbf{x}^{*},\mathbf{y}^{*})\leq\frac{1}{2}$,
then $(\hat{\mathbf{x}},\mathbf{y}^{*})$ is a $\frac{1}{2}$-WSNE for the game
$(R,C)$.

###### Proof.

Since $(\mathbf{x}^{*},\mathbf{y}^{*})$ is a Nash equilibrium of the game
$(R,-R)$, we know that for every $i\in[n]$, it holds that
$\mathcal{R}(e_{i},\mathbf{y}^{*})\leq\mathcal{R}(\mathbf{x}^{*},\mathbf{y}^{*})\leq\frac{1}{2}$.
Hence, the best-response payoff of the row player against $\mathbf{y}^{*}$ is
at most $\frac{1}{2}$, and thus, any strategy for the row player satisfies the
constraints of $\frac{1}{2}$-WSNE, when the column player plays
$\mathbf{y}^{*}$. Similarly, for the column player we get that for every
$j\in[n]$,
$\mathcal{C}(\hat{\mathbf{x}},e_{j})\leq\mathcal{C}(\hat{\mathbf{x}},\hat{\mathbf{y}})\leq\mathcal{R}(\mathbf{x}^{*},\mathbf{y}^{*})\leq\frac{1}{2}$.
So, the best-response payoff of the column player against $\hat{\mathbf{x}}$
is at most $\frac{1}{2}$, and thus, any mixed strategy for the column player
satisfies the constraints of $\frac{1}{2}$-WSNE, when the row player selects
$\hat{\mathbf{x}}$. ∎

######  Lemma 4 (Case 3(b)).

Suppose that
$\mathcal{C}(\hat{\mathbf{x}},\hat{\mathbf{y}})\leq\mathcal{R}(\mathbf{x}^{*},\mathbf{y}^{*})$
and $\mathcal{R}(\mathbf{x}^{*},\mathbf{y}^{*})>\frac{1}{2}$. If there exists
a strategy $\mathbf{x}^{\prime}$ with
$\mathrm{supp}(\mathbf{x}^{\prime})\subseteq\mathrm{supp}(\mathbf{x}^{*})$
such that $\mathcal{C}(\mathbf{x}^{\prime},e_{j})\leq\frac{1}{2}$ for any
$j\in[n]$, then $(\mathbf{x}^{\prime},\mathbf{y}^{*})$ is a $\frac{1}{2}$-WSNE
for $(R,C)$. In addition, we can find such a strategy $\mathbf{x}^{\prime}$,
or decide that no such strategy exists, in polynomial time by solving a system
of linear equations.

###### Proof.

Assume that such a strategy $\mathbf{x}^{\prime}$ exists. Recall that since
$\mathbf{x}^{*}$ is a best response against $\mathbf{y}^{*}$, any pure
strategy in $\mathrm{supp}(\mathbf{x}^{*})$ is also a best response against
$\mathbf{y}^{*}$. Thus, any $\mathbf{x}^{\prime}$ with
$\mathrm{supp}(\mathbf{x}^{\prime})\subseteq\mathrm{supp}(\mathbf{x}^{*})$, is
a best-response strategy against $\mathbf{y}^{*}$. Hence, the strategy profile
$(\mathbf{x}^{\prime},\mathbf{y}^{*})$ satisfies the constraints of
$\frac{1}{2}$-WSNE for the row player.

Now, for the column player, observe the following. Since the strategy
$\mathbf{x}^{\prime}$ guarantees that
$\mathcal{C}(\mathbf{x}^{\prime},e_{j})\leq\frac{1}{2}$, for any $j\in[n]$,
this means that the best-response payoff for the column player against
$\mathbf{x}^{\prime}$ is at most $\frac{1}{2}$. Thus, any mixed strategy for
the column player satisfies the constraints of the $\frac{1}{2}$-WSNE, when
the row player selects $\mathbf{x}^{\prime}$.

Finally, it only remains to argue that we can decide in polynomial time if
such a strategy exists, and if it does, to compute it efficiently. Indeed,
this can be formulated as a feasibility system of linear equations. In
particular, it corresponds to finding a solution for the linear system defined
by:

$\displaystyle\mathcal{C}(\mathbf{x}^{\prime},e_{j})\leq\frac{1}{2}$
$\displaystyle\quad\text{for every $j\in[n]$};$
$\displaystyle\mathbf{x}^{\prime}(i)\geq 0$ $\displaystyle\quad\text{for every
$i\in\mathrm{supp}(\mathbf{x}^{*})$};$ $\displaystyle\mathbf{x}^{\prime}(i)=0$
$\displaystyle\quad\text{for every $i\notin\mathrm{supp}(\mathbf{x}^{*})$};$
$\displaystyle\sum_{i}\mathbf{x}^{\prime}(i)=1.$

∎

Next we focus on Case 3(c), whose correctness seems less intuitive compared to
the other two cases. In order to argue about the correctness of the algorithm,
we will focus on the subgame $(R_{\mathbf{x}^{*}},C_{\mathbf{x}^{*}})$ of
$(R,C)$ that has size $|\mathrm{supp}(\mathbf{x}^{*})|\times n$. More
specifically, in $(R_{\mathbf{x}^{*}},C_{\mathbf{x}^{*}})$ the row player will
be constrained to use only pure strategies in $\mathrm{supp}(\mathbf{x}^{*})$,
while the column player will be allowed to choose from her complete set of
pure strategies. Then, we will prove that the bimatrix game
$(R_{\mathbf{x}^{*}},C_{\mathbf{x}^{*}})$ possesses a Nash equilibrium
$(\mathbf{x},\mathbf{y})$ where both players get payoff at least
$\frac{1}{2}$.

######  Lemma 5.

If Algorithm 1 reaches Case 3(c), then for every equilibrium profile
$(\mathbf{x},\mathbf{y})$ of the bimatrix game
$(R_{\mathbf{x}^{*}},C_{\mathbf{x}^{*}})$, it holds that
$\mathcal{R}(\mathbf{x},\mathbf{y})>1/2$ and
$\mathcal{C}(\mathbf{x},\mathbf{y})>1/2$.

###### Proof.

Let $(\mathbf{x},\mathbf{y})$ be a Nash equilibrium of the bimatrix game
$(R_{\mathbf{x}^{*}},C_{\mathbf{x}^{*}})$. Firstly, we will prove that
$\mathcal{R}(\mathbf{x},\mathbf{y})>1/2$. Since the algorithm has reached Case
3(c), it must be true that $\mathcal{R}(\mathbf{x}^{*},\mathbf{y}^{*})>1/2$.
Thus, from Observation 1, we get that
$\mathcal{R}(\mathbf{x}^{*},\mathbf{y})>1/2$ for every possible $\mathbf{y}$.
Hence, it must be true that $\mathcal{R}(\mathbf{x},\mathbf{y})>1/2$ since
otherwise the row player could deviate to $\mathbf{x}^{*}$, which is a valid
strategy for the game $(R_{\mathbf{x}^{*}},C_{\mathbf{x}^{*}})$, and increase
her payoff; this would contradict the assumption that
$(\mathbf{x},\mathbf{y})$ is a Nash equilibrium.

Before we prove that $\mathcal{C}(\mathbf{x},\mathbf{y})>\frac{1}{2}$, we will
prove an intermediate claim. Consider the zero-sum game
$(-C_{\mathbf{x}^{*}},C_{\mathbf{x}^{*}})$ and let
$(\tilde{\mathbf{x}},\tilde{\mathbf{y}})$ be a Nash equilibrium for this game.
We argue that

$\displaystyle\mathcal{C}(\tilde{\mathbf{x}},\tilde{\mathbf{y}})>\frac{1}{2}.$
(1)

For the sake of contradiction, assume that
$\mathcal{C}(\tilde{\mathbf{x}},\tilde{\mathbf{y}})\leq\frac{1}{2}$. Then,
since $(\tilde{\mathbf{x}},\tilde{\mathbf{y}})$ is a Nash equilibrium of the
game $(-C_{\mathbf{x}^{*}},C_{\mathbf{x}^{*}})$, we get that
$\mathcal{C}(\tilde{\mathbf{x}},e_{j})\leq\frac{1}{2}$ for every $j\in[n]$.
But this would mean that Algorithm 1 satisfies the conditions from Case 3(b)
and contradicts the fact that the algorithm reached Case 3(c).

Now we are ready to prove that
$\mathcal{C}(\mathbf{x},\mathbf{y})>\frac{1}{2}$. To obtain a contradiction,
assume that $\mathcal{C}(\mathbf{x},\mathbf{y})\leq\frac{1}{2}$. From Equation
(1) and Observation 1, we get that
$\mathcal{C}(\mathbf{x},\tilde{\mathbf{y}})>\frac{1}{2}$. Hence the column
player can deviate from $\mathbf{y}$ to $\tilde{\mathbf{y}}$ and increase her
payoff. But this would contradict the assumption that
$(\mathbf{x},\mathbf{y})$ is a Nash equilibrium of the game
$(R_{\mathbf{x}^{*}},C_{\mathbf{x}^{*}})$. ∎

In addition to Lemma 5, we will need the following lemma that uses $k$-uniform
sampled strategies for constant values of $k$, which was proved in [15].

######  Lemma 6 (Theorem 2 from [15]).

Let $(\mathbf{x},\mathbf{y})$ be a Nash equilibrium for a bimatrix game
$(R,C)$. Then, for any constant $\delta>0$, there exists a
$\kappa(\delta)$-uniform strategy profile $(\mathbf{x}_{s},\mathbf{y}_{s})$,
with
$\kappa(\delta)=\left\lceil\frac{2\ln{(1/\delta)}}{\delta^{2}}\right\rceil$,
where $\mathbf{x}_{s}$ is sampled from $\mathbf{x}$, and $\mathbf{y}_{s}$ is
sampled from $\mathbf{y}$ such that:

  1. 1.

$\mathcal{R}(e_{i},\mathbf{y}_{s})\geq\mathcal{R}(\mathbf{x},\mathbf{y})-\delta$,
for every $i\in\mathrm{supp}(\mathbf{x}_{s})$;

  2. 2.

$\mathcal{C}(\mathbf{x}_{s},e_{j})\geq\mathcal{C}(\mathbf{x},\mathbf{y})-\delta$,
for every $j\in\mathrm{supp}(\mathbf{y}_{s})$;

Lemma 6 tells us two things that are useful for our purposes. Firstly, Points
1-2 provide an approximation guarantee for the strategy profile
$(\mathbf{x}_{s},\mathbf{y}_{s})$ as a well-supported NE. Then, the fact that
both $\mathbf{x}_{s}$ and $\mathbf{y}_{s}$ are $\kappa(\delta)$-uniform tells
us that we can find this profile by enumeration in polynomial time. The lemma
below summarizes the above and it completes the proof of correctness of our
algorithm.

######  Lemma 7 (Case 3(c)).

If Algorithm 1 reaches Case 3(c), then we can compute in polynomial time a
$\kappa(\delta)$-uniform strategy profile $(\mathbf{w},\mathbf{z})$, with
$\kappa(\delta)=\left\lceil\frac{2\ln{(1/\delta)}}{\delta^{2}}\right\rceil$,
that is a $(\frac{1}{2}+\delta)$-WSNE for the game $(R,C)$.

###### Proof.

The proof of the lemma follows from the combination of Lemma 5 and Lemma 6.
From Lemma 5, we get that there exists a strategy profile
$(\mathbf{x},\mathbf{y})$, that is a Nash equilibrium for the subgame
$(R_{\mathbf{x}^{*}},C_{\mathbf{x}^{*}})$, and additionally under this
strategy profile both players get payoff at least $\frac{1}{2}$. Then, Lemma
6, applied to the profile $(\mathbf{x},\mathbf{y})$ for the game
$(R_{\mathbf{x}^{*}},C_{\mathbf{x}^{*}})$, implies the existence of a strategy
profile $(\mathbf{w},\mathbf{z})$, such that:

  * •

$\mathcal{R}(e_{i},\mathbf{z})\geq\frac{1}{2}-\delta$ for every
$i\in\mathrm{supp}(\mathbf{w})$ and
$\mathcal{C}(\mathbf{w},e_{j})\geq\frac{1}{2}-\delta$ for every
$j\in\mathrm{supp}(\mathbf{z})$;

  * •

$\mathrm{supp}(\mathbf{w})\subseteq\mathrm{supp}(\mathbf{x}^{*})$.

This profile satisfies all the constraints we want. Observe that the first
bullet above implies that $(\mathbf{w},\mathbf{z})$ is a
$(\frac{1}{2}+\delta)$-WSNE for the game $(R,C)$; this is straightforward to
see since the maximum payoff is at most 1. Thus, it only remains to prove that
we can compute this strategy profile in polynomial time. This is again easy to
see: there are
$O(n^{\kappa(\delta)})=n^{O\left(\frac{\ln{(1/\delta)}}{\delta^{2}}\right)}$
$\kappa(\delta)$-uniform strategy profiles, which is polynomially bounded, for
every constant $\delta>0$, and we can check if such a profile is a
$(\frac{1}{2}+\delta)$-WSNE in polynomial time. ∎

##  4 A Query Efficient Algorithm

In this section we consider the query complexity of the problem and we show
how Algorithm 1 can be converted to a query-efficient algorithm that achieves
the same approximation for well-supported Nash equilibria using $O(n\cdot\log
n)$ payoff queries.

#### Query Complexity.

In the setting, we assume that the algorithm only knows that the players will
play an $n\times n$ game $(R,C)$, but it does not know any of the payoff
entries of $R$ and $C$. The algorithm learns the payoff entries via payoff
queries: if the algorithm queries the pure strategy profile $(e_{i},e_{j})$,
it is told the payoffs $R_{ij}$ and $C_{ij}$ the players get under this
strategy profile. After each payoff query, the algorithm can perform arbitrary
computations –our algorithm will perform polynomial-time computations– in
order to decide the next strategy profile to query (if any). In the end, the
algorithm outputs a mixed strategy profile $(\mathbf{x},\mathbf{y})$. The goal
is to ensure that $(\mathbf{x},\mathbf{y})$ has a good approximation
guarantee, while keeping the number of queries as small as possible.

In order to prove our main result for this section, we will use the following
lemma, proven by Fearnley and Savani [25], which essentially shows that with
high probability we can find an $\varepsilon$-WSNE of a zero-sum game with
$O(\frac{n\cdot\log n}{\varepsilon^{4}})$ payoff queries.

######  Lemma 8.

[Corollary 5.5 from [25]] Given an $n\times n$ zero-sum game, with probability
at least $(1-n^{-\frac{1}{8}})(1-\frac{2}{n})^{2}$, we can compute an
$\varepsilon$-WSNE $(\mathbf{x},\mathbf{y})$ using $O(\frac{n\cdot\log
n}{\varepsilon^{4}})$ payoff queries.

While Lemma 8 suffices to simulate Steps 1 and 2, and Case 3(a) of Algorithm
1, there is no obvious way to implement the remaining cases in a query-
efficient way. One idea would be to perform an exhaustive search under the
constraint that we consider only the subgame
$(R_{\mathbf{x}^{*}},C_{\mathbf{x}^{*}})$, where $\mathbf{x}^{*}$ is the
strategy computed at Step 1. This would not break the correctness of the
algorithm, since from Lemmas 4 and 5 we know that it suffices to focus on this
subgame if the algorithm reaches Cases 3(b) and 3(c). This idea would indeed
allow us to simulate Case 3(b), and Case 3(c), with $O(n\cdot\log n)$ payoff
queries, if $(R_{\mathbf{x}^{*}},C_{\mathbf{x}^{*}})$ had $O(n\cdot\log n)$
payoff entries; for example, everything would work fine if
$|\mathrm{supp}(\mathbf{x}^{*})|=O(\log n)$. However, Lemma 8 does not provide
any bound on the support size of $\mathbf{x}$; in fact it may even return a
fully-mixed strategy for every player. Luckily though, we can sample an
$O(\log n)$-uniform strategy $\mathbf{x}^{*}_{s}$ that approximates well
enough $\mathbf{x}^{*}$.

We describe formally below all the adjustments that need to be done to
Algorithm 1.

Algorithm 2: Query-Efficient implementation of Algorithm 1 Input: A bimatrix
game $(R,C)$ and constants $\varepsilon,\delta\in(0,1],$ and
$\kappa(\delta)=\left\lceil\frac{2\ln{(1/\delta)}}{\delta^{2}}\right\rceil$.
Output: A $(\frac{1}{2}+3\varepsilon+\delta)$-WSNE for $(R,C)$ using
$O(\frac{n\cdot\log n}{\varepsilon^{4}})$ payoff queries. 1. Use Lemma 8 to
compute an $\varepsilon$-WSNE $(\mathbf{x}^{*},\mathbf{y}^{*})$ for the zero-
sum game $(R,-R)$. 2. Use Lemma 8 to compute an $\varepsilon$-WSNE
$(\hat{\mathbf{x}},\hat{\mathbf{y}})$ for the zero-sum game $(-C,C)$. 3. If
$\mathcal{R}(\mathbf{x}^{*},\mathbf{y}^{*})\geq\mathcal{C}(\hat{\mathbf{x}},\hat{\mathbf{y}})$,
use Lemma 1 to sample the strategy profile
$(\mathbf{x}^{*}_{s},\mathbf{y}^{*}_{s})$. Query all strategy profiles
$(e_{i},e_{j})$, with $i\in\mathrm{supp}(\mathbf{x}^{*}_{s})$, and create the
subgame $(R_{\mathbf{x}^{*}_{s}},C_{\mathbf{x}^{*}_{s}})$. (a) If
$\mathcal{R}(\mathbf{x}^{*},\mathbf{y}^{*})\leq\frac{1}{2}$, then return
$(\hat{\mathbf{x}},\mathbf{y}^{*})$. (b) Else if there exists a strategy
$\mathbf{x}^{\prime}$ such that
$\mathrm{supp}(\mathbf{x}^{\prime})\subseteq\mathrm{supp}(\mathbf{x}^{*}_{s})$
and $\mathcal{C}(\mathbf{x}^{\prime},e_{j})\leq\frac{1}{2}$ for every
$j\in[n]$, then return $(\mathbf{x}^{\prime},\mathbf{y}^{*}_{s})$. (c) Else,
exhaustively search over $\kappa(\delta)$-uniform strategy profiles of
$(R_{\mathbf{x}^{*}_{s}},C_{\mathbf{x}^{*}_{s}})$ and find a
$(\frac{1}{2}+3\varepsilon+\delta)$-WSNE of $(R,C)$. 4. Else if
$\mathcal{C}(\hat{\mathbf{x}},\hat{\mathbf{y}})>\mathcal{R}(\mathbf{x}^{*},\mathbf{y}^{*})$,
use Lemma 1 to sample the strategy profile
$(\hat{\mathbf{x}}_{s},\hat{\mathbf{y}}_{s})$. Query all strategy profiles
$(e_{i},e_{j})$, with $j\in\mathrm{supp}(\hat{\mathbf{y}}_{s})$, and create
the subgame $(R_{\hat{\mathbf{x}}_{s}},C_{\hat{\mathbf{x}}_{s}})$. (a) If
$\mathcal{C}(\hat{\mathbf{x}},\hat{\mathbf{y}})\leq\frac{1}{2}$, then return
$(\hat{\mathbf{x}},\mathbf{y}^{*})$. (b) Else if there exists a strategy
$\mathbf{y}^{\prime}$ such that
$\mathrm{supp}(\mathbf{y}^{\prime})\subseteq\mathrm{supp}(\hat{\mathbf{y}}_{s})$
and $\mathcal{R}(e_{i},\mathbf{y}^{\prime})\leq\frac{1}{2}$ for every
$i\in[n]$, then return $(\hat{\mathbf{x}}_{s},\mathbf{y}^{\prime})$. (c) Else,
exhaustively search over $\kappa(\delta)$-uniform strategy profiles of
$(R_{\hat{\mathbf{x}}_{s}},C_{\hat{\mathbf{x}}_{s}})$ and find a
$(\frac{1}{2}+3\varepsilon+\delta)$-WSNE for $(R,C)$.

######  Theorem 2.

For any constants, $\varepsilon,\delta>0$, Algorithm 2 computes in polynomial
time, and with probability at least $(1-n^{-\frac{1}{8}})(1-\frac{2}{n})^{2}$,
a $(\frac{1}{2}+3\varepsilon+\delta)$-WSNE using $O(\frac{n\cdot\log
n}{\varepsilon^{4}})$ payoff queries.

Note that in order to compute a $(1/2+\delta^{\prime})$-WSNE for some given
$\delta^{\prime}$, it suffices to set the constants $\varepsilon,\delta$ of
Algorithm 2, so that $\delta^{\prime}=3\varepsilon+\delta$, e.g., using
$\varepsilon=\delta=\delta^{\prime}/4$ suffices.

Before we prove Theorem 2, we state first the following simple observation,
which follows directly from the definition of $\varepsilon$-WSNE.

######  Observation 2.

Fix $\varepsilon\geq 0$, and let $(\mathbf{x}^{*},\mathbf{y}^{*})$ be an
$\varepsilon$-WSNE of the zero-sum game $(R,-R)$. Then, we have:

$\displaystyle\mathcal{R}(\mathbf{x}^{*},\mathbf{y}^{*})\geq\mathcal{R}(e_{i},\mathbf{y}^{*})-\varepsilon,~{}\forall
i\in[n],\quad$
$\displaystyle\text{and}\quad\mathcal{R}(\mathbf{x}^{*},\mathbf{y}^{*})-\varepsilon\leq\mathcal{R}(\mathbf{x}^{*},e_{j}),~{}\forall
j\in[n].$ (2)

Similarly, for any $\varepsilon$-WSNE $(\hat{\mathbf{x}},\hat{\mathbf{y}})$ of
the zero-sum game $(-C,C)$ we have:

$\displaystyle\mathcal{C}(\hat{\mathbf{x}},\hat{\mathbf{y}})-\varepsilon\leq\mathcal{C}(e_{i},\hat{\mathbf{y}}),~{}\forall
i\in[n],\quad$
$\displaystyle\text{and}\quad\mathcal{C}(\hat{\mathbf{x}},\hat{\mathbf{y}})\geq\mathcal{C}(\hat{\mathbf{x}},e_{j})-\varepsilon,~{}\forall
j\in[n].$ (3)

###### Proof of Theorem 2.

We begin by establishing the number of payoff queries the algorithm requires.
Steps 1 and 2, according to Lemma 8, require $O(\frac{n\cdot\log
n}{\varepsilon^{4}})$ queries each. In addition, Steps 3 and 4 require
$O(\frac{n\cdot\log n}{\varepsilon^{2}})$ queries each; this is because we
know from Lemma 1 that $|\mathrm{supp}(\mathbf{x}^{*}_{s})|=O(\frac{\log
n}{\varepsilon^{2}})$ and $|\mathrm{supp}(\mathbf{x}^{*}_{s})|=O(\frac{\log
n}{\varepsilon^{2}})$.

In order to prove the correctness of Algorithm 2, we will follow a similar
approach as in the proof of Theorem 1. Without loss of generality assume that
$\mathcal{R}(\mathbf{x}^{*},\mathbf{y}^{*})\geq\mathcal{C}(\hat{\mathbf{x}},\hat{\mathbf{y}})$,
hence the algorithm will proceed according to Step 3. We will distinguish
between the three possible cases.

  * •

Case 3(a) occurs. Then, using exactly the same arguments as in Lemma 3, and by
Observation 2, we get that $(\hat{\mathbf{x}},\mathbf{y}^{*})$ is a
$(\frac{1}{2}+\varepsilon)$-WSNE, since $(\mathbf{x}^{*},\mathbf{y}^{*})$ and
$(\hat{\mathbf{x}},\hat{\mathbf{y}})$ are $\varepsilon$-WSNEs and not exact
Nash equilibria.

  * •

Case 3(b) occurs. Then, we follow the proof of Lemma 4 and we get a
$\frac{1}{2}$-WSNE. This is because we are using the sampled strategy profile
$(\mathbf{x}^{*}_{s},\mathbf{y}^{*}_{s})$ which, according to Lemma 1, is a
$3\varepsilon$-WSNE. Thus, we get that $\mathbf{x}^{\prime}$ will satisfy the
constraints of a $3\varepsilon$-WSNE for the row player, while the linear
system of Lemma 4 will satisfy the constraints of a $\frac{1}{2}$-WSNE.

  * •

Case 3(c) occurs. Here, we can reprove Lemma 5, using the subgame
$(R_{\mathbf{x}^{*}_{s}},C_{\mathbf{x}^{*}_{s}})$ this time, and get that this
subgame possesses a Nash equilibrium $(\mathbf{x},\mathbf{y})$ such that
$\mathcal{R}(\mathbf{x},\mathbf{y})>\frac{1}{2}-3\varepsilon$, and
$\mathcal{C}(\mathbf{x},\mathbf{y})>\frac{1}{2}-3\varepsilon$; the loss of
$3\varepsilon$ comes from the use of the sampled strategies and Lemma 1. Then,
using verbatim the analysis of Lemma 7, we get that there exists a
$\kappa(\delta)$-uniform strategy profile in
$(R_{\mathbf{x}^{*}_{s}},C_{\mathbf{x}^{*}_{s}})$ that is a
$(\frac{1}{2}+3\varepsilon+\delta)$-WSNE for $(R,C)$.

∎

##  5 Discussion

We have presented a new algorithm for computing a $\frac{1}{2}$-well-supported
Nash equilibrium in bimatrix games. Our algorithm not only significantly
improves the previously-best approximation guarantee, but it is conceptually
much simpler and intuitive. As a byproduct, we have showed how we can convert
our main algorithm into a query-efficient protocol that achieves the same
approximation guarantee with $O(n\cdot\log n)$ queries.

Below we identify three orthogonal directions for future work.

  * •

Close the gap between polynomial-time upper bounds and the quasi-polynomial
lower bound from [41]. While we conjecture that 1/2 is not the limit of
polynomial-time tractability for $\varepsilon$-WSNE, we believe that new
techniques and ideas will be required for achieving a better approximation.
Indeed, the shifting-probabilities ideas that were used in [24] and [14] had
as a natural limit $\varepsilon=1/2$. Hence, some fresh ideas seem to be
required to go below $\frac{1}{2}$.

  * •

Prove a matching query-complexity lower bound. In [25] it was shown that any
deterministic algorithm requires $\Omega(n^{2})$ payoff queries to find an
$\varepsilon$-NE, and thus an $\varepsilon$-WSNE, for every $\varepsilon<1/2$.
Steps 1 and 2 from Algorithm 2 are randomized, thus the above-mentioned lower
bound is not binding; in [25] it has been shown that for $\varepsilon=1/6n$,
any randomized algorithm requires $\Omega(n^{2})$ queries. We conjecture that
any randomized algorithm that finds an $\varepsilon$-WSNE, with
$\varepsilon<1/2$, requires $\Omega(n^{2})$ queries.

  * •

Improve the approximation guarantee of $\varepsilon$-WSNE with polylogarithmic
communication. In the communication complexity model, introduced in [26],
every player knows her own payoff matrix, but she does not know the entries in
the payoff matrix of her opponent. The players have to follow a protocol that
works in rounds and in every round the players exchange a bit of information.
Algorithm 1 can be converted to a communication protocol that finds a
$(\frac{1}{2}+\delta)$-WSNE with $O(n\cdot\log n)$ communication, using a
similar approach as in [14]. However, there is a fundamental barrier that does
not allow us to implement it with polylogarithmic communication, which is the
desirable bound in communication complexity. Although we can implement almost
every step of the algorithm with $O(\log^{2}n)$ communication, the last step
seems to inevitably require $O(n)$ communication. In particular, the Case 3(c)
of the algorithm can be easily reduced to the so-called Disjointness problem,
which is known to be “hard” with respect to communication [40].

## References

  * [1] Bharat Adsul, Jugal Garg, Ruta Mehta, and Milind Sohoni.  Rank-1 bimatrix games: a homeomorphism and a polynomial time algorithm.  In Proceedings of STOC, pages 195–204, 2011.
  * [2] Per Austrin, Mark Braverman, and Eden Chlamtáč.  Inapproximability of NP-complete variants of Nash equilibrium.  In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, pages 13–25. Springer, 2011.
  * [3] Yakov Babichenko, Siddharth Barman, and Ron Peretz.  Empirical distribution of equilibrium play and its testing application.  Math. Oper. Res., 42(1):15–29, 2017.
  * [4] Imre Bárány, Santosh Vempala, and Adrian Vetta.  Nash equilibria in random games.  Random Structures & Algorithms, 31(4):391–405, 2007.
  * [5] Siddharth Barman.  Approximating Nash equilibria and dense subgraphs via an approximate version of Carathéodory’s theorem.  SIAM J. Comput., 47(3):960–981, 2018.
  * [6] Shant Boodaghians, Joshua Brakensiek, Samuel B. Hopkins, and Aviad Rubinstein.  Smoothed complexity of 2-player Nash equilibria.  In Proceedings of FOCS, pages 271–282, 2020.
  * [7] Hartwig Bosse, Jaroslaw Byrka, and Evangelos Markakis.  New algorithms for approximate Nash equilibria in bimatrix games.  Theoretical Computer Science, 411(1):164–173, 2010.
  * [8] Mark Braverman, Young Kun-Ko, and Omri Weinstein.  Approximating the best Nash equilibrium in _n ${}^{\mbox{o}}$_${}^{\mbox{(log \emph{n})}}$-time breaks the exponential time hypothesis.  In Proceedings of SODA, pages 970–982. SIAM, 2015.
  * [9] Xi Chen, Xiaotie Deng, and Shang-Hua Teng.  Sparse games are hard.  In Proceedings of WINE, pages 262–273, 2006.
  * [10] Xi Chen, Xiaotie Deng, and Shang-Hua Teng.  Settling the complexity of computing two-player Nash equilibria.  Journal of the ACM, 56(3), 2009.
  * [11] Xi Chen, Shang-Hua Teng, and Paul Valiant.  The approximation complexity of win-lose games.  In Proceedings of SODA, volume 7, pages 159–168, 2007.
  * [12] Bruno Codenotti and Daniel Štefankovič.  On the computational complexity of Nash equilibria for (0,1) bimatrix games.  Information Processing Letters, 94(3):145–150, 2005.
  * [13] Artur Czumaj, Argyrios Deligkas, Michail Fasoulakis, John Fearnley, Marcin Jurdzinski, and Rahul Savani.  Distributed methods for computing approximate equilibria.  CoRR, abs/1512.03315, 2015.
  * [14] Artur Czumaj, Argyrios Deligkas, Michail Fasoulakis, John Fearnley, Marcin Jurdziński, and Rahul Savani.  Distributed methods for computing approximate equilibria.  Algorithmica, 81(3):1205–1231, 2019.
  * [15] Artur Czumaj, Michail Fasoulakis, and Marcin Jurdziński.  Approximate well-supported Nash equilibria in symmetric bimatrix games.  In Proceedings of SAGT, volume 8768, pages 244–254, 2014.
  * [16] Artur Czumaj, Michail Fasoulakis, and Marcin Jurdzinski.  Zero-sum game techniques for approximate Nash equilibria.  In Proceedings of the 16th Conference on Autonomous Agents and MultiAgent Systems (AAMAS’17), pages 1514–1516, 2017.
  * [17] Constantinos Daskalakis, Paul W. Goldberg, and Christos H. Papadimitriou.  The complexity of computing a Nash equilibrium.  In Proceedings of STOC, pages 71–78, 2006.
  * [18] Constantinos Daskalakis, Aranyak Mehta, and Christos Papadimitriou.  Progress in approximate Nash equilibria.  In Proceedings of EC, pages 355–358, 2007.
  * [19] Constantinos Daskalakis, Aranyak Mehta, and Christos Papadimitriou.  A note on approximate Nash equilibria.  Theoretical Computer Science, 410(17):1581–1588, 2009.
  * [20] Argyrios Deligkas, Michail Fasoulakis, and Evangelos Markakis.  A polynomial-time algorithm for 1/3-approximate Nash equilibria in bimatrix games.  Arxiv, abs/2204.11525, 2022.
  * [21] Argyrios Deligkas, John Fearnley, Themistoklis Melissourgos, and Paul G. Spirakis.  Approximating the existential theory of the reals.  J. Comput. Syst. Sci., 125:106–128, 2022.
  * [22] Argyrios Deligkas, John Fearnley, and Rahul Savani.  Inapproximability results for constrained approximate Nash equilibria.  Inf. Comput., 262:40–56, 2018.
  * [23] Michail Fasoulakis and Evangelos Markakis.  An improved quasi-polynomial algorithm for approximate well-supported Nash equilibria.  In Proceedings of the Thirty-Third Conference on Artificial Intelligence (AAAI’19), pages 1926–1932, 2019.
  * [24] John Fearnley, Paul W. Goldberg, Rahul Savani, and Troels Bjerre Sørensen.  Approximate well-supported Nash equilibria below two-thirds.  Algorithmica, 76(2):297–319, 2016.
  * [25] 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.
  * [26] Paul W Goldberg and Arnoud Pastink.  On the communication complexity of approximate Nash equilibria.  Games and Economic Behavior, 85:19–31, 2014.
  * [27] Ravi Kannan and Thorsten Theobald.  Games of fixed rank: A hierarchy of bimatrix games.  Economic Theory, 42(1):157–173, 2010.
  * [28] Spyros C. Kontogiannis, Panagiota N. Panagopoulou, and Paul G. Spirakis.  Polynomial algorithms for approximating Nash equilibria of bimatrix games.  In Proceedings of WINE, pages 286–296, 2006.
  * [29] Spyros C. Kontogiannis and Paul G. Spirakis.  Well supported approximate equilibria in bimatrix games.  Algorithmica, 57(4):653–667, 2010.
  * [30] Spyros C. Kontogiannis and Paul G. Spirakis.  Approximability of symmetric bimatrix games and related experiments.  In Proceedings of SEA, volume 6630, pages 1–20, 2011.
  * [31] Pravesh K. Kothari and Ruta Mehta.  Sum-of-squares meets Nash: lower bounds for finding any equilibrium.  In Proceedings of STOC, pages 1241–1248. ACM, 2018.
  * [32] Richard Lipton, Evangelos Markakis, and Aranyak Mehta.  Playing large games using simple strategies.  In Proceedings of EC, pages 36–41, 2003.
  * [33] Zhengyang Liu and Ying Sheng.  On the approximation of Nash equilibria in sparse win-lose games.  In Proceedings of AAAI, volume 32, 2018.
  * [34] Andrew McLennan and Rabee Tourky.  Imitation games and computation.  Games and Economic Behavior, 70(1):4–11, 2010.
  * [35] Andrew McLennan and Rabee Tourky.  Simple complexity from imitation games.  Games and Economic Behavior, 68(2):683–688, 2010.
  * [36] Ruta Mehta.  Constant rank two-player games are PPAD-hard.  SIAM J. Comput., 47(5):1858–1887, 2018.
  * [37] Aniket Murhekar and Ruta Mehta.  Approximate Nash equilibria of imitation games: Algorithms and complexity.  In Proceedings of AAMAS, pages 887–894, 2020.
  * [38] John Nash.  Non-cooperative games.  Annals of Mathematics, 54(2):286–295, 1951.
  * [39] Panagiota N. Panagopoulou and Paul G. Spirakis.  Random bimatrix games are asymptotically easy to solve (a simple proof).  Theory of Computing Systems, 54(3):479–490, 2014.
  * [40] Tim Roughgarden et al.  Communication complexity (for algorithm designers).  Foundations and Trends® in Theoretical Computer Science, 11(3–4):217–404, 2016.
  * [41] Aviad Rubinstein.  Settling the complexity of computing approximate two-player Nash equilibria.  In Proceedings of FOCS, pages 258–265, 2016.
  * [42] Haralambos Tsaknakis and Paul G. Spirakis.  An optimization approach for approximate Nash equilibria.  Internet Mathematics, 5(4):365–382, 2008.