Breaking the 1/3 Barrier for Approximate Nash Equilibria in Symmetric Bimatrix Games

Introduction

Nash equilibrium is the standard notion of stability in strategic interaction. Nash’s theorem guarantees that every finite game admits a mixed-strategy equilibrium [2]. However, finding an equilibrium is PPAD-complete even in two-player bimatrix games [3, 4].

The hardness of computing exact equilibria has motivated the study of additive approximations. With payoffs normalized to $[0,1]$, an $\varepsilon$-approximate Nash equilibrium is a mixed-strategy profile in which neither player can gain more than $\varepsilon$ by deviating unilaterally. The small-support theorem of Lipton, Markakis, and Mehta [2003] yields a quasi-polynomial-time approximation scheme for bimatrix games. Rubinstein [2016] showed that this running time is nearly optimal under the exponential-time hypothesis for PPAD. Specifically, under this assumption, there exists a constant $\varepsilon> 0$ for which computing an $\varepsilon$-approximate Nash equilibrium of an $n \times n$ bimatrix game requires time $n^{\log^{1-o(1)} n}$. The same assumption also rules out a PTAS for general bimatrix games. This motivates the search for the smallest approximation error achievable in polynomial time.

The class of symmetric bimatrix games provides a natural setting for this question. We write $\mathcal{G} := (A, A^{\mathsf{T}})$ for a game in this class, where $A \in[0,1]^{n \times n}$ is the row player’s payoff matrix and $A^{\mathsf{T}}$ is the column player’s payoff matrix. At a pure strategy profile $(i,j)$, the row player receives $A_{ij}$ and the column player receives $A_{ji}$. Every symmetric bimatrix game admits a symmetric Nash equilibrium, in which both players use the same mixed strategy [7]. However, symmetry does not remove the hardness of exact equilibrium computation. The classical symmetrization reduction of Gale, Kuhn, and Tucker [1950], together with the PPAD-completeness of bimatrix Nash [3, 4], implies that computing a symmetric Nash equilibrium is also PPAD-complete. This motivates studying whether symmetry allows better polynomial-time approximation guarantees.

Symmetry nevertheless simplifies the approximation problem. A single mixed strategy $p$ defines the symmetric profile $(p,p)$, in which both players receive the same payoff and have the same regret, given by

Thus, finding a symmetric $\varepsilon$-approximate Nash equilibrium amounts to finding a strategy $p$ whose best-response payoff $\max_{i \in[n]} e_i^{\mathsf{T}} A p$ exceeds its self-payoff $p^{\mathsf{T}} A p$ by at most $\varepsilon$, or equivalently, $\operatorname{Reg}(p) \le\varepsilon$. Despite this simplification, achieving an approximation guarantee below $1/3$ in polynomial time had remained elusive.

The one-third frontier. For every fixed $\delta> 0$, Kontogiannis and Spirakis [2011] gave a polynomial-time algorithm that computes a symmetric $(1/3+\delta)$-approximate Nash equilibrium. Their quadratic-programming formulation also yields an approximate equilibrium with regret strictly below $1/3$ given an exact KKT point. However, their polynomial-time algorithm computes only an approximate KKT point and guarantees $1/3+\delta$. Ahnadi and Zhang [2021] later showed that a rank-two solution of an SDP relaxation can be rounded to a $1/3$-approximate Nash equilibrium for a symmetric game. This guarantee is conditional, since the relaxation is not guaranteed to return a rank-two solution. Thus, prior to our work, the best known unconditional polynomial-time guarantee for symmetric bimatrix games remained $1/3+\delta$.

In parallel, a line of work on general bimatrix games steadily improved polynomial-time approximation guarantees. Early work by Daskalakis, Mehta, and Papadimitriou [2006] established a $1/2$ guarantee, followed by the $(3-\sqrt{5})/2 \approx0.38197$ guarantee of Daskalakis, Mehta, and Papadimitriou [2007] and the $1/2 - 1/(3\sqrt{6}) \approx0.36392$ guarantee of Bosse, Byrka, and Markakis [ [12]. Tsaknakis and Spirakis [ [13] developed an optimization-based approach achieving $0.3393 + \delta$, which Deligkas, Fasoulakis, and Markakis [ [14] later refined to $1/3 + \delta$ for every bimatrix game. Symmetric games had reached the $1/3 + \delta$ guarantee more than a decade earlier, but no unconditional polynomial-time algorithm was known to break the $1/3$ barrier for either class. Thus, prior to our work, $1/3 + \delta$ remained the best known unconditional polynomial-time guarantee for both general and symmetric bimatrix games.

Our contribution. We give the first unconditional polynomial-time algorithm that breaks the $1/3$ approximation barrier for symmetric bimatrix games. One concrete instantiation computes a symmetric $3/10$-approximate Nash equilibrium. More generally, for every fixed $\delta> 0$, an algorithm in our family computes a symmetric $\varepsilon$-approximate Nash equilibrium with

where $1 - 1/\sqrt{2} \approx0.29289 < 1/3$. The algorithm returns a single mixed strategy $p$, yielding the symmetric profile $(p,p)$. Thus, our result improves the best known unconditional polynomial-time approximation guarantee for symmetric bimatrix games from $1/3 + \delta$ to $1 - 1/\sqrt{2} + \delta$.

Unlike previous approaches based on quadratic programming or descent methods, our algorithm uses auxiliary zero-sum games as its only optimization subroutines. We begin with the saddle-gap game $S$, an auxiliary zero-sum game in which the row player chooses an ordered pair $(i,j)$, the column player chooses a pure strategy $k$, and the payoff is $A_{ik} - A_{kj}$. If the value $v$ of $S$ is at most $\varepsilon$, an optimal column strategy yields a symmetric $\varepsilon$-approximate Nash equilibrium. Otherwise, the first marginal $a$ of an optimal row strategy of $S$ has self-payoff at least $2v$ and earns at least $v$ against any opponent strategy. The self-payoff bound alone recovers the one-third benchmark of Kontogiannis and Spirakis [ [1]. The second bound allows us to control the self-payoff when modifying $a$, providing the additional information needed to improve on this guarantee.

Our main technical contribution is an amortized repair procedure built around a sequence of further auxiliary zero-sum games. At iteration $t$, the algorithm identifies the near-best-response set $B_t$ of the current strategy $p_t$ and solves the restricted zero-sum game $B_t$ on $B_t \times B_t$, with payoffs inherited from $A$. If its value is at least $1-\varepsilon$, an optimal row strategy directly yields a symmetric $\varepsilon$-approximate Nash equilibrium. Otherwise, an optimal column strategy provides a repair direction that controls the payoffs of the near-best responses. The remaining strategies have enough slack to stay controlled after the update, while the guarantee inherited from $S$ helps preserve the self-payoff. Our amortized analysis shows how to balance these effects over successive repairs. A single repair already achieves $\sqrt{7}/2 - 1 \approx0.32288$, breaking the $1/3$ barrier. Repeated repairs yield the concrete $3/10$ guarantee and approach $1 - 1/\sqrt{2}$ in the limit.

Our Results

Our main theorem gives a two-parameter family of algorithms. The parameter $K$ bounds the number of repair steps, while $m$ determines the repair weights $\alpha_t := 1/(m+t)$.

The algorithm solves the auxiliary zero-sum game $S$, with $n^2$ row actions and $n$ column actions, followed by at most $K$ restricted zero-sum games $B_t$, each with at most $n$ actions per player.

The theorem gives a concrete improvement over the $1/3$ guarantee with only a finite number of repairs. In particular, choosing $K = 13$ and $m = 14$ yields $\varepsilon_{13,14} = 3/10$, using at most 13 repair steps.

The guarantee improves further as the number of repairs increases. Taking $K \to\infty$ with $m/K \to1/\sqrt{2}$ yields $\varepsilon_{K,m} \to1 - 1/\sqrt{2} \approx0.29289$. Since $K$ and $m$ can be chosen as constants depending only on $\delta$, this gives the following polynomial-time guarantee.

The improvement begins with a single repair, which achieves $\sqrt{7}/2 - 1 \approx0.32288$ with a suitable choice of weight. The multi-repair analysis builds on this idea by preserving and exploiting the payoff guarantee from $S$ across successive repairs, leading to the stronger bounds in Theorem 1.1.

Technical Overview and Proof Strategy

The algorithm maintains a single mixed strategy that is updated through successive repairs. Throughout this overview, we denote the current strategy by $p$, corresponding to $p_t$ at iteration $t$ in the formal algorithm.

Saddle-gap game. We begin with the auxiliary zero-sum game $S$, which we call the saddle-gap game. Its row player chooses an ordered pair $(i,j)$, its column player chooses a pure strategy $k$, and the row player’s payoff is $A_{ik} - A_{kj}$. For a mixed column strategy $x$ of $S$, the row player’s best-response payoff is

This quantity upper-bounds the regret of the symmetric profile $(x,x)$ in the original game $G$, since $x^{\mathsf T} A x \ge\min_j x^{\mathsf T} A e_j$. In particular, if the value $v$ of $S$ is at most $\varepsilon$, an optimal column strategy $x$ of $S$ satisfies

Thus, $(x,x)$ is a symmetric $\varepsilon$-approximate Nash equilibrium of $G$.

Suppose now that $v > \varepsilon$. Let $\sigma$ be an optimal row strategy of $S$, with first and second marginals $a$ and $b$. By the maximin property of $\sigma$, for every $k \in[n]$,

Since all payoffs are nonnegative, $a^{\mathsf T} A e_k \ge v$ for every $k$. Averaging the same inequality over $k \sim a$ and $k \sim b$ gives

We initialize the repair procedure at $p_0 := a$. Since all payoffs are at most one, these bounds give

The regret bound alone already recovers the one-third guarantee of Kontogiannis and Spirakis [2011], since $1 - 2\varepsilon= \varepsilon$ when $\varepsilon= 1/3$. To improve on this guarantee, we exploit the additional property $p_0^{\mathsf{T}}Ae_j \ge v > \varepsilon$ for every $j \in[n]$. This lower bound also holds against any mixed column strategy, allowing us to control the self-payoff during repairs. Our analysis tracks how much of this guarantee is preserved across successive updates.

A generic repair step. Consider a current strategy $p$ and a repair weight $\alpha\in(0,1)$. The algorithm seeks a strategy $z$ to mix with $p$, assigning it weight $\alpha$. To identify the rows that need to be controlled directly, we define the near-best-response set

The set $B$ contains every best response to $p$. Rows outside $B$ have a payoff gap against $p$ that will help control their payoffs after the update.

We solve the auxiliary zero-sum game $\mathcal{B}$ with row and column action sets $B$ and payoff matrix $A_{B,B}$. If its value is at least $1-\varepsilon$, minimax gives a strategy $w \in\Delta(B)$ such that

Since $w$ is supported on $B$, we have $w^{\mathsf{T}}Aw \ge1-\varepsilon$. Every pure deviation earns at most one, so $\operatorname{Reg}(w) \le\varepsilon$. The algorithm therefore stops and outputs the symmetric $\varepsilon$-approximate Nash equilibrium $(w,w)$ of $\mathcal{G}$.

Otherwise, an optimal column strategy $z \in\Delta(B)$ of $\mathcal{B}$ satisfies

We use $z$ as a repair direction and update $p$ to

The choice of the near-best-response window in (2) ensures that every pure row has a controlled payoff against $p^+$. If $i \in B$, the minimax guarantee for $z$ gives

If $i \notin B$, the definition of $B$ and the upper bound $e_i^{\mathsf{T}}Az \le1$ instead give

The right-hand sides of (4) and (5) coincide. This explains the width $\alpha\varepsilon/(1-\alpha)$ in (2) and yields

Tracking regret through repairs. The preceding argument bounds the best-response payoff against $p^+$. To bound the regret of $(p^+,p^+)$ in $G$, we also need to control its self-payoff. For this purpose, we track two bounds for the current strategy $p$, namely a regret budget $R$ and a lower bound $L$ on its payoff against every pure column strategy,

Using the update in (3), we expand the self-payoff of the repaired strategy as

Both cross terms in $p^{\mathsf{T}}Az+z^{\mathsf{T}}Ap$ admit useful lower bounds. Since $z$ is supported on the near-best-response set $B$, we have

Moreover, since $p^{\mathsf{T}}Ae_j\ge L$ for every pure column strategy $j$, we also have

Combining these bounds with the best-response estimate from the preceding paragraph and using $z^{\mathsf{T}}Az\ge0$, we obtain

The contribution of the previous regret is scaled by $(1-\alpha)^2$, while the term $-\alpha(1-\alpha)L$ reflects the lower bound on $p^{\mathsf{T}}Az$.

The same repair preserves part of this lower bound for subsequent iterations. Indeed, since all payoffs are nonnegative,

Thus, each repair provides a new regret bound while preserving a fraction of the payoff guarantee needed for the next step. This allows the procedure to be repeated, with the remaining bound contributing to the analysis of subsequent repairs.

From one repair to amortized repairs. As a warm-up, we analyze the single-repair algorithm in § 5 by applying (6) once. Starting from the saddle-gap marginal $a$, we use the initial budgets $R:=1-2\varepsilon$ and $L:=\varepsilon$. For the repaired strategy $p^+=(1-\alpha)a+\alpha z$, the one-step inequality gives

To ensure that the regret is at most $\varepsilon$, it suffices to choose

Minimizing the right-hand side over $\alpha\in(0,1)$ shows that a single repair suffices to compute a symmetric $\varepsilon$-approximate Nash equilibrium with $\varepsilon=\sqrt{7}/2-1\approx0.32288$, already below the $1/3$ benchmark.

We now extend the single-repair procedure to multiple repairs. The key observation is that the payoff lower bound against every pure column strategy is partially preserved after each update, allowing us to use it again in subsequent repairs. Whenever iteration $t$ reaches the repair branch, the restricted zero-sum game $B_t$ provides a repair direction $z_t$. We choose the weights $\alpha_t := 1/(m+t)$ and update

To analyze these updates, let $R_t$ and $L_t$ denote the regret and column-floor budgets for $p_t$, respectively. Applying the one-step bounds at each repair gives

with initial values $R_0 := 1-2\varepsilon$ and $L_0 := \varepsilon$, as guaranteed by the saddle-gap certificate. The chosen repair weights make both recurrences telescope. The floor recurrence gives

Substituting this expression into the regret recurrence and multiplying by $(m+t)^2$ yields

Summing over $t=0,1,\ldots,K-1$ cancels the intermediate scaled regret terms, leaving only scaled versions of the initial regret $(m-1)^2R_0$ and final regret $(m+K-1)^2R_K$. Choosing $\varepsilon$ so that the final regret budget satisfies $R_K=\varepsilon$ yields exactly $\varepsilon=\varepsilon_{K,m}$ in (1).

Consequently, after at most $K$ repairs, the algorithm computes a symmetric $\varepsilon_{K,m}$-approximate Nash equilibrium of $G$. In particular, choosing $K=13$ and $m=14$ gives $\varepsilon_{13,14}=3/10$, yielding a symmetric $3/10$-approximate Nash equilibrium. Moreover, taking $K\to\infty$ with $m/K\to1/\sqrt{2}$ gives $\varepsilon_{K,m}\to1-1/\sqrt{2}$. Thus, for every fixed $\delta>0$, we obtain a polynomial-time algorithm that computes a symmetric $(1-1/\sqrt{2}+\delta)$-approximate Nash equilibrium.

Related Work

Computing an exact Nash equilibrium is PPAD-complete [3, 4]. The symmetrization reduction of Gale, Kuhn, and Tucker [ [8] extends this hardness to computing symmetric equilibria in symmetric bimatrix games. For approximate equilibria, Lipton, Markakis, and Mehta [ [5] established the existence of $\varepsilon$-approximate equilibria with logarithmic support, yielding an $n^{O(\log n/\varepsilon^2)}$-time algorithm. Rubinstein [ [6] showed that, under the exponential-time hypothesis for PPAD, computing an $\varepsilon$-approximate Nash equilibrium for some constant $\varepsilon>0$ requires time $n^{\log^{1-o(1)}n}$. These results motivate the study of approximation guarantees achievable in polynomial time.

For symmetric bimatrix games, Kontogiannis and Spirakis [ [1] developed a quadratic-programming formulation whose exact KKT points yield approximate equilibria with regret strictly below $1/3$. Given such a point, the corresponding approximate equilibrium can be recovered efficiently. Their polynomial-time algorithm computes an approximate KKT point and guarantees a symmetric $(1/3+\delta)$-approximate Nash equilibrium for every fixed $\delta> 0$. Thus, the sub-third guarantee requires access to an exact KKT point, while the unconditional polynomial-time guarantee remains $1/3+\delta$.

Ahmadi and Zhang [ [9] subsequently studied an SDP relaxation of a quadratic formulation for Nash equilibria in bimatrix games. A rank-one solution yields an exact Nash equilibrium, while a rank-two solution can be rounded to a $1/3$-approximate Nash equilibrium for a symmetric game. Since the relaxation is not guaranteed to return a solution of rank at most two, this guarantee is conditional. The algorithm of Deligkas, Fasoulakis, and Markakis [ [14] achieves a $(1/3+\delta)$-approximate Nash equilibrium for every fixed $\delta> 0$ in general bimatrix games and therefore also applies to symmetric games. However, even when the input game is symmetric, their algorithm does not require both players to use the same mixed strategy. Consequently, the resulting approximate Nash equilibrium is not guaranteed to be symmetric. To the best of our knowledge, our algorithm is the first unconditional polynomial-time algorithm to compute a symmetric $\varepsilon$-approximate Nash equilibrium with $\varepsilon< 1/3$ for every symmetric bimatrix game.

The polynomial-time approximation frontier for arbitrary bimatrix games has advanced through a long sequence of results. Kontogiannis, Panagopoulou, and Spirakis [ [15] gave an early $3/4$-approximation. Daskalakis, Mehta, and Papadimitriou [ [10] improved this to $1/2$, followed by the $(3-\sqrt{5})/2 \approx0.38197$ guarantee of Daskalakis, Mehta, and Papadimitriou [ [11]. Bosse, Byrka, and Markakis [ [12] improved the guarantee to $1/2-1/(3\sqrt{6}) \approx0.36392$. Using a descent method for a nonconvex regret objective, Tsaknakis and Spirakis [ [13] achieved $0.3393+\delta$, which remained the best known guarantee for roughly fifteen years. Deligkas, Fasoulakis, and Markakis [ [14] later refined this approach to obtain a $(1/3+\delta)$-approximate Nash equilibrium for every fixed $\delta> 0$. Our result improves on this guarantee for symmetric bimatrix games while also ensuring that the output is a symmetric approximate Nash equilibrium.

An $\varepsilon$-well-supported Nash equilibrium ($\varepsilon$-WSNE) requires every pure strategy played with positive probability by either player to be within $\varepsilon$ of a best response. This is stronger than an ordinary $\varepsilon$-approximate Nash equilibrium, which only bounds each player’s gain from a unilateral deviation. For general bimatrix games, Kontogiannis and Spirakis [ [16] gave a polynomial-time $2/3$-WSNE algorithm. Fearnley, Goldberg, Savani, and Sørensen [ [17] improved the guarantee to approximately $0.6608$, and Czumaj, Deligkas, Fasoulakis, Fearnley, Jurdziński, and Savani [ [18] obtained $0.6528$. Deligkas, Fasoulakis, and Markakis [ [19] later achieved a $1/2$-WSNE guarantee in polynomial time for every bimatrix game.

For symmetric bimatrix games, Czumaj, Fasoulakis, and Jurdziński [ [20] gave a polynomial-time $(1/2+\delta)$-WSNE algorithm. In subsequent work, Czumaj, Fasoulakis, and Jurdziński [ [21] developed an algorithm for arbitrary bimatrix games that outputs either a $1/3$-approximate Nash equilibrium or a $1/2$-WSNE. Since a $1/2$-WSNE only guarantees ordinary regret at most $1/2$, this does not provide a uniform $1/3$-approximation guarantee for ordinary Nash equilibrium.

These WSNE results are complementary to our work, as they address a stronger notion of equilibrium. Their guarantees do not improve the $1/3$ benchmark for ordinary approximate Nash equilibria. Our algorithm breaks this benchmark for symmetric bimatrix games while returning a symmetric profile.

Preliminaries

Let $[n] := \{1,\ldots,n\}$, and let $\Delta_n$ denote the simplex of probability distributions over $[n]$. For any nonempty set $S \subseteq[n]$, we write $\Delta(S)$ for the distributions supported on $S$. We denote by $e_i$ the $i$th standard basis vector, identified with pure strategy $i$. Throughout, we assume that the input payoff matrices have entries in $[0,1]$.

A bimatrix game with $n$ strategies per player is specified by a pair $(R,C)$ of payoff matrices. At a mixed-strategy profile $(x,y) \in\Delta_n \times\Delta_n$, the row and column players receive payoffs $x^{\mathsf{T}}Ry$ and $x^{\mathsf{T}}Cy$, respectively. Their corresponding regrets are

A profile is an $\varepsilon$-approximate Nash equilibrium if both players have regret at most $\varepsilon$.

For the symmetric input game $\mathcal{G} = (A,A^{\mathsf{T}})$, both players receive the same payoff $p^{\mathsf{T}}Ap$ at a symmetric profile $(p,p)$. Moreover, the column player’s payoff from deviating to pure strategy $j$ is

which equals the row player’s payoff from the same deviation. Thus, both players have the same regret at any symmetric profile, as formalized in the following lemma.

Proof. At $(p,p)$, both players receive payoff $p^{\mathsf{T}}Ap$ and have the same best-response payoff $\max_{i \in[n]} e_i^{\mathsf{T}}Ap$. Their common regret is therefore $\operatorname{Reg}(p)$, and the claim follows.

We also use the finite minimax theorem in the following form for the auxiliary zero-sum games considered in our algorithms.

Proof. The claim follows from the finite minimax theorem [22]. Optimal strategies for both players can be computed by linear programming.

The Saddle-Gap Game

Given the symmetric game $\mathcal{G} = (A,A^{\mathsf{T}})$, we define an auxiliary zero-sum game $\mathcal{S}$, called the saddle-gap game. Its row player chooses an ordered pair $(i,j) \in[n]^2$, its column player chooses a pure strategy $k \in[n]$, and its payoff matrix $H \in\mathbb{R}^{n^2 \times n}$ is defined by

For a mixed column strategy $x \in\Delta_n$, the row player’s best-response payoff in $\mathcal{S}$ is

This quantity upper-bounds the regret of the symmetric profile $(x,x)$ in $\mathcal{G}$, since $x^{\mathsf{T}}Ax \ge\min_j x^{\mathsf{T}}Ae_j$.

Let $v$ denote the value of $S$. By the minimax theorem,

Let $x \in\Delta_n$ be an optimal column strategy and $\sigma\in\Delta_{n^2}$ an optimal row strategy of $S$. We denote the first and second marginals of $\sigma$ by $a,b \in\Delta_n$, respectively, where

The value $v$ determines how the algorithm proceeds. If $v \le\varepsilon$, the optimal column strategy $x$ already yields an approximate equilibrium. Otherwise, the row strategy $\sigma$ provides the initial guarantees needed for the repair procedure.

When $v > \varepsilon$, the bounds in Lemma 4.2 give the initial regret and payoff guarantees used by the repair algorithms.

Warm-up: The Single-Repair Algorithm

We begin with the single-repair algorithm, which uses the saddle-gap certificate and at most one restricted zero-sum game. Its analysis shows how the near-best-response set and the payoff guarantee from $S$ together yield an approximation factor below $1/3$. The same estimates will be used later in § 6 and § 7 for successive repairs in the amortized algorithm.

Fix a repair weight $\alpha\in(0,1)$ and define

Proof. Fix $\alpha\in(0,1)$ and write $\varepsilon:= \varepsilon(\alpha)$. We first verify the branches in which the algorithm returns a strategy without performing a repair. If the saddle-gap game $S$ has value at most $\varepsilon$, the output $(x,x)$ is correct by Lemma 4.1. Otherwise, the algorithm checks the regret of the first marginal $a$ of an optimal row strategy of $S$. If this regret is at most $\varepsilon$, it returns $(a,a)$, which is correct by Lemma 3.1.

The algorithm next forms the near-best-response set

and solves the restricted zero-sum game $\mathcal{B}$ on $B \times B$. If the value of $\mathcal{B}$ is at least $1-\varepsilon$, an optimal row strategy $w \in\Delta(B)$ satisfies

Algorithm 1 Saddle-Gap Algorithm with Single Repair

Require: A symmetric game $G = (A, A^{\mathsf{T}})$ with $A \in[0,1]^{n \times n}$ and a repair weight $\alpha\in(0,1)$

1. Set $\varepsilon:= \varepsilon(\alpha)$.

2. Solve the saddle-gap game $S$ with payoff matrix $H$ and value

3. Let $x$ and $\sigma$ be optimal column and row strategies of $S$, respectively, and let $a,b$ be the marginals of $\sigma$.

4. if $v \le\varepsilon$ then

5. &nbsp;&nbsp;&nbsp;&nbsp;return $(x,x)$

6. end if

7. if $\max_{i \in[n]} e_i^{\mathsf{T}}Aa - a^{\mathsf{T}}Aa \le\varepsilon$ then

8. &nbsp;&nbsp;&nbsp;&nbsp;return $(a,a)$

9. end if

10. Define the near-best-response set

11. Solve the restricted zero-sum game $B$ with row and column action sets $B$ and payoff matrix $A_{B,B}$. Its value is

12. if $\rho\ge1-\varepsilon$ then

13. &nbsp;&nbsp;&nbsp;&nbsp;Compute $w \in\Delta(B)$ satisfying

14. &nbsp;&nbsp;&nbsp;&nbsp;return $(w,w)$

15. else

16. &nbsp;&nbsp;&nbsp;&nbsp;Compute $z \in\Delta(B)$ satisfying

17. &nbsp;&nbsp;&nbsp;&nbsp;Set $p^+ := (1-\alpha)a + \alpha z$.

18. &nbsp;&nbsp;&nbsp;&nbsp;return $(p^+,p^+)$

19. end if

Since $w$ is supported on $B$,

Every pure deviation in $G$ earns at most one, so $\operatorname{Reg}(w) \le\varepsilon$. Hence the output $(w,w)$ is also a symmetric $\varepsilon$-approximate Nash equilibrium.

It remains to analyze the repair branch, in which the value of $B$ is below $1-\varepsilon$. An optimal column strategy $z \in\Delta(B)$ then satisfies

The algorithm returns the symmetric profile $(p^+,p^+)$, where

We first bound the best-response payoff against $p^+$. For $i \in B$, the minimax guarantee for $z$ gives

For $i \notin B$, the definition of $B$ gives $e_i^{\mathsf T}Aa<\max_h e_h^{\mathsf T}Aa-\alpha\varepsilon/(1-\alpha)$. Although this row may earn as much as one against $z$, we have

Thus, the restricted minimizer controls rows in $B$, while the payoff gap in the definition of $B$ controls those outside it. Both cases give the same upper bound, so

We next lower-bound the self-payoff of $p^+$. Because $z$ is supported on $B$, every row in its support is a near-best response to $a$. Consequently,

The high saddle-gap certificate also gives $\bar a^{\mathsf T}Ae_j\ge\varepsilon$ for every $j\in[n]$ by Corollary 4.3. Since $z\in\Delta(B)$, this implies

Expanding the self-payoff and using $z^{\mathsf T}Az\ge0$, we obtain

Subtracting (15) from (14) gives

We are in the high saddle-gap branch, so Corollary 4.3 gives $a^{\mathsf{T}}Aa > 2\varepsilon$. Since every pure payoff is at most one,

Substituting this bound into (16), we get

By the definition of $\varepsilon(\alpha)$ in (11),

Hence $\operatorname{Reg}(p^+) \le\varepsilon(\alpha)$, and $(p^+,p^+)$ is a symmetric $\varepsilon(\alpha)$-approximate Nash equilibrium. This proves the approximation guarantee in every branch of the algorithm.

We now optimize the repair weight. The bound just proved is at most $\varepsilon$ whenever

or equivalently,

Differentiating gives

The unique critical point in $(0,1)$ is $\alpha=(3-\sqrt{7})/2$. The derivative is negative before this point and positive after it, so the critical point minimizes $\varepsilon(\alpha)$. Substitution gives $\varepsilon((3-\sqrt{7})/2)=\frac{\sqrt{7}}{2}-1$. This completes the proof.

The one-repair analysis uses the lower bound $a^{\mathsf{T}}Az\ge\varepsilon$ to control the self-payoff of $p^+$. The update also retains part of the initial guarantee against every pure column. Indeed, for every $j\in[n]$,

where the inequalities use nonnegativity of the payoffs and Corollary 4.3. The amortized algorithm tracks this surviving guarantee and uses it in subsequent repairs.

The Saddle-Gap Algorithm with Amortized Repairs

The single-repair analysis shows that each update preserves part of the payoff guarantee obtained from $S$. We now use this property to perform a sequence of repairs, carrying the remaining guarantee from one iteration to the next.

Algorithm 2 Saddle-Gap Algorithm with Amortized Repairs

Require: A symmetric game $G = (A, A^{\mathsf T})$ with $A \in[0,1]^{n \times n}$ and integers $K \ge1$, $m \ge2$

1. Set $\varepsilon:= \varepsilon_{K,m}$.

2. Solve the saddle-gap game $S$ with payoff matrix $H$ and value

3. Let $x$ and $\sigma$ be optimal column and row strategies of $S$, respectively, and let $a,b$ be the marginals of $\sigma$.

4. if $v \le\varepsilon$ then

5. &nbsp;&nbsp;&nbsp;&nbsp;return $(x,x)$

6. end if

7. Set $p_0 := a$.

8. for $t = 0,1,\ldots,K-1$ do

9. &nbsp;&nbsp;&nbsp;&nbsp;if $\max_{i \in[n]} e_i^{\mathsf T}Ap_t - p_t^{\mathsf T}Ap_t \le\varepsilon$ then

10. &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;return $(p_t,p_t)$

11. &nbsp;&nbsp;&nbsp;&nbsp;end if

12. &nbsp;&nbsp;&nbsp;&nbsp;Define the near-best-response set

13. &nbsp;&nbsp;&nbsp;&nbsp;Solve the restricted zero-sum game $B_t$ with row and column action sets $B_t$ and payoff matrix $A_{B_t,B_t}$. Its value is

14. &nbsp;&nbsp;&nbsp;&nbsp;if $\rho_t \ge1-\varepsilon$ then

15. &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;Compute $w_t \in\Delta(B_t)$ satisfying

16. &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;return $(w_t,w_t)$

17. &nbsp;&nbsp;&nbsp;&nbsp;else

18. &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;Compute $z_t \in\Delta(B_t)$ satisfying

19. &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;Set

20. &nbsp;&nbsp;&nbsp;&nbsp;end if

21. end for

22. return $(p_K,p_K)$

Fix integers $K \ge1$ and $m \ge2$, and set $\varepsilon:= \varepsilon_{K,m}$ as in (1). As in the single-repair algorithm, we first solve the saddle-gap game $S$. If its value $v$ is at most $\varepsilon$, an optimal column strategy $x$ yields a symmetric $\varepsilon$-approximate Nash equilibrium. Otherwise, we initialize $p_0 := a$, where $a$ is the first marginal of an optimal row strategy of $S$. By Corollary 4.3, this initial strategy satisfies $\operatorname{Reg}(p_0) \le1 - 2\varepsilon$ and $p_0^\mathsf{T}Ae_j \ge\varepsilon$ for every $j \in[n]$.

The algorithm performs at most $K$ repairs, using the weights

The corresponding near-best-response window at iteration $t$ has width

At each iteration, the algorithm first checks whether $\operatorname{Reg}(p_t) \le\varepsilon$, in which case it returns $(p_t,p_t)$. Otherwise, it forms the near-best-response set $B_t$ using the window in (18) and solves the restricted zero-sum game $B_t$ with payoff matrix $A_{B_t,B_t}$ and value $\rho_t$.

If $\rho_t \ge1-\varepsilon$, an optimal row strategy $w_t \in\Delta(B_t)$ guarantees payoff at least $1-\varepsilon$ against every pure column in $B_t$. Since $w_t$ is supported on $B_t$, the algorithm can return the symmetric $\varepsilon$-approximate Nash equilibrium $(w_t,w_t)$. If $\rho_t < 1-\varepsilon$, an optimal column strategy $z_t \in\Delta(B_t)$ guarantees $e_i^\mathsf{T}Az_t \le1-\varepsilon$ for every $i \in B_t$. The algorithm uses $z_t$ as a repair direction and updates

If all $K$ repairs are completed, the algorithm returns $(p_K,p_K)$.

The decreasing repair weights preserve a portion of the column-payoff guarantee at each step. The next section shows how this guarantee controls the regret across successive repairs and establishes the approximation bound $\varepsilon_{K,m}$.

The complete procedure is given in Algorithm 2. It solves $S$, with $n^2$ row actions and $n$ column actions, followed by at most $K$ restricted zero-sum games $B_t$, each with at most $n$ actions per player.

Analysis of the Amortized Algorithm

We begin by verifying the early-return branches of Algorithm 2 and proving a one-step repair inequality. We then apply this inequality across successive iterations, solve the resulting recurrences, and use these bounds to establish the main theorem and its corollaries.

Early Termination and One-Step Repair

The low-value branch of $S$ in Line 5 of Algorithm 2 is correct by Lemma 4.1. Similarly, the explicit regret check in Line 10 is correct by Lemma 3.1. We therefore consider the remaining early-return branch, in which a restricted zero-sum game has value at least $1-\varepsilon$.

Since $w_t$ is supported on $B_t$, its self-payoff satisfies

Every pure deviation in $\mathcal{G}$ has payoff at most one. Therefore,

The claim follows from Lemma 3.1.

We now analyze the repair branch. For a current strategy $p$, we use $R$ to upper-bound its regret and $L$ to lower-bound its payoff against every pure column strategy. The following lemma establishes how these two bounds change after one repair.

Proof. We first establish the column-payoff bound of (20). For every $j \in[n]$, nonnegativity of the payoffs gives

We next upper-bound the best-response payoff against $p^+$ in (21). Consider a row $i \in B$. The restricted minimizer satisfies $e_i^{\mathsf{T}} A z \le1-\varepsilon$, so

Now consider a row $i\notin B$. By the definition of $B$,

Although this row may obtain payoff as large as one against $z$, we have

The two cases yield the same upper bound. For rows in $B$, this bound follows from the minimax guarantee for $z$. For rows outside $B$, it follows from their payoff gap against $p$. This explains the choice of the near-best-response window $\alpha\varepsilon/(1-\alpha)$. Combining (22) and (23), we obtain

We now lower-bound the self-payoff of $p^{+}$. Since $z$ is supported on $B$, every row in its support is a near-best response to $p$. Therefore,

The column-payoff bound on $p$ gives a lower bound for the other cross term. Since $z$ is a probability distribution and $p^{\mathsf{T}}Ae_j\geq L$ for every $j$,

Expanding the self-payoff of $p^{+}$, we have

Here we used $z^{\mathsf{T}} A z\geq0$, which follows from the nonnegativity of the entries of $A$.

Subtracting (25) from (24), we obtain

where the last inequality follows from (19). This proves (21).

The regret bound in (21) retains a factor $(1-\alpha)^2$ of the previous regret budget. The terms $\alpha(1-\varepsilon)$ and $\alpha^2\varepsilon$ arise from the best-response bound and the near-best-response window, while $-\alpha(1-\alpha)L$ captures the contribution of the column-payoff floor to the new self-payoff. By (20), the repaired strategy also retains a column-payoff floor of at least $(1-\alpha)L$. The next subsection uses these two bounds across successive repairs.

Amortized Regret Analysis

We now apply Lemma 7.2 to the sequence of repairs in Algorithm 2. Suppose the saddle-gap game has value $v>\varepsilon$, so the algorithm initializes $p_0=a$. By Corollary 4.3,

We track the regret of $p_t$ through an upper bound $R_t$ and its payoff against every pure column through a lower bound $L_t$. These are quantities used in the analysis. We initialize

and, for $t=0,1,\ldots,K-1$, define

Here $\alpha_t=1/(m+t)$, as defined in (17). These recurrences follow from the one-step repair bounds. The next lemma verifies that they remain valid throughout the algorithm.

Proof. At $t=0$, the claim follows from (26) and Corollary 4.3.

Suppose the claim holds at some $t<K$ and the algorithm performs a repair. The repair weight is $\alpha_t=1/(m+t)$, and by (18), the near-best-response window satisfies

Thus, Lemma 7.2 applies to the current strategy $p_t$ with regret budget $R_t$ and column-floor budget $L_t$. Its two conclusions give

where $R_{t+1}$ and $L_{t+1}$ are exactly the quantities defined in (27) and (28). The claim follows by induction. □

We next solve the budget recurrences for $L_t$ and $R_t$. The floor recurrence can be solved independently of the regret recurrence. Using $L_0=\varepsilon$ and $\alpha_t=1/(m+t)$, we obtain

In particular, $(m+t-1)L_t=\varepsilon(m-1)$ is independent of $t$. This identity allows the regret recurrence to telescope after scaling.

Proofs of the Main Results

We now combine the preceding lemmas to prove the main theorem and derive its two corollaries.

Proof. Write $\varepsilon= \varepsilon_{K,m}$. The algorithm can terminate in one of three early-return branches or after completing all $K$ repairs.

If it returns in Line 5 of Algorithm 2, the output is a symmetric $\varepsilon$-approximate Nash equilibrium by Lemma 4.1. The regret check in Line 10 is correct by Lemma 3.1, and the restricted high-value branch in Line 16 is correct by Lemma 7.1.

It remains to consider the case in which the algorithm performs all $K$ repairs and returns $(p_K,p_K)$. By Lemma 7.3,

Since Lemma 7.4 establishes that $R_K = \varepsilon_{K,m} = \varepsilon$, we have

Thus, Lemma 3.1 implies that $(p_K,p_K)$ is a symmetric $\varepsilon$-approximate Nash equilibrium.

Finally, the algorithm solves one zero-sum game $S$ with $n^2$ row actions and $n$ column actions, followed by at most $K$ restricted zero-sum games $B_t$, each with at most $n$ actions per player. All these games can be solved in polynomial time by linear programming, and the remaining operations are also polynomial-time computable. This establishes the claimed running time.

Proof. Setting $K = 13$ and $m = 14$ in (1) gives

The claim follows from Theorem 1.1.

The finite guarantee in (1) also yields an improved asymptotic approximation factor when $m$ grows proportionally to $K$. We optimize this limiting factor to obtain the following result.

Proof. Consider a sequence of integers $K,m$ such that $K \to\infty$ and $m/K \to c$ for some constant $c > 0$. Dividing the numerator and denominator of (1) by $K^2$ gives

We minimize $g$ over $c > 0$. Differentiating yields

Since the denominator is positive for $c > 0$, the derivative vanishes precisely when $4c^2 - 2 = 0$. The unique positive critical point is $c = 1/\sqrt{2}$. Moreover, $g'(c) < 0$ for $0 < c < 1/\sqrt{2}$ and $g'(c) > 0$ for $c > 1/\sqrt{2}$. Thus, this critical point is the global minimizer of $g$ over $c > 0$. Evaluating $g$ at this point gives

For each $K$, choose

Then $m/K \to1/\sqrt{2}$, and consequently

Hence, for every fixed $\delta> 0$, we can choose $K$ sufficiently large, with $m \ge2$, such that

For a fixed $\delta$, these choices of $K$ and $m$ are constants independent of the input size. By Theorem 1.1, the resulting algorithm runs in polynomial time and computes a symmetric $(1-\frac{1}{\sqrt{2}}+\delta)$-approximate Nash equilibrium.

Conclusion

We have shown that the $1/3$ approximation barrier for symmetric bimatrix games can be broken in polynomial time using auxiliary zero-sum games as the only optimization subroutines. For every fixed $\delta> 0$, our algorithm computes a symmetric $(1-1/\sqrt{2}+\delta)$-approximate Nash equilibrium for every symmetric bimatrix game. This improves upon the best currently known polynomial-time approximation guarantee for general bimatrix games.

Our analysis achieves the limiting factor $1-1/\sqrt{2}$ for the repair schedule $\alpha_t = 1/(m+t)$. Different weight schedules or more refined repair rules may lead to further improvements. One possible direction is to exploit the full joint distribution over ordered pairs in the saddle-gap solution, beyond the marginal information used by our algorithm. Understanding the hardness of computing approximate symmetric Nash equilibria and determining the optimal polynomial-time approximation threshold for this class also remain important open problems. It would also be interesting to investigate whether similar techniques can improve the $1/3$ approximation frontier for general bimatrix games. More broadly, the use of auxiliary zero-sum games to guide successive local repairs may prove useful in other approximation problems.

Acknowledgement

A.S. and P.J. were partially supported by the ONR grant N00014-24-1-2470. Part of this research was performed while A.S. was visiting the Institute for Mathematical and Statistical Innovation (IMSI), which is supported by the National Science Foundation (Grant No. DMS-2425650). G.F. was supported in part by the National Science Foundation awards CCF-2443068 and IIS-2552046, the Office of Naval Research grant N000142512296, and an AI2050 Early Career Fellowship.