Inapproximability of NP-Complete Variants of Nash Equilibrium

Introduction

The classical notion of Nash equilibrium is the most fundamental concept in the theory of non-cooperative games. In recent years, there has been much work on the complexity of finding a Nash equilibrium in a given game. In particular, a series of hardness results culminated in the work of Chen et. al [CDT09], who showed that even for two-player (bimatrix) games, the problem of computing a Nash equilibrium is PPAD-complete, and thus unlikely to be solvable in polynomial time.

Therefore, it makes sense to consider the complexity of approximate equilibria. In particular, a notion which has emerged as the focus of several works is that of an $\varepsilon$-approximate Nash equilibrium, or $\varepsilon$-equilibrium for short, where neither player can gain more than $\varepsilon$ (additively) by defecting to a different strategy (without loss of generality, all payoffs are scaled to lie in the interval $$). A straightforward sampling argument of Lipton et al. [LMM03] shows that in every game, there exist$\varepsilon$-equilibria with support$O(\log n/\varepsilon^{2})$, and so they can be found in quasi-polynomial time$n^{O(\log n/\varepsilon^{2})}$ by exhaustive search.

On the other hand, finding good polynomial time approximations has proved more challenging. While finding a $\frac{1}{2}$-equilibrium turns out to be quite simple [DMP09], more complicated algorithms have given a series of improvements [DMP07, BBM10, TS08], where the current best known is the $0.3393$-equilibrium shown by Tsaknakis and Spirakis [TS08]. A major open question in this area is whether or not there exists a PTAS for Nash Equilibrium (note that the algorithm of Lipton et al. gives a quasi-polynomial time approximation scheme for the problem).

Recently, Hazan and Krauthgamer [HK11] have attempted to provide evidence for the optimality of the QPTAS of Lipton et al. [LMM03], by showing a reduction from a well-studied and seemingly intractable problem (which can also be solved in quasi-polynomial time) to the related problem of finding an $\varepsilon$-equilibrium with near maximum value (the value of an equilibrium is the average of the payoffs of the two players).

The problem they reduce from is the Hidden Clique Problem: Given a graph sampled from $G(n,\frac{1}{2})$ with a planted (but hidden) clique of size $k$, find the planted clique. Since with high probability the maximum clique in $G(n,\frac{1}{2})$ is of size $(2-o(1))\log n$, it is easy to see that for constant $\delta>0$, one can distinguish between $G(n,\frac{1}{2})$ and $G(n,\frac{1}{2})$ with a planted clique of size $k>(2+\delta)\log n$ in quasi-polynomial time by exhaustive search over all subsets of $(2+\delta)\log n$ vertices. It is also not hard to extend this to an algorithm which finds the hidden clique in quasi-polynomial time.

On the other hand, the best known polynomial time algorithm, due to Alon et al. [AKS98] only finds cliques of size $\Omega(\sqrt{n})$. In fact, Feige and Krauthgamer [FK03] show that even extending this approach by using the Lovász-Schrijver SDP hierarchy, one still requires $\Omega(\log n)$ levels of the hierarchy (corresponding to $n^{\Omega(\log n)}$ running time to solve the SDP) just to find a hidden clique of size $n^{1/2-\varepsilon}$. The only possible approach we are aware of for breaking the $\Omega(\sqrt{n})$ barrier would still (assuming certain conjectures) only discover cliques of size $\Omega(n^{c})$ for some constant $c>0$ [FK08, BV09].

Hazan and Krauthgamer show that finding a near-optimal $\varepsilon$-equilibrium is as hard as finding hidden cliques of size $C\log n$, for some universal constant $C$. Here, by near-optimal we mean having value close to maximum possible value obtained in an actual Nash equilibrium. Subsequently, Minder and Vilenchik [MV09] then improved this hardness to planted cliques of size $(2+\delta)\log n$ for arbitrarily small $\delta>0$.There is a small caveat: the reduction of [MV09] only certifies the presence of a hidden clique (i.e. distinguishes the graph from the random graph $G(n,\frac{1}{2})$ w.h.p.) but does not identify the vertices of the clique. Here, we will rely on the hardness assumption for hidden cliques of size $C\log n$ for any constant $C$, and will not concern ourselves with optimizing the value of $C$.

It is important to note that the problem considered in [HK11] is not equivalent to finding an unconstrained $\varepsilon$-equilibrium. In light of the results of [HK11, MV09] it is natural to ask to what extent the hardness for near-optimal approximate equlibrium gives an indication of hardness for unconstrained approximate equilibrium. Indeed, [HK11], in their concluding remarks, ask whether their methods can be used to rule out a PTAS for unconstrained Nash equilibrium. One of the messages of this paper is that these two problems are quite different in terms of approximability and that one should not yet be overly pessimistic about the possibility for a PTAS for unconstrained Nash equilibrium. Indeed, while there is a a polynomial time algorithm to find a $0.3393$-equilibrium, we show that finding a near-optimal $(\frac{1}{2}-\eta)$-equilibrium is hard.

For every $\eta>0$, finding a near-optimal $(\frac{1}{2}-\eta)$-approximate equilibrium is as hard as finding a hidden clique of size $C\log n$ in $G(n,\frac{1}{2})$.

As mentioned above, there is a simple polynomial time algorithm to find a $\frac{1}{2}$-equilibrium, and we show that this algorithm can be extended to find a $\frac{1}{2}$-equilibrium with value at least that of the best exact equilibrium:

There exists a polynomial time algorithm to find a $\frac{1}{2}$-approximate equilibrium with value at least that of the optimal true equilibrium.

Thus, Theorem 1.1 is tight and unlike unconstrained Nash equilibrium, where stronger techniques yield approximations better than $\frac{1}{2}$, near-optimal Nash equilibrium does not admit efficient “non-trivial” approximations (assuming the Hidden Clique problem is hard).

2 The Bigger Picture: Hardness for NP-hard Variants of Nash

Just like with unconstrained $\varepsilon$-equilibrium, finding a near-optimal $\varepsilon$-equilibrium can be done in quasi-polynomial time using the algorithm of [LMM03]. However, the exact version – finding a maximum value Nash equilibrium – is known to be NP-hard [GZ89] and therefore harder than its unconstrained counterpart which is in PPAD [Pap94]. In fact, maximum value Nash is one of several optimization variants of Nash equilibrium which are NP-complete. Other variants include: determining whether a bimatrix game has more than one Nash equilibrium [GZ89], finding a Nash Equilibrium with minimum support [GZ89], and determining whether there exists an equilibrium with value at least $1-\frac{1}{n}$ or all equilibria have value at most $\varepsilon/n$ (even for arbitrarily small $\varepsilon=\varepsilon(n)>0$) [CS03]. We show that approximate-equilibrium variants of these problems are also as hard as Hidden Clique.

For the problem of obtaining any non-trivial approximation to the optimal value of a Nash equilibrium, we prove the following theorem.

For every $\eta>0$, finding an $\varepsilon$-equilibrium with value at least $\eta$ is as hard as finding a hidden clique of size $C\log n$ in $G(n,\frac{1}{2})$, even in a game having an equilibrium of value $1-\eta$.

For the case of determining whether a game has more than one equilibrium, note that by continuity considerations, every two-player game has an infinite number of $\varepsilon$-equilibria. Thus, the appropriate approximate analog is to consider the problem of finding two $\varepsilon$-equilibria with (at least) a certain total variation distance between them. We show that this problem is also as hard as Hidden Clique.

For all sufficiently small $\epsilon>0$, determining whether a game has two different $\varepsilon$-approximate equilibria (say, having statistical distance at least $3\epsilon$) is as hard as finding a hidden clique of size $C\log n$ in $G(n,\frac{1}{2})$.

We then move to the problem of finding an equilibrium with small support. Recall that by [LMM03], there exist $\varepsilon$-Nash equilibria with support $O(\log n/\varepsilon^{2})$. It is also known that for any $\eta>0$, in certain two-player games all $(\frac{1}{2}-\eta)$-equilibria must have support at least $\log n/(1+\log(1/\eta))$ [FNS07] (the threshold of $\frac{1}{2}$ is tight, since the simple $\frac{1}{2}$-equilibrium of [DMP09] has support 3). As an approximate-equilibrium variant of the Minimum Support Equilibrium problem, we consider the problem of finding an $\varepsilon$-equilibrium with support at most some threshold $t$, and prove the following hardness result.

For every $\eta>0$, finding a $(\frac{1}{2}-\eta)$-equilibrium with support size $C^{\prime}\log n$ is as hard as finding a hidden clique of size $C\log n$ in $G(n,\frac{1}{2})$.

This can be seen as a complexity-theoretic analogue of the lower bound of [FNS07] mentioned above. Again, this contrasts with the situation for unconstrained Nash equilibrium, which is guaranteed to exist, and admits stronger approximations.

While these are all negative results, we again would like to stress that there is a positive message to this story: these problems are hard because they are approximate versions of NP-complete problems, not because they are approximate variants of Nash equilibrium. Therefore, these results should not be viewed as indications that Nash equilibrium does not have a PTAS.

3 The Complexity of Approximate Pure Bayes Nash Equilibria

Finally, we consider the problem of approximating pure Bayes Nash Equilibria (BNE) in two-player games. Bayesian games model the situation where the players’ knowledge of the world is incomplete. In a Bayesian game, both players may be in one of a number of different states, known as types, representing what each player knows about the state of the world, and the payoff of each player depends on the type of both players in addition to their strategies. The types are distributed according to some joint distribution and are not necessarily independent. A pure strategy for a Bayesian game assigns to each type a strategy that the player plays when she is in that type. In a pure BNE, conditioning on any given type for a given player, the player cannot gain by changing his strategy for that type. See Section 6 for precise definitions.

Conitzer and Sandholm [CS03] have shown that determining whether a given two-player game has a pure BNE is NP-complete. We show that this holds also for approximate pure BNE.

Let $\varepsilon=0.004$. Then given a Bayesian game that admits a pure BNE, it is NP-hard to find a pure $\varepsilon$-BNE for the game.

However, this hardness result relies heavily on the joint distribution of the players’ types being non-uniform (in fact, not even product distribution). We show that when the distribution over type pairs is uniform, there is in fact a quasi-polynomial time algorithm for $\varepsilon$-approximate pure BNE (when a pure BNE exists).

For every $\varepsilon>0$ there is a quasipolynomial time algorithm to find a pure $\varepsilon$-BNE in two-player Bayesian games with uniformly distributed types and in which a pure BNE exists.

We remark that this algorithm extends easily to arbitrary product distributions over types but in order to keep the notation simple we restrict our attention to the uniform case.

The algorithm is tight: it follows immediately from our hardness for Small Support Equilibrium that this problem is also as hard as Hidden Clique.

For every $\eta>0$, finding a $(\frac{1}{4}-\eta)$-approximate pure BNE in a two-player Bayesian games with uniformly distributed types and in which a pure BNE exists is as hard as finding a hidden clique of size $C\log n$.

4 Organization

In Section 3 we prove the results relating to approximate equilibria with good value: Theorem 1.1 (Section 3.2), Theorem 1.2 (Section 3.4), and Theorem 1.3 (Section 3.3).

In Section 4 we prove Theorem 1.4 by a black-box application of Theorem 1.3. In Section 5 we prove Theorem 1.5 using similar techniques as for the hardness results of Section 3. In Section 6 we prove our results for Bayesian games, Theorems 1.6, 1.7, and 1.8.

Preliminaries

The value of a pair of strategies, denoted $v_{\mathcal{G}}(x,y)$, is the average payoff of the two players, i.e.,

Further, for a set $S\subseteq[n]$ of strategies, we use $v_{\mathcal{G}|S}(x,y)$ to denote the value of $(x,y)$ conditioned on both players playing in $S$. Formally,

(If $\|x_{S}\|=0$ or $\|y_{S}\|=0$, $v_{\mathcal{G}|S}(x,y)$ is undefined.)

Given an undirected graph $G=(V,E)$, and (not necessarily disjoint) vertex sets $S_{1},S_{2}\subseteq V$, we will denote by $E(S_{1},S_{2})$ the set of ordered pairs $\{(i,j)\in S_{1}\times S_{2}\mid\{i,j\}\in E\text{ or }i=j\}$. We will refer to $d(S_{1},S_{2})=|E(S_{1},S_{2})|/(|S_{1}||S_{2}|)$ as the density of the pair $(S_{1},S_{2})$.

Finally, we shall make repeated use of the following standard Chernoff bound.

Approximate Equilibria With Good Value

In this section we describe the general reduction that we use to prove Theorems 1.1 and 1.3 and describe its properties. This reduction also forms the basis for the reductions we use to prove Theorems 1.4, 1.5 and 1.8. It is based on the reduction of [HK11].

As in [HK11] our soundness analysis proceeds by using the approximate equilibrium to find a dense bipartite subgraph of $G$. The following lemma shows that this is sufficient to recover the hidden clique.

There exist universal constants $c_{1}$ and $c_{2}$ such that the following holds. Let $G$ be a sample from $G(n,\frac{1}{2})$ with a hidden clique of size $C\log n$ for some $C\geq c_{1}$. Then, given a pair of vertex sets $S_{1},S_{2}\subseteq[n]$ of size $c_{2}\log n$ and density $d(S_{1},S_{2})\geq 5/9$ we can in polynomial time reconstruct the hidden clique (with high probability over $G$).

The lemma is slightly different from Lemma 5.3 of [HK11]: there we start with a bipartite subgraph of density $3/5$ instead of $5/9$ but this minor difference only changes the value of the constant $c_{2}$ – the lemma holds for any constant density strictly larger than $\frac{1}{2}$.

Let us now describe the reduction. It is controlled by three parameters $\alpha,\beta,\gamma\in(0,1)$. Setting these parameters appropriately gives the various hardness results.

We conclude this section with an additional lemma which shows how to obtain a dense bipartite subgraph given an approximate equilibrium of $\mathcal{G}$ with certain properties. This lemma (and its proof) is analogous to [HK11, Lemma 5.2], but as we need it in larger generality we also give the proof.

Let $\mathcal{G}$ be as in Reduction 3.2. Fix any $s\in$, $t\in$ and $\varepsilon\in$ such that $1-t-3\sqrt{s}/2\geq\alpha+\varepsilon$, and let $(x,y)$ be an $\varepsilon$-approximate equilibrium of $\mathcal{G}$ with the following two properties:

Both $\|x_{[n]}\|\geq 1-t$ and $\|y_{[n]}\|\geq 1-t$.

The conditional value $v_{\mathcal{G}|[n]}(x,y)\geq(1-s)\alpha$.

Then, given $(x,y)$ as above, we can efficiently find vertex sets $S_{1},S_{2}\subseteq[n]$ each of size $c_{2}\log n$ and density $d(S_{1},S_{2})\geq 5/9$.

In the proof of Lemma 3.3 we shall use the following simple claim, which is analogous to [HK11, Claim 5.3]:

Let $S\subset[n]$ be a set of size $|S|\leq c_{2}\log n$. Then, w.h.p. over $\mathcal{G}$, in any $\varepsilon$-equilibrium in the above game, the probability mass a column (or row) player may place on such a set $S$ is at most $\varepsilon+\alpha$.

The proof of the claim follows by noting that for such $S$, with high probability, there is a row $i$ of $B$ such that $B_{ij}=1$ for all $j\in S$. Indeed, the probability that such a row does not exist is exactly

We omit the remaining details as they are identical to [HK11, Claim 5.3].

To obtain a lower bound on the cardinality $|S^{\prime}_{1}|$, we shall bound $\|x_{S^{\prime}_{1}}\|$ by $\varepsilon+\alpha$ and then appeal to the claim. By the first given property of $(x,y)$, we have

Thus we have $\|x_{S^{\prime}_{1}}\|\geq 1-t-3\sqrt{s}/2\geq\varepsilon+\alpha$ and so by the claim, $|S^{\prime}_{1}|\geq c_{2}\log n$. Truncate $S^{\prime}_{1}$ by taking any arbitrary subset $S_{1}\subseteq S^{\prime}_{1}$ of cardinality $|S_{1}|=c_{2}\log n$.

The argument to lower bound $|S^{\prime}_{2}|$ is similar to the argument for $|S^{\prime}_{1}|$. We get

as desired. Again, we can truncate $S^{\prime}_{2}$ by taking a subset $S_{2}\subseteq S^{\prime}_{2}$ of cardinality $|S^{\prime}_{2}|=c_{2}\log n$. By construction $d(S_{1},S_{2})\geq 5/9$, and we are done. ∎

2 Hardness for ε𝜀\varepsilon close to 1212\frac{1}{2}

To obtain Theorem 1.1 the main requirement is to set $\alpha=\frac{1}{2}+O(\eta)$. The values of $\beta$ and $\gamma$ are essentially irrelevant in this case – the only thing needed is that $\beta$ is bounded away from both and $\alpha$ and that $\gamma\leq\frac{1}{2}$.

Let $\alpha=\frac{1}{2}+t$, $\gamma\leq\frac{1}{2}$ and $\mathcal{G}$ be the game of Reduction 3.2. Then for any pair of strategies $(x,y)$ with value at least $v_{\mathcal{G}}(x,y)\geq\alpha-t^{2}$ it holds that $\|x_{[n]}\|$ and $\|y_{[n]}\|$ are both at least $1-t$.

Let $p=\|x_{[n]}\|$ and $q=\|y_{[n]}\|$. As the value of any outcome outside the $\alpha A$ block is at most $\frac{1}{2}$, we have that the value of $(x,y)$ is at most

so that if the value is at least $\alpha-t^{2}$ we have

Since $p,q\in$, it follows that they are both at least $1-t$. ∎

Let $(x,y)$ be any pair of strategies with value $v_{\mathcal{G}}(x,y)\geq\frac{1}{2}$ and $\|x_{[n]}\|>0$, $\|y_{[n]}\|>0$. Then $v_{\mathcal{G}|[n]}(x,y)\geq v_{\mathcal{G}}(x,y)$, provided that $\gamma\leq\frac{1}{2}$.

Plugging this into Lemma 3.3, we can now easily complete the proof of hardness for $\varepsilon$ close to $\frac{1}{2}$.

For every $\eta>0$ there exist $\delta=\Omega(\eta^{2})$, $\alpha\geq\frac{1}{2}$ and universal constant $C$ not depending on $\eta$ such that the following holds. Given a graph $G=(V,E)$ we can in randomized polynomial time construct a bimatrix game $\mathcal{G}$ with maximum value $\alpha$ (over all strategy pairs) such that, if $G=G(n,\frac{1}{2})$ with a hidden clique of size $C\log n$, the following holds (w.h.p. over $G$ and $\mathcal{G}$):

There is a Nash equilibrium $(x,y)$ with value $\alpha$.

Given any $(\frac{1}{2}-\eta)$-equilibrium with value $\geq\alpha-\delta$, we can efficiently recover the hidden clique.

Given a graph $G=(V,E)$, we apply Reduction 3.2 with parameters as follows. For some $t>0$ to be determined momentarily, let $\alpha=\frac{1}{2}+t$, $\beta=\gamma=1/3$, $\delta=t^{2}$.

For the completeness, we shall show that having both players play uniformly over the hidden clique is an equilibrium. For this to hold, we have to make sure that there is no row in $B$ with average value at least $\alpha$ in the positions corresponding to the clique. By Lemma 2.1 and a union bound over all rows of $B$ we can bound the probability of this happening by

If $C$ is a sufficiently large universal constant (e.g., $C=18\cdot(c_{2}+1)\log 1/\beta+1$) this probability is $o(1)$ and the completeness property follows.

For the soundness, consider any $(\frac{1}{2}-\eta)$-approximate equilibrium $(x,y)$ with value at least $v_{\mathcal{G}}(x,y)\geq\alpha-\delta=\alpha-t^{2}$. By Lemma 3.5 both $\|x_{[n]}\|$ and $\|y_{[n]}\|$ are at least $1-t$. Furthermore, by Observation 3.6 we have $v_{\mathcal{G}|[n]}(x,y)\geq\alpha-\delta\geq\alpha(1-t^{2})$.

Now if $\frac{1}{2}-\eta\leq 1-t-3t/2-\alpha=\frac{1}{2}-7t/4$ we can apply Lemma 3.3 and extract a dense bipartite subgraph of $G$ which can be plugged in to Lemma 3.1 to obtain the hidden clique. Setting $t=4\eta/7$ we get the result. ∎

3 Distinguishing Between Low and High Value

For Theorem 1.3 the choices of all three parameters $\alpha,\beta,\gamma$ of Reduction 3.2 are important. We are going to set $\gamma$ close to , and $\alpha>\beta$ both close to $1$.

On a high level, the proof has the same structure as that of Theorem 1.1. However, in the current setting Lemma 3.5 and Observation 3.6 do not apply. To arrive at similar conclusions we use a different argument, exploiting the fact that $(x,y)$ is a $\varepsilon$-equilibrium. Essentially, the argument is as follows: the off-diagonal blocks ($B$ and $B^{\top}$) are not stable, since there is too much incentive for at least one player to deviate. Therefore, most of the probability mass in an equilibrium is concentrated either in the $\alpha A$ block, or in the $\gamma J$ block. However, in the $\gamma J$ block, the value is too small. So, if the equilibrium has even slightly larger value, its mass must be concentrated in the $\alpha A$ block. There it has to actually have very large value, since otherwise, there is incentive for both players to deviate to $B$ and $B^{\top}$ to get reward $\beta$. The rest of the proof follows as before.

Formally, we have the following lemma, showing that (under certain conditions) any $\varepsilon$-equilibrium with non-negligible value must satisfy the conditions of Lemma 3.3.

Fix a parameter $\varepsilon\in(0,1)$, let $\alpha-\beta\leq\varepsilon$, and $\gamma=4\sqrt{\varepsilon}$ and consider the game $\mathcal{G}$ as in Reduction 3.2.

Then, w.h.p. over $\mathcal{G}$, any $\varepsilon$-equilibrium $(x,y)$ with value more than $5\sqrt{\varepsilon}$ satisfies:

Both $\|x_{[n]}\|$ and $\|y_{[n]}\|$ are at least $1-\sqrt{\varepsilon}$.

$v_{\mathcal{G}|[n]}(x,y)\geq\alpha-3\varepsilon$.

Consider any $\varepsilon$-equilibrium $(x,y)$ with value more than $5\sqrt{\varepsilon}$. Note that this trivially implies that $\varepsilon\leq 1/25$.

Let $p=\|x_{[n]}\|$ and $q=\|y_{[n]}\|$ be the probability mass that the row (resp. column) player assigns to the first $n$ strategies in this equilibrium. We begin with the first item, i.e., the lower bound on $p$ and $q$.

Consider the row player’s incentive to deviate by shifting the probability mass in the first $n$ rows to the uniform distribution over the remaining rows. When the column player is playing outside the first $n$ columns, this deviation changes the row player’s payoff from to $\gamma$, and when the column player is playing in one of the first $n$ columns the row player’s payoff decreases by at most $\alpha-\beta+o(1)$. Let us ignore this $o(1)$ term. Since this is an $\varepsilon$-equilibrium, we have

Considering also the symmetric argument for the column player, this gives

where the first inequality holds trivially for all $p,q\in$. The inequality $p(1-p)\leq\sqrt{\varepsilon}/2$ together with the constraint $\varepsilon\leq 1/25$ implies that either $p\leq\sqrt{\varepsilon}$ or $p\geq 1-\sqrt{\varepsilon}$. The inequality for $q$ gives an analogous bound. Moreover, it cannot be the case that $p<\frac{1}{2}<q$ or $q<\frac{1}{2}<p$, since then we would have $\max\{p(1-q),q(1-p)\}\geq\frac{1}{4}$, contradicting (7). Thus, it follows that either $p,q\leq\sqrt{\varepsilon}$ or $p,q\geq 1-\sqrt{\varepsilon}$.

Let us now exclude the first option. Suppose for contradiction that $p,q\leq\sqrt{\varepsilon}$. Then the value of the equilibrium is at most

contradicting the assumption that $(x,y)$ has value more than $5\sqrt{\varepsilon}$. Hence both $p$ and $q$ are at least $1-\sqrt{\varepsilon}$.

It remains to give a lower bound on the conditional value $w:=v_{\mathcal{G}|[n]}(x,y)$ obtained when playing inside $\alpha A$. As above, consider the incentive for the row player to deviate to the uniform distribution over. To be more precise, we can use $w$ instead of $\alpha$ in the bound (6). Solving for $w$ gives

where we used that $\frac{1}{pq}\leq\frac{1}{(1-\sqrt{\varepsilon})^{2}}\leq\frac{25}{16}<2$ for $\varepsilon\leq 1/25$. ∎

Equipped with Lemma 3.8, it is easy to finish the proof of Theorem 1.3.

For every constant $\eta>0$ there exist $\varepsilon=\Omega(\eta^{2})$ and $C=O(1/\eta^{3})$ such that the following holds. Given a graph $G$, we can in randomized polynomial time construct a bimatrix game $\mathcal{G}$ such that, if $G=G(n,\frac{1}{2})$ with a hidden clique of size $C\log n$, the following holds (w.h.p. over $G$ and $\mathcal{G}$):

There is a Nash equilibrium $(x,y)$ with both players earning payoff $1-\eta$.

Given any $\varepsilon$-equilibrium with value $\geq\eta$, we can efficiently recover the hidden clique.

Given a graph $G=(V,E)$, we apply Reduction 3.2 with parameters as follows.

Let $\varepsilon=(\eta/5)^{2}$, $\alpha=1-\eta=1-5\sqrt{\varepsilon}$, $\beta=\alpha-\varepsilon$, and $\gamma=4\sqrt{\varepsilon}$. Assume without loss of generality that $\eta$ is small enough so that $\alpha>3/4$.

For the completeness, we proceed as in the proof of Theorem 3.7. We can upper bound the probability that the uniform distribution over the hidden clique is not an equilibrium by

We have $N=n^{O(\log 1/\beta)}=n^{O(\eta)}=n^{O(\sqrt{\varepsilon})}$. Letting $C$ be a sufficiently large multiple of $1/\varepsilon^{1.5}$ the completeness property follows.

For the soundness analysis, take any $\varepsilon$-approximate equilibrium $(x,y)$ with value at least $5\sqrt{\varepsilon}$. By Lemma 3.8, w.h.p. $(x,y)$ satisfies the conditions of Lemma 3.3 with $t=\sqrt{\varepsilon}$ and $s=\frac{3\varepsilon}{\alpha}\leq 4\varepsilon$. The only remaining thing to check is the condition $\alpha+\varepsilon\leq 1-t-3\sqrt{s}/2$, which is easily verified ($1-4\sqrt{\varepsilon}$ is an upper bound for the LHS and a lower bound for the RHS).

4 An Algorithm For Good 1212\frac{1}{2}-Approximate Equilibria

In this section we prove Theorem 1.2 by describing a simple algorithm to find a $\frac{1}{2}$-approximate Nash equilibrium with at least as good value as the best exact Nash equilibrium. This shows that the bound on $\varepsilon$ in Theorem 1.1 is tight.

For general $\frac{1}{2}$-approximate equilibria (without any constraint on the value), the following simple algorithm was suggested by Daskalakis, Mehta and Papadimitiou [DMP09]. Start by choosing an arbitrary pure strategy $e_{i}$ for the row player, let $e_{j}$ be the column player’s best response to $e_{i}$, and let $e_{k}$ be the row player’s best response to $e_{j}$. Then the following is a $\frac{1}{2}$-equilibrium: let the column player play $e_{j}$, and let the row player play $e_{i}$ with probability $\frac{1}{2}$ and $e_{k}$ with probability $\frac{1}{2}$ (neither player can gain more than $\frac{1}{2}$ by deviating, since each player is playing a best response strategy with probability $\frac{1}{2}$). Thus, every bimatrix game has a $\frac{1}{2}$-approximate equilibrium in which one of the players plays a pure strategy. We show that this is also the case for optimal value $\frac{1}{2}$-equilibria.

For every bimatrix game which has a Nash equilibrium of value $v$, there exists a $\frac{1}{2}$-approximate equilibrium with value at least $v$ in which one of the players plays a pure strategy.

Let the pure strategy $e_{j}$ be some strategy in the support of $y^{*}$ for which the row player’s payoff is at least $v_{r}$ (when the row player is playing $x^{*}$ and the column player $e_{j}$). Such a strategy exists since $v_{r}$ is the expected payoff for the row player when the column player plays according to $y^{*}$. Furthermore, any such $e_{j}$ is a best response to $x^{*}$ since $(x^{*},y^{*})$ is an equilibrium.

Clearly, if the pair of strategies $(x^{*},e_{j})$ is a $\frac{1}{2}$-equilibrium we are done, since both the row and colum player are getting at least the same payoff as for the pair $(x^{*},y^{*})$.

If $(x^{*},e_{j})$ is not a $\frac{1}{2}$-equilibrium, this must be because the row player has incentive $\geq\frac{1}{2}$ to deviate (as the column player is by definition playing a best response). Note that this implies that $v_{c}\leq v_{r}\leq\frac{1}{2}$ since the row player’s incentive to deviate can never be more than $1-v_{r}$. Let $e_{k}$ be some best response for the row player, and consider the pair of strategies $\left(\frac{1}{2}(x^{*}+e_{k}),e_{j}\right)$. As above, this is a $\frac{1}{2}$-equilibrium, since both players are playing a best response with probability $\frac{1}{2}$. Furthermore, the payoff for the row player is at least $v_{r}/2+(v_{r}+1/2)/2\geq v_{r}+1/4\geq v_{r}+v_{c}/2$, and the payoff for the column player is at least $v_{c}/2$. Thus the value is at least $\frac{1}{2}(v_{r}+v_{c}/2+v_{c}/2)=v$, and we are done.

For at least one strategy $e_{j}$, this LP is feasible and computes a $\frac{1}{2}$-equilibrium with at least the desired value. ∎

Finding A Second Equilibrium

In the following Theorem, $d_{\text{TV}}$ refers to the total variation distance between two vectors, i.e., $d_{\text{TV}}(x,y)=\frac{1}{2}\sum|x_{i}-y_{i}|$.

There is a $C>0$ such that the following holds for all sufficiently small $\varepsilon>0$. Given a graph $G$ we can in randomized polynomial time construct a bimatrix game $\mathcal{G}^{\prime}$ which admits a pure Nash equilibrium $(e_{i},e_{j})$ such that, if $G=G(n,\frac{1}{2})$ with a hidden clique of size $C\log n$, the following holds (w.h.p. over $G$ and $\mathcal{G}^{\prime}$):

There is a Nash equilibrium $(x,y)$ such that $d_{\text{TV}}(e_{i},x)=d_{\text{TV}}(e_{j},y)=1$.

Given any $\varepsilon$-approximate equilibrium $(x,y)$ of $\mathcal{G}^{\prime}$ with $d_{\text{TV}}(e_{i},x)\geq\varepsilon+O(\varepsilon^{2})$ or $d_{\text{TV}}(e_{j},y)\geq\varepsilon+O(\varepsilon^{2})$, we can efficiently recover the hidden clique.

Note that the bound $\varepsilon+O(\varepsilon^{2})$ on the statistical distance is almost tight: given any true equilibrium $(x,y)$ there are $\varepsilon$-approximate equilibria $(x^{\prime},y^{\prime})$ with $d_{\text{TV}}(x,x^{\prime})\geq\varepsilon$ and $d_{\text{TV}}(y,y^{\prime})\geq\varepsilon$.

where ${\bf\lambda}$ is the $1\times N$ vector with each coordinate equal to $\lambda$. We set $\lambda=8/10$. $\mathcal{G}^{\prime}$ is a bimatrix game of size $(N+1)\times(N+1)$.

Clearly, $(e_{N+1},e_{N+1})$ is a pure Nash equilibrium of $\mathcal{G}^{\prime}$. Note that for any mixed strategy $x$, we can write $d_{\text{TV}}(e_{N+1},x)=1-x_{N+1}$ so it suffices to obtain good bounds on $x_{N+1}$ and $y_{N+1}$.

Furthermore the completeness case also follows immediately since in that case $\mathcal{G}$ has a Nash equilibrium with both players earning payoff $9/10$. As $\lambda\leq 8/10$ this is an equilibrium in $\mathcal{G}^{\prime}$ as well and since it does not use the $(N+1)$’st strategy we obtain the completeness property.

For the soundness, consider any $\varepsilon$-approximate equilibrium $(x,y)$ of $\mathcal{G}^{\prime}$, let $p=\|x_{[N]}\|$, $q=\|y_{[N]}\|$ be the probability that the row (resp. column) player plays in the original game $\mathcal{G}$ where $x_{N+1}<1-\varepsilon-O(\varepsilon^{2})$ and $y_{N+1}<1-\varepsilon-O(\varepsilon^{2})$. We need to show that $(x,y)$ can be used to recover the planted clique.

where the $q\varepsilon^{\prime}$ term is what the row player gains from when the column player plays on the first $N$ strategies, and the other term is since, when the column player plays on $N+1$ the row player gets the same payoff on all the first $N$ strategies. As $(x,y)$ is an $\varepsilon$-approximate equilibrium in $\mathcal{G}^{\prime}$, (13) must be bounded by $\varepsilon$ and hence

Now the same argument as in the first part of the proof of Lemma 3.8 gives that

This quadratic inequality in $p$ implies that either $p\leq\varepsilon+O(\varepsilon^{2})$ or $11p/10\geq 1-\varepsilon-O(\varepsilon^{2})$. The first possibility is ruled out by our assumption, therefore $p>\frac{10}{11}(1-\varepsilon-O(\varepsilon^{2}))$, and similarly $q>\frac{10}{11}(1-\varepsilon-O(\varepsilon^{2}))$.

Small support equilibria

In this section, we show hardness of finding an $\varepsilon$-approximate Nash equilibrium with small (logarithmic) support when one exists, even for $\varepsilon$ close to $\frac{1}{2}$. Note that an $\varepsilon$-approximate Nash equilibrium for two-player $n^{\prime}$-strategy games with support at most $O(\log n^{\prime}/\varepsilon)$ is guaranteed to exist by the algorithm of Lipton et al. [LMM03]. Here we consider approximate equilibria with smaller (but still logarithmic) support. Also, note that this is tight, since for $\varepsilon=\frac{1}{2}$, we have the simple algorithm of [DMP09], which gives a $\frac{1}{2}$ equilibrium of support 3.

Our reduction for small support equilibria involves the following construction, which is very similar to the earlier one.

For every $\eta>0$ there exists $C>0$ such that finding a $(\frac{1}{2}-\eta)$-equilibrium with support at most $(\log n)/2$ is as hard as finding a hidden clique of size $C\log n$ in $G(n,\frac{1}{2})$.

Given a graph $G$ from $G(n,\frac{1}{2})$ (possibly with a hidden clique), construct the game $\mathcal{G}$ as in Reduction 5.1 with the following parameters: let $\alpha=\frac{1}{2}+\eta/8$, let $\beta=\alpha+(\frac{1}{2}-\eta)-\eta^{2}/8=1-\frac{7}{8}\eta-\eta^{2}/8$. We choose the dimension $N_{2}$ as $N_{2}=n^{c^{\prime}}$, where $c^{\prime}$ is chosen to satisfy $(\eta^{2}/8)^{2}c^{\prime}=4c$. Since $c=(c_{2}+1)\log 1/\beta=\Theta(\eta)$ we have that $c^{\prime}=\Theta(1/\eta^{3})$. We choose the density $C$ of the hidden clique to be $C=c^{\prime}/2+1$.

Note that the number of strategies is $n+N_{1}N_{2}=n+n^{c^{\prime}+c}$, so that we are looking for an equilibrium with support at most $\frac{1}{2}\log(n+n^{c^{\prime}+c})=C^{\prime}\log n$ for some $c^{\prime}/2\leq C^{\prime}\leq c^{\prime}/2+1$ (assuming $\eta$ is sufficiently small).

The completeness follows easily. Suppose $G$ contains a hidden clique of size $C\log n>C^{\prime}\log n$. Then if both players play uniformly over the same subset of $C^{\prime}\log n$ clique vertices, they both achieve reward $\alpha$. The probability that, say, the row player can gain $\frac{1}{2}-\eta$ (i.e. get payoff $\alpha+\frac{1}{2}-\eta=\beta+\eta^{2}/8$) by deviating to some row in $B$ (note that he can only deviate to rows in copies of $B$) is by the Chernoff bound Lemma 2.1 and a union bound at most

Now, for the soundness, consider any $(\frac{1}{2}-\eta)$-equilibrium $(x,y)$. Let us first show that both players must have most of their probability concentrated in the $\alpha A$ block. Let $p=\|x_{[n]}\|$ and $q=\|y_{[n]}\|$ (the probabilities that each player plays in the first $n$ rows/columns). Let us consider the two player’s incentive to deviate. In the $\alpha A$ block, the row player achieves at most payoff $\alpha$, and can achieve payoff $\beta-o(1)$ by playing uniformly over all rows in $B$ (w.h.p. this is true for all distributions over columns in $[n]$). In particular, there exists at least one row in $B$ in which the row player can achieve this value. Now consider the right hand side of the payoff matrix. Let $\lambda\in$ be the payoff that the row player receives in $R$ (thus, the column player receives $1-\lambda$ here). For any row in $B$, there are $N_{2}$ corresponding rows in $R$ (one corresponding to each copy of $B$). Since the column player’s support is at most $C^{\prime}\log n$, the probability that regardless of the column player’s choice of support, there will be at least one row among these that has all 1’s in the corresponding positions is at least

Thus, w.h.p. for every row in $B$ and every possible strategy for the column player (up to the restriction on support size), there is a row in $R$ corresponding to the correct row in $B$ s.t. the row player would achieve payoff 1 in $R$ (by deviating to this row). In particular, this is true for the row in $B$ where the row player can achieve value $\beta-o(1)$ (as before, we will ignore this $o(1)$). To summarize, by deviating, the row player can gain at least

Similarly, the column player’s incentive to deviate is at least

On average, the two players’ incentive to deviate is at least

and since this incentive is at most $\frac{1}{2}-\eta$, we have

Now it remains to bound the conditional value $w$ that is achieved in the $\alpha A$ block. This we can do using the same analysis as above, but substituting $w$ for $\alpha$. Making this substitution in (24) and solving for $w$ we have

We are now in a position to apply Lemma 3.3. As stated Lemma 3.3 only applies to Reduction 3.2 and not the present reduction but it can be verified that it works also in this case (what is needed is that the size of $B$ is the same, and the presence of an approximate equilibrium with most mass in $A$ and good value in $A$). We have $t=\eta/8$ and $s=\eta^{2}/4$ which is easily checked to satisfy the condition $1-t-3\sqrt{s}/2\geq\alpha+(\frac{1}{2}-\eta)$. Thus we conclude the existence of a dense bipartite subgraph which, as before, allows us to reconstruct the hidden clique.

Note that we have a much smaller gap between the completeness and hardness above than in the other problems we have considered. In particular, we do not claim that finding a $\frac{1}{2}-\eta$-equilibrium with small support is hard even when an exact equilibrium with small support exists. However, modifying parameters in the above proof, such hardness can be shown for a smaller additive approximation:

For every $\eta>0$ there exists $C>0$ such that finding a $(\frac{1}{4}-\eta)$-equilibrium with support at most $O(\log n)$ in a two-player game which admits a pure Nash equilibrium is as hard as finding a hidden clique of size $C\log n$ in $G(n,\frac{1}{2})$.

Computing approximate pure Bayes-Nash equilibrium

Bayesian games model the situation where the players’ knowledge of the world is incomplete. In this paper we focus on Bayesian games with two players, but the results generalize to an arbitrary number of players. More details on Bayesian games can be found in most Game Theory textbooks, for example in [FT91].

Since a pure Nash equilibrium need not exist in non-Bayesian games, it need not exist in Bayesian games either. Moreover, while verifying whether a non-Bayesian two player game has a pure Nash equilibrium is trivial, verifying whether a pure Bayesian Nash equilibrium exists is NP-hard [CS03]. Furthermore, as the example in [CS03] demonstrates, this problem remains hard even when the distribution on types is uniform and the payoff does not depend on the players’ types.

A similar requirement should hold for the column player.

We show that for general distributions on types and for some small constant $\varepsilon$, finding a pure $\varepsilon$-BNE in games where a pure BNE exists is still NP-hard. On the other hand, we also show that if the distribution on the players’ types is uniform, whenever a pure BNE exists, a pure $\varepsilon$-BNE can be found in quasi-polynomial time.

We show that for some constant $\varepsilon$, determining whether a pure strategy $\varepsilon$-Bayes Nash equilibrium exists is NP-hard. Specifically, $\varepsilon=0.004$ suffices. We prove:

Let $\varepsilon=0.004$. Then given a Bayesian game that admits a pure BNE, it is NP-hard to find a pure $\varepsilon$-BNE for the game. Moreover, it is NP-hard to solve the promise problem of distinguishing games that admit a pure BNE from games that do not admit a pure $\varepsilon$-BNE.

We give a reduction from the problem of $3$-coloring $4$-regular graphs, which is known to be NP-complete [Dai80]. Let $G=(V,E)$ be a $4$-regular graph with $|V|=n$. The edges of $G$ can be properly colored with $5$ colors using Vizing’s algorithm. In other words, we can compute a coloring $c:E\rightarrow\{1,\ldots,5\}$ such that for every two edges $e_{1},e_{2}$ incident to the same vertex, $c(e_{1})\neq c(e_{2})$.

if $G$ is $3$-colorable, then the game admits a pure BNE;

if $G$ is not $3$-colorable, then the game admits no pure $\varepsilon$-BNE.

2 Uniform distribution on types

In this section we show that in the case where the distribution on types is uniform, a pure $\varepsilon$-BNE can be computed in quasi-polynomial time. This contrasts with the previously noted fact from [CS03] that computing a pure BNE is NP-hard even in this special case. As for other quasi-polynimial time computable approximate equilibria we’ve considered, whose exact variants are NP-hard, this problem is also as hard as Hidden Clique:

For every $\eta>0$, finding a $(\frac{1}{4}-\eta)$-approximate pure BNE in a two-player Bayesian games with uniformly distributed types and in which a pure BNE exists is as hard as finding a hidden clique of size $C\log n$.

The assumption in Theorem 6.3 can be relaxed to a pure $(\varepsilon/2)$-BNE equilibrium existing (instead of an actual equilibrium).

The proof is similar in spirit to the quasi-polynomial $\varepsilon$-Nash algorithm of [LMM03], but some additional work is needed. We first (approximately) guess the payoffs and the allowed strategies for both players for all possible types. We then use linear programming to produce a (not necessarily pure) $(3\varepsilon/4)$-BNE. We then sample from this approximate non-pure BNE to obtain a pure $\varepsilon$-BNE.

In the case when $k=O((\log(nk))/\varepsilon^{2})$, i.e. the number of types is small, we can find the exact BNE by brute force, completing the proof of the theorem. ∎

References