Inapproximability Results for Approximate Nash Equilibria

Introduction

One of the most fundamental problems in game theory is to find a Nash equilibrium of a game. Often, we are not interested in finding any Nash equilibrium, but instead we want to find one that also satisfies certain constraints. For example, we may want to find a Nash equilibrium that provides high social welfare, which is the sum of the players’ payoffs.

In this paper we study such problems for bimatrix games, which are two-player strategic-form games. Unfortunately, for bimatrix games, it is known that these problems are hard. Finding any Nash equilibrium of a bimatrix game is $\mathtt{PPAD}$-complete , while finding a constrained Nash equilibrium turns out to be even harder. Gilboa and Zemel studied several decision problems related to Nash equilibria. They proved that it is $\mathtt{NP}$-complete to decide whether there exist Nash equilibria in bimatrix games with some “desirable” properties, such as high social welfare. Conitzer and Sandholm extended the list of $\mathtt{NP}$-complete problems of and furthermore proved inapproximability results for some of them. Recently, Garg et al. and Bilo and Mavronicolas extended these results to many player games and provided $\mathtt{ETR}$-completeness results for them.

Approximate equilibria. Due to the apparent hardness of finding exact Nash equilibria, focus has shifted to approximate equilibria. There are two natural notions of approximate equilibrium, both of which will be studied in this paper. An $\epsilon$-approximate Nash equilibrium ($\epsilon$-NE) requires that each player has an expected payoff that is within $\epsilon$ of their best response payoff. An $\epsilon$-well-supported Nash equilibrium ($\epsilon$-WSNE) requires that both players only play strategies whose payoff is within $\epsilon$ of the best response payoff. Every $\epsilon$-WSNE is an $\epsilon$-NE but the converse does not hold, so a WSNE is a more restrictive notion.

There has been a long line of work on finding approximate equilibria . Since we use an additive notion of approximation, it is common to rescale the game so that the payoffs lie in $$, which allows different algorithms to be compared. The state of the art for polynomial-time algorithms is the following. There is a polynomial-time algorithm that computes an$0.3393$-NE , and a polynomial-time algorithm that computes a$0.6528$-WSNE .

There is also a quasi-polynomial time approximation scheme (QPTAS) for finding approximate Nash equilibria. The algorithm of Lipton, Markakis, and Mehta finds an $\epsilon$-NE in $n^{O(\frac{\log n}{\epsilon^{2}})}$ time . They proved that there is always an $\epsilon$-NE with support of logarithmic size, and then they use a brute-force search over all possible candidates to find one. We will refer to their algorithm as the LMM algorithm.

A recent breakthrough of Rubinstein implies that we cannot do better than a QPTAS like the LMM algorithm : assuming an exponential time hypothesis for $\mathtt{PPAD}$ (PETH), there is a small constant, $\epsilon^{*}$, such that for $\epsilon<\epsilon^{*}$, every algorithm for finding an $\epsilon$-NE requires quasi-polynomial time. Briefly, PETH is the conjecture that EndOfTheLine, the canonical $\mathtt{PPAD}$-complete problem, cannot be solved faster than exponential time.

Constrained approximate Nash equilibria. While deciding whether a game has an exact Nash equilibrium that satisfies certain constraints is $\mathtt{NP}$-hard for most interesting constraints, this is not the case for approximate equilibria, because the LMM algorithm can be adapted to provide a QPTAS for them. The question then arises whether one can do better.

It is worth noting that the Rubinstein’s hardness result almost makes this result redundant. If one is willing to accept that PETH is true, which is a stronger conjecture than ETH, then Rubinstein’s result says that for small $\epsilon$ we require quasi-polynomial time to find any $\epsilon$-NE, which obviously implies that the same lower bound applies to $\epsilon$-NE $\delta$-SW for any $\delta$.

To understand this result, let us compare it to the BKW result. First, observe that as $\delta$ gets smaller, the $\epsilon$ in our $\epsilon$-NE gets larger, whereas in the BKW result, $\epsilon$ get smaller. Asymptotically, our $\epsilon$ approaches $1/8$. Moreover, since $\delta\leq 1$, our lower bound applies to all $\epsilon$-NE with $\epsilon\leq\frac{1-4g}{8}\approx 0.1214$. This is orders of magnitude larger than the inapproximability bound given by Rubinstein’s hardness result, and so is not made redundant by that result. In short, our hardness result is about the hardness of obtaining good social welfare, rather than the hardness of simply finding an approximate equilibrium.

Secondly, when compared to the BKW result, we obtain a slightly better lower bound. The exponent in their lower bound is logarithmic only in the limit, while ours is always logarithmic.

In this version, we show that we are able to assume only the ETH by using a stronger result that was discovered by Babichenko, Papadimitriou, and Rubinstein . Their results imply that approximating the value of a free game requires quasipolynomial time even when the size of the question sets is logarithmic in the game size. They do not explicitly formulate this result, but it is clearly implied by their techniques. For the sake of completeness, we provide an exposition of their ideas in Section 3.

The second main difference between our result and the BKW result is that we use a different starting point. The BKW result uses the PCP theorem of Moshkovitz and Raz , which provides a completeness/soundness gap of $1$ vs $\delta$ for arbitrarily small constant $\delta$ in the label cover problem. The use of this powerful PCP theorem is necessary, as their proof relies on the large completeness/soundness gap produced by that theorem. This choice of PCP theorem directly impacts the running time lower bound that they produce, as the $(\log n)^{1-o(1)}$ term in the exponent arises from the blowup of $n^{1+o(1)}$ from the PCP theorem.

One final point of comparison is the size of the payoffs used in our simulation. The zero-sum games that we use have payoffs in the range $(-4,4)$, which directly leads to the $\frac{1-4g\cdot\delta}{8}$ bound on the quality of approximation. In contrast to this, the zero-sum games used by the BKW result have payoffs of size $O(\frac{1}{\epsilon})$, which ultimately means that their lower bound only applies to the problem $\epsilon$-NE $\epsilon$-SW.

Other related work

The only positive result for finding $\epsilon$-NE with good social welfare that we are aware of was given by Czumaj, Fasoulakis, and Jurdziński . In , they showed that if there is a polynomial-time algorithm for finding an $\epsilon$-NE, then for all $\epsilon^{\prime}>\epsilon$ there is also a polynomial-time algorithm for finding an $\epsilon^{\prime}$-NE that is within a constant multiplicative approximation of the best social welfare. They also give further results for the case where $\epsilon>\frac{1}{2}$. In they derived polynomial-time algorithms that compute $\epsilon$-NE for $\epsilon\geq\frac{3-\sqrt{5}}{2}$ that approximate the quality of plutocratic and egalitarian Nash equilibria to various degrees.

Preliminaries

Throughout the paper, we use $[n]$ to denote the set of integers $\{1,2,\dots,n\}$. An $n\times n$ bimatrix game is a pair $(R,C)$ of two $n\times n$ matrices: $R$ gives payoffs for the row player and $C$ gives the payoffs for the column player.

Each player has $n$ pure strategies. To play the game, both players simultaneously select a pure strategy: the row player selects a row $i\in[n]$, and the column player selects a column $j\in[n]$. The row player then receives payoff $R_{i,j}$, and the column player receives payoff $C_{i,j}$.

Let $\mathbf{y}$ be a mixed strategy for the column player. The set of pure best responses against $\mathbf{y}$ for the row player is the set of pure strategies that maximize the payoff against $\mathbf{y}$. More formally, a pure strategy $i\in[n]$ is a best response against $\mathbf{y}$ if, for all pure strategies $i^{\prime}\in[n]$ we have: $\sum_{j\in[n]}\mathbf{y}_{j}\cdot R_{i,j}\geq\sum_{j\in[n]}\mathbf{y}_{j}\cdot R_{i^{\prime},j}$. Column player best responses are defined analogously.

Approximate Equilibria

There are two commonly studied notions of approximate equilibrium, and we consider both of them in this paper. The first notion is that of an $\epsilon$-approximate Nash equilibrium ($\epsilon$-NE), which weakens the requirement that a player’s expected payoff should be equal to their best response payoff. Formally, given a strategy profile $(\mathbf{x},\mathbf{y})$, we define the regret suffered by the row player to be the difference between the best response payoff and the actual payoff: \max_{i\in[n]}\big{(}(R\cdot y)_{i}\big{)}-\mathbf{x}^{T}\cdot R\cdot\mathbf{y}. Regret for the column player is defined analogously. We have that $(\mathbf{x},\mathbf{y})$ is an $\epsilon$-NE if and only if both players have regret less than or equal to $\epsilon$.

The other notion is that of an $\epsilon$-approximate-well-supported equilibrium ($\epsilon$-WSNE), which weakens the requirement that players only place probability on best response strategies. We say that a pure strategy $j\in[n]$ of the row player is an $\epsilon$-best-response against $\mathbf{y}$ if:

Since approximate Nash equilibria use an additive notion of approximation, it is standard practice to rescale the input game so that all payoffs lie in the range $$, which allows us to compare different results on this topic. For the most part, we follow this convention. However, for our result in Section 4, we will construct a game whose payoffs do not lie in$$. In order to simplify the proof, we will prove results about approximate Nash equilibria in the unscaled game, and then rescale the game to $$at the very end. To avoid confusion, we will refer to an$\epsilon$-approximate Nash equilibrium in this game as an$\epsilon$-UNE, to mark that it is an additive approximation in an unscaled game.

Two-prover games

A two-prover game $\mathcal{T}$ is defined by a tuple $(X,Y,A,B,\mathcal{D},V)$ where $X$ and $Y$ are finite sets of questions, $A$ and $B$ are finite sets of answers, $\mathcal{D}$ is a probability distribution defined over $X\times Y$, and $V$ is a verification function of the form $V:X\times Y\times A\times B\rightarrow\{0,1\}$.

The value of the game, denoted $\omega(\mathcal{T})$, is the maximum expected payoff to the Merlins when they play optimally:

Free games

Hardness of approximating free games

The conference version of this paper solved this issue by using a sub-sampling lemma, also proved by Aaronson, Impagliazzo, and Moshkovitz, which shows that if we randomly choose logarithmically many questions from the original game, the value of the resulting sub-game is close the value of the original. However, this comes at the cost of needing randomness in the reduction, and so our result depended on the truth of the randomized ETH, which is a stronger conjecture.

In this exposition, we will instead use a technique of Babichenko, Papadimitriou, and Rubinstein , which allows us to produce a free game with a logarithmic size question set in a deterministic way. The result that we need is a clear consequence of their ideas, but is not explicitly formulated in their paper. For the sake of completeness, in the rest of this section we provide our own exposition of their ideas.

The starting point of the result will be a 3SAT instance $\phi$. We say that the size of a formula $\phi$ is the number of variables and clauses in the formula. We define $\operatorname{SAT}(\phi)\in$ to be the maximum fraction of clauses that can be satisfied in $\phi$. The first step is to apply a PCP theorem.

Given any 3SAT instance $\phi$ of size $n$, and a constant $\epsilon$ in the range $0<\epsilon<\frac{1}{8}$, we can produce in polynomial time a 3SAT instance $\psi$ where:

The size of $\psi$ is $n\cdot\operatorname{polylog}(n)$.

Every clause of $\psi$ contains exactly 3 variables and every variable is contained in at most $d$ clauses, where $d$ is a constant.

If $\operatorname{SAT}(\phi)=1$, then $\operatorname{SAT}(\psi)=1$.

If $\operatorname{SAT}(\phi)<1$, then $\operatorname{SAT}(\psi)<1-\epsilon$.

After applying the PCP theorem given above, we then directly construct a free game. Observe that a 3SAT formula can be viewed as a bipartite graph in which the vertices are variables and clauses, and there is an edge between a variable $x_{i}$ and a clause $C_{j}$ if and only if $x_{i}$ is appears in $C_{j}$. In particular, the 3SAT formulas produced by Theorem 1 correspond to bipartite graphs with constant degree, since each clause has degree at most 3, and each variable has degree at most $d$.

The first step is to apply the following lemma, which allows us to partition the vertices of this bipartite graph. The lemma and proof are essentially identical to [23, Lemma 6], although we generalise the formulation slightly, because the original lemma requires that the two sides of the graph have exactly the same number of nodes and that the graph is $d$-regular.

Let $(V,E)$ be a bipartite graph with $|V|=n$, where $V=U\cup W$ are the two sides of the graph, and where each node has degree at most $d$. Suppose that $U$ and $W$ both have a constant fraction of the vertices, and hence $|U|=c_{1}\cdot n$ and $|W|=c_{2}=(1-c_{1})\cdot n$ for some constants $c_{1}<1$ and $c_{2}<1$. We can efficiently find a partition $S_{1},S_{2},\dots,S_{\sqrt{n}}$ of $U$ and a partition $T_{1},T_{2},\dots,T_{\sqrt{n}}$ of $W$ such that each set has size at most $2\sqrt{n}$, and for all $i$ and $j$ we have

The algorithm is as follows. First we arbitrarily split $U$ into $\sqrt{n}$ many sets $S_{1},S_{2},\dots,S_{\sqrt{n}}$, and so each set $S_{i}$ has size $c_{1}\sqrt{n}<2\sqrt{n}$. Then we iteratively construct the partition of $W$ into sets $T_{1},T_{2},\dots,T_{\sqrt{n}}$ in the following way. We initialize each set $T_{j}$ to be the empty set. In each iteration, we pick a vertex of $w\in W$ that has not already been assigned to a set. We find a set $T_{j}$ such that $|T_{j}|\leq 2\cdot\sqrt{n}$, and such that for all $i$ we have $|(S_{i}\times T_{j})\cap E|\leq 2\cdot d^{2}$. We assign $w$ to $T_{j}$ and repeat.

Obviously, for the algorithm to be correct, we must prove that for each vertex $w$ that is considered, there does exist a set $T_{j}$ that satisfies the required constraints. For this, we rely on the following two properties.

The average number of vertices in a set $T_{j}$ is at most $c_{2}\sqrt{n}<\sqrt{n}$, and so by Markov’s inequality strictly less than half the sets can have size more than $2\sqrt{n}$, and so we lose strictly less than half the sets $T_{j}$ to the size constraint.

Since each vertex has degree at most $d$, the graph has at most $dn$ edges, and so the average number of edges between each pair of sets $S_{i}$ and $T_{j}$ is $dn/(\sqrt{n}\cdot\sqrt{n})=d$. Again, using Markov’s inequality we can conclude that there are at most $1/2d$ pairs of sets $S_{i}$ and $T_{j}$ that have more than $2d^{2}$ edges between them. Hence, even in the worst case, we can lose at most $1/2d$ sets $T_{j}$ to the edge constraints.

So, we lose strictly less than half the sets to the size constraints, and $1/2d\leq 1/2$ the sets to the edge constraints. Hence, by the union bound, we have shown that there is at least one set $T_{j}$ that satisfies both constraints simultaneously. \qed

A free game

Note that Lemma 1 can be applied to the 3SAT formula that arises from Dinur’s PCP theorem, because the number of variables and number of constraints are both a constant fraction of the number of nodes in the associated bipartite graph, and because each vertex has either has degree $d$ or degree $3$. We use this to construct the following free game, which is highly reminiscent of the clause variable game given by Aaronson, Impagliazzo, and Moshkovitz .

Given a 3SAT formula $\phi$ of size $n$, we define a free game $\mathcal{F}_{\phi}$ in the following way.

If $n$ is the size of $\phi$, then when we write $\mathcal{F}_{\phi}$ down as a free game $(X,Y,A,B,\mathcal{D},V)$, the number of questions in the sets $X$ and $Y$ is $\sqrt{n\operatorname{polylog}(n)}$, and the number of answers in $A$ and $B$ is $2^{2\sqrt{n\operatorname{polylog}(n)}}$, where the extra $\operatorname{polylog}(n)$ factor arises due to the application of the PCP theorem.

The following lemma shows that if $\phi$ is unsatisfiable, then the value of this free game is bounded away from $1$. Again, the ideas used to prove this lemma are clearly evident in the work of Babichenko, Papadimitriou, and Rubinstein .

If $\phi$ is satisfiable then $\omega(\mathcal{F}_{\phi})=1$. If $\phi$ is unsatisfiable then $\omega(\mathcal{F}_{\phi})\leq 1-\epsilon/2d$.

The case where $\operatorname{SAT}(\phi)=1$ is straightforward. Since there exists a satisfying assignment for $\phi$, there also exists a satisfying assignment for $\psi$. If the two Merlins play according to this satisfying assignment, then they obviously achieve an expected payoff of $1$.

Since $\phi$ is unsatisfiable, the PCP theorem tells us that $\operatorname{SAT}(\psi)<1-\epsilon$. Thus, there are at least $\epsilon dN$ clauses that are not satisfied when $s_{1}$ is played against $s_{2}$. Since Lemma 1 ensures that the maximum number of edges between two sets is $2d^{2}$, there must therefore be at least $\epsilon dN/2d^{2}=\epsilon N/2d$ pairs of sets that give payoff to the Merlins under $s_{1}$ and $s_{2}$. Since there are exactly $N$ pairs of sets in total, this means that the expected payoff to the Merlins is bounded by $1-\epsilon/2d$. \qed

Finally, we can formulate the lower bound that we will use in this paper. The proof is the same as the one given in , but we use the free game $\mathcal{F}_{\phi}$, rather than the construction originally given in that paper.

Lemma 2 implies that if we can approximate the value of $\mathcal{F}_{\phi}$ with an additive error of less than $\epsilon/2d$, then we can solve the satisfiability problem for $\phi$.

Assume, for the sake of contradiction, that there exists an algorithm that can solve the $\textsc{FreeGame}_{\delta}$ problem in time $N^{o\left(\frac{\log N}{(\log\log N)^{c}}\right)}$ for some constant $c$ that will be fixed later. Observe that the free game $\mathcal{F}_{\phi}$ has size $N=O(2^{\sqrt{n\operatorname{polylog}(n)}})$, and so the hypothesized algorithm would run in time:

If we set $c$ to be greater than the degree of the polynomial in the $\operatorname{polylog}(n)$ from the numerator, then we can conclude that the running time would be $2^{o(n)}$, which would violate the ETH. \qed

Hardness of approximating social welfare

In this section, we study the following social welfare problem for a bimatrix game $\mathcal{G}=(R,C)$. The social welfare of a strategy profile $(\mathbf{x},\mathbf{y})$ is denoted by $\operatorname{SW}(\mathbf{x},\mathbf{y})$ and is defined to be $\mathbf{x}^{T}R\mathbf{y}+\mathbf{x}^{T}C\mathbf{y}$. Given an $\epsilon\geq 0$, we define the set of all $\epsilon$ equilibria as

Then, we define the best social welfare achievable by an $\epsilon$-NE in $\mathcal{G}$ as

Using these definitions we now define the main problem that we consider:

(Completeness) If $\omega(\mathcal{F})=1$, then the unscaled $\operatorname{BSW}(\mathcal{G},\epsilon)=2$.

(Soundness) If $\omega(\mathcal{F})<1-\delta$, then the unscaled $\operatorname{BSW}(\mathcal{G},\epsilon)<2(1-g\cdot\delta)$.

This will allow us to prove our lower bound using Theorem 2.

1 The construction

We use $\mathcal{F}$ to construct a bimatrix game, which we will denote as $\mathcal{G}$ throughout the rest of this section. The game is built out of four subgames, which are arranged and defined as follows.

III$R<span class="katex-display"><span class="katex"><span class="katex-mathml"><math xmlns="http://www.w3.org/1998/Math/MathML" display="block"><semantics><mrow><mo>−</mo><msub><mi>D</mi><mn>2</mn></msub></mrow><annotation encoding="application/x-tex">-D_{2}</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:0.8333em;vertical-align:-0.15em;"></span><span class="mord">−</span><span class="mord"><span class="mord mathnormal" style="margin-right:0.0278em;">D</span><span class="msupsub"><span class="vlist-t vlist-t2"><span class="vlist-r"><span class="vlist" style="height:0.3011em;"><span style="top:-2.55em;margin-left:-0.0278em;margin-right:0.05em;"><span class="pstrut" style="height:2.7em;"></span><span class="sizing reset-size6 size3 mtight"><span class="mord mtight"><span class="mord mtight">2</span></span></span></span></span><span class="vlist-s">​</span></span><span class="vlist-r"><span class="vlist" style="height:0.15em;"><span></span></span></span></span></span></span></span></span></span></span>C<span class="katex-display"><span class="katex"><span class="katex-mathml"><math xmlns="http://www.w3.org/1998/Math/MathML" display="block"><semantics><mrow><msub><mi>D</mi><mn>2</mn></msub></mrow><annotation encoding="application/x-tex">D_{2}</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:0.8333em;vertical-align:-0.15em;"></span><span class="mord"><span class="mord mathnormal" style="margin-right:0.0278em;">D</span><span class="msupsub"><span class="vlist-t vlist-t2"><span class="vlist-r"><span class="vlist" style="height:0.3011em;"><span style="top:-2.55em;margin-left:-0.0278em;margin-right:0.05em;"><span class="pstrut" style="height:2.7em;"></span><span class="sizing reset-size6 size3 mtight"><span class="mord mtight"><span class="mord mtight">2</span></span></span></span></span><span class="vlist-s">​</span></span><span class="vlist-r"><span class="vlist" style="height:0.15em;"><span></span></span></span></span></span></span></span></span></span></span>D_{1}$$-D_{1}$ 1. The game $(R,C)$ is built from $\mathcal{F}$ in the following way. Each row of the game corresponds to a pair $(x,a)\in X\times A$ and each column corresponds to a pair $(y,b)\in Y\times B$. Since all free games are cooperative, the payoff for each strategy pair $(x,a),(y,b)$ is defined to be $R_{(x,a),(y,b)}=C_{(x,a),(y,b)}=V(x,y,a(x),b(y)).$

The game $(D_{1},-D_{1})$ is a zero-sum game. The game is a slightly modified version of a game devised by Feder, Nazerzadeh, and Saberi . Let $H$ be the set of all functions of the form $f:Y\rightarrow\{0,1\}$ such that $f(y)=1$ for exactly halfIf $|Y|$ is not even, then we can create a new free game in which each question in $|Y|$ appears twice. This will not change the value of the free game. of the elements $y\in Y$. The game has $|Y\times B|$ columns and $|H|$ rows. For all $f\in H$ and all $(y,b)\in Y$ the payoffs are

The game $(-D_{2},D_{2})$ is built in the same way as the game $(D_{1},-D_{1})$, but with the roles of the players swapped. That is, each column of $(-D_{2},D_{2})$ corresponds to a function that picks half of the elements of $X$.

The game $(0,0)$ is a game in which both players have zero matrices.

Observe that the size of $(R,C)$ is the same as the size of $\mathcal{F}$. The game $(D_{1},-D_{1})$ has the same number of columns as $C$, and the number of rows is at most $2^{|Y|}\leq 2^{O(\log|\mathcal{F}|)}=|\mathcal{F}|^{O(1)}$, where we are crucially using the fact that Theorem 2 allows us to assume that the size of $Y$ is $O(\log|\mathcal{F}|)$. By the same reasoning, the number of columns in $(-D_{2},D_{2})$ is at most $|\mathcal{F}|^{O(1)}$. Thus, the size of $\mathcal{G}$ is $|\mathcal{F}|^{O(1)}$, and so this reduction is polynomial.

2 Completeness

To prove completeness, it suffices to show that, if $\omega(\mathcal{F})=1$, then there exists a $(1-4g\cdot\delta)$-UNE of $\mathcal{G}$ that has social welfare $2$. To do this, assume that $\omega(\mathcal{F})=1$, and take a pair of optimal strategies $(s_{1},s_{2})$ for $\mathcal{F}$ and turn them into strategies for the players in $\mathcal{G}$. More precisely, the row player will place probability $\frac{1}{|X|}$ on each answer chosen by $s_{1}$, and the column player will place probability $\frac{1}{|Y|}$ on each answer chosen by $s_{2}$. By construction, this gives both players payoff $1$, and hence the social welfare is $2$. The harder part is to show that this is an approximate equilibrium, and in particular, that neither player can gain by playing a strategy in $(D_{1},-D_{1})$ or $(-D_{2},D_{2})$. We prove this in the following lemma.

If $\omega(\mathcal{F})=1$, then there exists a $(1-4g\cdot\delta)$-UNE $(\mathbf{x},\mathbf{y})$ of $\mathcal{G}$ with $\operatorname{SW}(\mathbf{x},\mathbf{y})=2$.

Clearly, by construction, we have that the payoff to the row player under $(\mathbf{x},\mathbf{y})$ is equal to $p(\mathcal{F},s_{1},s_{2})=1$, and therefore $(\mathbf{x},\mathbf{y})$ has social welfare $2$.

On the other hand, we must prove that $(\mathbf{x},\mathbf{y})$ is a $(1-4g\cdot\delta)$-UNE. To do so, we will show that neither player has a deviation that increases their payoff by more than $(1-4g\cdot\delta)$. We will show this for the row player; the proof for the column player is symmetric. There are two types of row to consider.

First suppose that $r$ is a row in the sub-game $(R,C)$. We claim that the payoff of $r$ is at most $1$. This is because the maximum payoff in $R$ is $1$, while the maximum payoff in $-D_{2}$ is . Since the row player already obtains payoff $1$ in $(\mathbf{x},\mathbf{y})$, row $r$ cannot be a profitable deviation.

Next suppose that $r$ is a row in the sub-game $(D_{1},-D_{1})$. Since we have $\sum_{b\in B}\mathbf{y}(y,b)=\frac{1}{|Y|}$ for every question $y$, we have that all rows in $D_{1}$ have the same payoff. This payoff is

Since $\delta\leq 1$ and $g\leq\frac{1}{4}$ we have

Thus, we have shown that the payoff of $r$ is at most $2-4g\cdot\delta$. Thus the row player’s regret is at most $1-4g\cdot\delta$. \qed

3 Soundness

We now suppose that $\omega(\mathcal{F})<1-\delta/2$, and we will prove that all $(1-4g\cdot\delta)$-UNE provide social welfare at most $2-2g\cdot\delta$. Throughout this subsection, we will fix $(\mathbf{x},\mathbf{y})$ to be a $(1-4g\cdot\delta)$-UNE of $\mathcal{G}$. We begin by making a simple observation about the amount of probability that is placed on the subgame $(R,C)$.

If $\operatorname{SW}(\mathbf{x},\mathbf{y})>2-2g\cdot\delta$, then

$\mathbf{x}$ places at least $(1-g\cdot\delta)$ probability on rows in $(R,C)$, and

$\mathbf{y}$ places at least $(1-g\cdot\delta)$ probability on columns in $(R,C)$.

We will prove the lemma for $\mathbf{x}$; the proof for $\mathbf{y}$ is entirely symmetric. For the sake of contradiction, suppose that $\mathbf{x}$ places strictly less than $(1-g\cdot\delta)$ probability on rows in $(R,C)$. Observe that every subgame of $\mathcal{G}$ other than $(R,C)$ is a zero-sum game. Thus, any probability assigned to these sub-games contributes nothing to the social welfare. On the other hand, the payoffs in $(R,C)$ are at most $1$. So, even if the column player places all probability on columns in $C$, the social welfare $\operatorname{SW}(\mathbf{x},\mathbf{y})$ will be strictly less than $2\cdot(1-g\cdot\delta)+g\cdot\delta\cdot 0=2-2g\cdot\delta$, a contradiction. \qed

So, for the rest of this subsection, we can assume that both $\mathbf{x}$ and $\mathbf{y}$ place at least $1-g\cdot\delta$ probability on the subgame $(R,C)$. We will ultimately show that, if this is the case, then both players have payoff at most $1-\frac{1}{2}\cdot\delta+mg\cdot\delta$ for some constant $m$ that will be derived during the proof. Choosing $g=1/(2m+2)$ then ensures that both players have payoff at most $1-g\cdot\delta$, and therefore that the social welfare is at most $2-2g\cdot\delta$.

We use $(\mathbf{x},\mathbf{y})$ to create a two-prover game. First, we define two distributions that capture the marginal probability that a question is played by $\mathbf{x}$ or $\mathbf{y}$. Formally, we define a distribution $\mathbf{x}^{\prime}$ over $X$ and a distribution $\mathbf{y}^{\prime}$ over $Y$ such that for all $x\in X$ and $y\in Y$ we have $\mathbf{x}^{\prime}(x)=\sum_{a\in A}\mathbf{x}(x,a),$ and $\mathbf{y}^{\prime}(y)=\sum_{b\in B}\mathbf{y}(y,b).$ By Lemma 4, we can assume that $\|\mathbf{x}^{\prime}\|_{1}\geq 1-g\cdot\delta$ and $\|\mathbf{y}^{\prime}\|_{1}\geq 1-g\cdot\delta$.

Our two-prover game will have the same question sets, answer sets, and verification function as $\mathcal{F}$, but a different distribution over the question sets. Let $\mathcal{T}_{(\mathbf{x},\mathbf{y})}=(X,Y,A,B,\mathcal{D},V)$, where $\mathcal{D}$ is the product of $\mathbf{x}^{\prime}$ and $\mathbf{y}^{\prime}$. Note that we have cheated slightly here, since $\mathcal{D}$ is not actually a probability distribution. If $\|\mathcal{D}\|_{1}=c<1$, then we can think of this as Arthur having a $1-c$ probability of not sending any questions to the Merlins and awarding them payoff .

The strategies $\mathbf{x}$ and $\mathbf{y}$ can also be used to give a us a strategy for the Merlins in $\mathcal{T}_{(\mathbf{x},\mathbf{y})}$. Without loss of generality, we can assume that for each question $x\in X$ there is exactly one answer $a\in A$ such that $\mathbf{x}(x,a)>0$, because if there are two answers $a_{1}$ and $a_{2}$ such that $\mathbf{x}(x,a_{1})>0$ and $\mathbf{x}(x,a_{2})>0$, then we can shift all probability onto the answer with (weakly) higher payoff, and (weakly) improve the payoff to the row player. Since $(R,C)$ is cooperative, this can only improve the payoff of the columns in $(R,C)$, and since the row player does not move probability between questions, the payoff of the columns in $(-D_{2},D_{2})$ does not change either. Thus, after shifting, we arrive at a $(1-4g\cdot\delta)$-UNE of $\mathcal{G}$ whose social welfare is at least as good as $\operatorname{SW}(\mathbf{x},\mathbf{y})$. Similarly, we can assume that for each question $y\in Y$ there is exactly one answer $b\in B$ such that $\mathbf{y}(y,b)>0$.

We will use $\mathcal{T}_{(\mathbf{x},\mathbf{y})}$ as an intermediary between $\mathcal{G}$ and $\mathcal{F}$ by showing that the payoff of $(\mathbf{x},\mathbf{y})$ in $\mathcal{G}$ is close to the payoff of $(s_{\mathbf{x}},s_{\mathbf{y}})$ in $\mathcal{T}_{(\mathbf{x},\mathbf{y})}$, and that the payoff of $(s_{\mathbf{x}},s_{\mathbf{y}})$ in $\mathcal{T}_{(\mathbf{x},\mathbf{y})}$ is close to the payoff of $(s_{\mathbf{x}},s_{\mathbf{y}})$ in $\mathcal{F}$. Since we have a bound on the payoff of any pair of strategies in $\mathcal{F}$, this will ultimately allow us to bound the payoff to both players when $(\mathbf{x},\mathbf{y})$ is played in $\mathcal{G}$.

For notational convenience, let us define $p_{r}(\mathcal{G},\mathbf{x},\mathbf{y})$ and $p_{c}(\mathcal{G},\mathbf{x},\mathbf{y})$ to be the payoff to the row player and column player, respectively, when $(\mathbf{x},\mathbf{y})$ is played in $\mathcal{G}$. We begin by showing that the difference between $p_{r}(\mathcal{G},\mathbf{x},\mathbf{y})$ and $p(\mathcal{T}_{(\mathbf{x},\mathbf{y})},s_{\mathbf{x}},s_{\mathbf{y}})$ is small. Once again we prove this for the payoff of the row player, but the analogous result also holds for the column player.

We have $|p_{r}(\mathcal{G},\mathbf{x},\mathbf{y})-p(\mathcal{T}_{(\mathbf{x},\mathbf{y})},s_{\mathbf{x}},s_{\mathbf{y}})|\leq 4g\cdot\delta.$

By construction, $p(\mathcal{T}_{(\mathbf{x},\mathbf{y})},s_{\mathbf{x}},s_{\mathbf{y}})$ is equal to the payoff that the row player obtains from the subgame $(R,C)$, and so we have $p(\mathcal{T}_{(\mathbf{x},\mathbf{y})},s_{\mathbf{x}},s_{\mathbf{y}})\leq p_{r}(\mathcal{G},\mathbf{x},\mathbf{y})$. On the other hand, since the row player places at most $g\cdot\delta$ probability on rows not in $(R,C)$, and since these rows have payoff at most $\frac{4}{1+4g\cdot\delta}<4$, we have $p_{r}(\mathcal{G},\mathbf{x},\mathbf{y})\leq p(\mathcal{T}_{(\mathbf{x},\mathbf{y})},s_{\mathbf{x}},s_{\mathbf{y}})+4g\cdot\delta$. \qed

First we show that if $(\mathbf{x},\mathbf{y})$ is indeed a $(1-4g\cdot\delta)$-UNE, then $\mathbf{x}^{\prime}$ and $\mathbf{y}^{\prime}$ must be close to uniform over the questions. We prove this for $\mathbf{y}^{\prime}$, but the proof can equally well be applied to $\mathbf{x}^{\prime}$. The idea is that, if $\mathbf{y}^{\prime}$ is sufficiently far from uniform, then there is set $B\subseteq Y$ of $|Y|/2$ columns where $\mathbf{y}^{\prime}$ places significantly more than $0.5$ probability. This, in turn, means that the row of $(D_{1},-D_{1})$ that corresponds to $B$, will have payoff at least $2$, while the payoff of $(\mathbf{x},\mathbf{y})$ can be at most $1+3g\cdot\delta$, and so $(\mathbf{x},\mathbf{y})$ would not be a $(1-4g\cdot\delta)$-UNE. We formalise this idea in the following lemma. Define $\mathbf{u}_{X}$ to be the uniform distribution over $X$, and $\mathbf{u}_{Y}$ to be the uniform distribution over $Y$.

We have $\|\mathbf{u}_{Y}-\mathbf{y}^{\prime}\|_{1}<16g\cdot\delta$ and $\|\mathbf{u}_{X}-\mathbf{x}^{\prime}\|_{1}<16g\cdot\delta$.

If $\|\mathbf{u}_{Y}-\mathbf{y}^{\prime}\|_{1}\geq c$ then there exists a set $B\subseteq Y$ of size $|Y|/2$ such that

We first define $\mathbf{d}=\mathbf{y}^{\prime}-\mathbf{u}_{Y}$, and then we partition $Y$ as follows

Since $\|\mathbf{y}^{\prime}\|_{1}\geq 1-g\cdot\delta$ and $\|\mathbf{u}\|_{1}=1$, we have that

We will prove that there exists a set $B\subseteq Y$ of size $|Y|/2$ such that $\sum_{y\in B}\mathbf{d}_{y}\geq c/4-g\cdot\delta$.

We have two cases to consider, depending on the size of $U$.

First suppose that $|U|>|Y|/2$. If this is the case, then there must exist a set $B\subseteq U$ with $|B|=|U|/2$ and $\sum_{i\in B}\mathbf{d}_{i}\geq c/4-g\cdot\delta$. We can then add arbitrary columns from $U\setminus B$ to $B$ in order to make $|B|=|Y|/2$, and since $\mathbf{d}_{i}>0$ for all $i\in U$, this cannot decrease $\sum_{i\in B}\mathbf{d}_{i}$. Thus, we have completed the proof for this case.

Now suppose that $|U|\leq|Y|/2$. If this is the case, then there must exist a set $C\subseteq L$ with $|C|=|L|/2$ and $\sum_{i\in C}\mathbf{d}_{i}\geq-\frac{c}{4}+g\cdot\delta$. So, let $C^{\prime}\subseteq C$ be an arbitrarily chosen subset such that $|C^{\prime}|+|U|=|Y|/2$. This is possible since $|L|=|Y|-|U|$ and hence $|L|/2=|Y|/2-|U|/2$, which implies that $|L|/2+|U|>|Y|/2$. Setting $B=C^{\prime}\cup U$ therefore gives us a set with $|B|=|Y|/2$ such that

So we have completed the proof of this case, and the lemma as a whole. \qed

We can now proceed with the proof of Lemma 6.

Suppose, for the sake of contradiction that one of these two properties fails. Without loss of generality, let us assume that $\|\mathbf{u}_{Y}-\mathbf{y}^{\prime}\|_{1}\geq c$. We will show that the row player can gain more than $1$ in payoff by deviating to a new strategy, which will show that $(\mathbf{x},\mathbf{y})$ is not a $1$-UNE, contradicting our assumption that it is a $(1-4g\cdot\delta)$-UNE.

By assumption, $\mathbf{x}$ places at least $1-g\cdot\delta$ probability on rows in $(R,C)$. The maximum payoff in $R$ is $1$, and the maximum payoff in $-D_{2}$ is . On the one hand, the rows in $D_{2}$ give payoff at most $8/(2+g\cdot\delta)\leq 4$. So the row player’s payoff under $(\mathbf{x},\mathbf{y})$ is bounded by