Approximate Nash Equilibria with Near Optimal Social Welfare

1 Introduction

The problem of finding good equilibria in noncooperative games and understanding their properties is a central problem in modern game theory. After Nash [Nash, 1951] proved that every finite game has at least one equilibrium (so-called Nash equilibrium), the natural question arose whether we can find one efficiently. After several years of extensive research, this study has culminated in a proof that finding a Nash equilibrium is PPAD-complete even for two-players normal form games [Chen et al., 2009] (see also [Daskalakis et al., 2009a]), making the task of finding an approximate Nash equilibrium one of the central questions in the area of equilibrium computation.

∗Research partially supported by the Centre for Discrete Mathematics and its Applications (DIMAP) and by EPSRC award EP/D063191/1. Email: {A.Czumaj, M.Fasoulakis, M.Jurdzinski}@warwick.ac.uk

Since scaling the payoffs by any positive factor, and applying any additive constant, results in an equilibrium-equivalent game, one typically considers games with all payoffs normalized to be in the interval [0, 1]. Then, we say a set of mixed strategies is an ε-approximate Nash equilibrium, if each player has only at most ε incentive to deflect. The PPADhardness of finding a Nash equilibrium can be extended to provide a PPAD-hardness of designing a fully polynomialtime approximation scheme for this problem [Chen et al., 2009]. In contrast, [Lipton et al., 2003], based on [Althofer, 1994], showed that for every ε > 0, one can find an ε-approximate Nash equilibrium in quasi-polynomial-time nO(ε-2 log n) by examining all supports of size O(ε-2 log n). This work prompted a series of papers [Bosse et al., 2010; Daskalakis et al., 2007; 2009b; Kontogiannis et al., 2006; Tsaknakis and Spirakis, 2008] giving polynomial-time algorithms to find an ε-approximate Nash equilibrium for decreasing values of ε, culminating with the state of the art result by [Tsaknakis and Spirakis, 2008], which finds in polynomial time a 0.3393-approximate Nash equilibrium of a bimatrix game. However, the question whether there is a polynomial-time approximation scheme (which could run in time nO(f(1/ε)) ) still remains one of the central open questions in the area of equilibria computations.

While the Nash theorem [Nash, 1951] ensures that every finite two-player game has at least one Nash equilibrium, typical games posses many equilibria and it is natural to seek those equilibria that are more desirable than others. One natural measure of the most desirable equilibria is to maximize its social welfare, that is, the sum of players' payoffs. Unlike the problem of finding a Nash equilibrium, which is known to be PPAD-complete, finding a Nash equilibrium with maximal social welfare is known to be NP-hard [Gilboa and Zemel, 1989; Conitzer and Sandholm, 2008], and thus, it is likely to be computationally even more difficult. In fact, it is even NP-hard to approximate (to any positive ratio) the maximum social welfare obtained in an exact Nash equilibrium, even in symmetric 2-player games [Conitzer and Sandholm, 2008, Corollary 6]. Therefore, it is natural to ask the question of computational complexity of finding an ε-approximate Nash equilibrium that approximates well the optimal social welfare. The mentioned above quasi-polynomial-time algorithm by [Lipton et al., 2003] not only finds an ε-approximate Nash equilibrium, but also the social welfare of the equilibrium found is an ε-approximation of the social welfare in any Nash equilibrium. In other words, in quasi-polynomial-timewe can find an arbitrarily good approximate Nash equilibrium with social welfare near to the best Nash equilibrium. Although this result raised a hope that it may be possible to extend it to design a polynomial-time algorithm, there are strong hardness results known now. Hazan and Krauthgamer [Hazan and Krauthgamer, 2011] show that for a fixed small ε, finding an ε-approximate Nash equilibrium in a two-player game whose social welfare is off by at most ε from best Nash equilibrium is as hard as finding a hidden clique of size O(logn) in the random graph Gn,1/2 (see also [Austrin et al., 2013; Minder and Vilenchik, 2009]). These hardness results have been further strengthened by Braverman et al. [Braverman et al., 2015], who showed that assuming the deterministic Exponential Time Hypothesis (that any deterministic algorithm for 3SAT requires 2Ω(n) time), there is a constant ε > 0 such that any algorithm for finding an ε-approximate Nash equilibriumwhose social welfare is at least (1-ε) times the optimal social welfare of a Nash equilibrium of the game, requires 2 ˜Ω(logn) time. The above results demonstrate that it is very unlikely to obtain a polynomial-time approximation scheme that for every positive constants ε and ε′ would construct in polynomial time an ε-approximate Nash equilibrium whose social welfare is at least (1-ε′ ) times the optimal social welfare of a Nash equilibrium of the game. We note that for large ε, a stronger (optimal) result is possible: Austrin et al. [Austrin et al., 2013, Theorem 1.3] gave a polynomial-time algorithm that finds a 12 -approximate Nash equilibrium whose social welfare is as good as that of any Nash equilibrium.

1.1 Approximate Nash equilibria with near optimal social welfare

In this paper we take a more pragmatic approach and focus on the analysis of the social welfare in ε-approximate Nash equilibria in a two-player game for a fixed ε, for the regime when we know that we can find an ε-approximate Nash equilibrium. Our goal is more general than that presented in earlier works, like e.g., in [Austrin et al., 2013; Braverman et al., 2015; Hazan and Krauthgamer, 2011; Minder and Vilenchik, 2009]; it is not to compare the social welfare of an ε-approximate Nash equilibrium to that of any Nash equilibrium, but rather to compare it with the optimal social welfare.

It is known that a Nash equilibrium can be arbitrarily far from the optimal social welfare in a bimatrix game. A simple example describing this situation is a prisoners' dilemma game:

Assuming that δ < 23 , the optimal social welfare is achieved by the strategy profile (C, C) with total payoff of 43 , but the unique Nash equilibrium is the strategy profile (D, D) with total payoff of 2δ. Thus, by taking δ arbitrarily small, we can make the social welfare of a Nash equilibrium arbitrarily far from the optimal social welfare of a game.

The central question studied in this paper is if we allow the players up to ε loss to deviate from the best response strategy, whether we can find a stable strategy profile (an εapproximate Nash equilibrium) that guarantees the players a value close to the social optimum?

We note that, to the best of our knowledge, the known polynomial-time algorithms to construct an ε-approximate Nash equilibrium for a constant ε > 0, do not guarantee any welfare for the ε-approximate Nash equilibrium and they return an ε-approximate Nash equilibrium strategy profile which can be arbitrarily far from the optimal social welfare (see, e.g., [Bosse et al., 2010; Daskalakis, 2013; Daskalakis et al., 2007; 2009b; Kontogiannis et al., 2006; Tsaknakis and Spirakis, 2008] for more details).

1.2 New contributions

In this paper we provide several results showing that for every bimatrix game, for every ε > 0, there is always an εapproximate Nash equilibrium with near optimal social welfare, at least a constant fraction the optimal social welfare. Our analysis shows that by considering an appropriate mixture of the optimal strategies and exact or approximate Nash equilibria, one can find the desired approximate Nash equilibrium with near optimal social welfare.

We begin with the case when ε ≥ 12 , the case for which it is known that there is always an ε-approximate Nash equilibrium with constant size support (cf. [Daskalakis et al., 2009b]). We show that in that case we can find an ε-approximate Nash equilibrium with constant size support whose social welfare is at least 2√ε - ε ≥ 0.914 times the optimal social welfare. Furthermore, we demonstrate that our bound for the social welfare is tight.

Theorem 1 For every ε ≥ 12 , we can construct in polynomial time an ε-approximate Nash equilibrium (and with constant size support) whose social value is at least 2√ε - ε times the optimal social welfare. Furthermore, there is a bimatrix game for which for every ε ≥ 12 , every ε-approximate Nash equilibrium has social welfare no more than 2√ε - ε times the optimal social welfare.

In particular, we can construct in polynomial time a 1 2 - approximate Nash equilibrium whose social welfare is at least 2√2-1 2 ≈ 0.914 times the optimal social welfare.

As a byproduct of our approach, we also obtain a stronger result for the class of win-lose bimatrix games and show that for any ε ∈ [ 1 2 , 1], for any win-lose bimatrix game with values in {0, 1}, we can find in polynomial time an ε-approximate Nash equilibrium with optimal social welfare (Theorem 5).

The case ε < 12 is more challenging and while we do not have a tight bound for the social welfare in this case, we can still construct an ε-approximate Nash equilibrium with social welfare that is at least κε times the optimum, for some positive constant κε. One challenge in the case ε < 12 stems from the fact that there are bimatrix games with no ε-approximate Nash equilibrium with constant support (cf. [Feder et al., 2007]), which requires us to use a different approach than that in Theorem 1 to deal with this case. Using as a starting point

ε∗ -approximate Nash equilibria with arbitrary social welfare and ε∗ < ε, we modify them to obtain an ε-approximate Nash equilibrium with high social welfare to get the following.

Theorem 2 For every fixed positive ε < 12 there is a positive constant κε = (1 - √1 - ε)2 , such that every bimatrix game has an ε-approximate Nash equilibrium with social welfare at least κε times the optimal social welfare.

Our construction is algorithmic and gives the following.

Theorem 3 Let ε∗ be such that there is a polynomial time algorithm for finding an ε∗ -approximate Nash equilibrium of a bimatrix game. Then for every fixed positive ε > ε∗ , there is a positive constant ζε,ε∗ = (1 - √ 1-ε 1-ε∗ )2 , such that for every bimatrix game one can find in polynomial time an ε-approximate Nash equilibrium with social welfare at least ζε,ε∗ times the optimal social welfare.

We also obtain further algorithmic results improving the bounds for the social welfare above in several special cases for ε < 12 . For example, in the case when the optimal social welfare is at least 2-3ε 1-ε , then in Theorem 8 we design a polynomial-time algorithm that finds an ε-approximate Nash equilibrium with constant support size and with social welfare at least (1 - ε(1-ε) 2-3ε ) ≥ 0.5 times the optimum social welfare. For this case we will prove that if the optimum social welfare is less than 2-3ε 1-ε , we need logarithmic support in order to create an ε-Nash equilibrium.

We will prove Theorem 1 in Section 3 and Theorems 2 and 3 in Section 4.

2 Preliminaries

Consider a two-player normal form game with n strategies in the disposal of every player and let (R,C) be the payoff matrices in [0, 1]n×n of the row player and the column player respectively. If the row player plays the strategy i and the column player plays the strategy j then the row player's payoff is Rij and the column player's payoff is Cij. A mixed strategy x ∈ [0, 1]n is a column vector that describes a probability distribution on the n pure strategies of a player; a support of a mixed strategy x is the set of the pure strategies i such that xi > 0. Note that if the row player plays a mixed strategy x and the column player plays a mixed strategy y the expected payoff of the row player is xT Ry and the expected payoff of the column player is xT Cy. The social welfare is the total payoff of both players, i.e., it is cost = xT Ry + xT Cy = xT (R + C)y.

A Nash equilibrium is a strategy profile (x∗ , y∗ ) such that

where ei ∈ [0, 1]n is the column vector with 1 in its coordinate i and 0 elsewhere.

For any ε ≥ 0, an ε-approximate Nash equilibrium is any strategy profile (x∗ , y∗ ) such that

Note that a 0-Nash equilibrium is a (exact) Nash equilibrium.

Throughout the paper, we let (i, j) to denote the pure strategy profile that maximizes the sum of the payoffs of the two players (utilitarian objective). We define opt to be the optimal social welfare, that is,

(Note that i and j can be trivially found in O(n2 ) time.)

We define the pure strategy r of the row player as the best response strategy of the row player to the strategy j of the column player and the pure strategy c of the column player as the best response strategy of the column player to the strategy i of the row player. The optimality of the profile (i, j) yields:

The central goal of this paper is for a fixed ε ∈ [0, 1], to find an ε-approximate Nash equilibrium strategy profile (x∗ , y∗ ) whose social welfare cost is as close to opt as possible.

In our analysis, we will consider several cases depending on the values of Rrj -Rij and Cic -Cij:

• Rrj -Rij ≤ ε and Cic -Cij ≤ ε,
• Rrj -Rij ≥ ε and Cic -Cij > ε (and the symmetric case Rrj - Rij > ε and Cic - Cij ≥ ε),
• Rrj -Rij < ε and Cic -Cij > ε (and the symmetric case Rrj - Rij > ε and Cic - Cij < ε).

We will use the fact that in the first case, when Rrj -Rij ≤ ε and Cic - Cij ≤ ε, the strategy profile (i, j) (which can be found in polynomial time) is an ε-approximate Nash equilibrium, and since it has the optimal social welfare, in this case we can find an optimal solution by choosing strategy (i, j). Thus, our main task will be to find a good algorithm to construct an ε-approximate Nash equilibrium in the other cases.

In our analysis, we will separately consider two regimes: one when ε ≥ 1 2 and one when ε < 12 .

3 Approximation with ε ≥ 12

We begin with the scenario when ε ≥ 12 , proving Theorem 1. We will show in Section 3.1 that if ε ≥ 1 2 , then one can find an ε-approximate Nash equilibrium with constant size support that has an almost optimal social welfare, at least 2√ε - ε ≥ 0.914 times the optimal social welfare. We will also prove that our bound is tight for any ε ≥ 12 , by showing in Section 3.2 explicit bimatrix games for which every ε-approximate Nash equilibrium has social welfare no more than 2√ε - ε times the optimal social welfare.

Let us recall that (i, j) is the pure strategy profile that maximizes the sum of the payoffs of the two players, and hence opt = Rij + Cij (cf. (1)). Let us recall that r is the pure strategy of the row player that is the best response strategy of the row player to the strategy j of the column player and that c is the pure strategy of the column player that is the best response strategy of the column player to the strategy i of the row player. We will now consider several cases depending on the values of Rrj - Rij and Cic - Cij .

Let us first note that it is impossible to have Rrj -Rij ≥ ε and Cic-Cij > ε, or to have Rrj-Rij > ε and Cic-Cij ≥ ε (since these cases are symmetric, we will focus only on the first one). To show that we cannot have Rrj -Rij ≥ ε and Cic -Cij > ε, we first observe that these inequalities yield:

Next, Rrj - Rij ≥ ε together with (3) yield Rij + Cij ≥ Rrj +Crj ≥ Rij +ε+Crj , what implies Cij ≥ ε. Similarly, Cic - Cij > ε and (2) give Rij + Cij ≥ Ric + Cic > Ric + Cij + ε, and hence Rij > ε. Now, however, we observe that with the assumption ε ≥ 1 2 , the inequalities above form a contradiction, and therefore this case cannot happen.

Since we cannot have either of the cases Rrj - Rij ≥ ε and Cic -Cij > ε, or Rrj -Rij > ε and Cic -Cij ≥ ε, we only have to consider one of the following three scenarios: (1) Rrj -Rij ≤ ε and Cic -Cij ≤ ε, (2) Rrj -Rij < ε and Cic - Cij > ε, (3) Rrj - Rij > ε and Cic - Cij < ε.

We will now consider these cases, depending on the values of Rrj -Rij and Cic -Cij:

1. If Rrj - Rij ≤ ε and Cic - Cij ≤ ε, then we know that the strategy profile (i, j) is an ε-approximate Nash equilibrium with the optimal social welfare.

and that (2) yields Rij - Ric ≥ Cic - Cij > ε. Next, we prove a key lemma describing an ε-approximate Nash equilibrium in our setting.

Lemma 4 Let ε ∈ [ 1 2 , 1], Rrj-Rij < ε, and Cic-Cij > ε. Let p = ε Cic-Cij . The strategy profile (i, pj+(1-p)c), where p is the probability for the column player to play strategy j and (1-p) is the probability of playing strategy c respectively, is an ε-approximate Nash equilibrium.

Proof. Let us first notice that p is well defined with 0 < p ≤ 1 since 0 < ε < Cic - Cij .

Let b be the best response strategy of the row player to the strategy pj + (1 - p)c of the column player. If the row player plays strategy i, her incentive to deviate is:

The first inequality follows from Rbj ≤ Rrj and Rbc ≤ 1, the second one because of the fact that Rrj ≤ 1 and Ric ≥ 0, the third one because Rij +Cij ≥ Ric +Cic, and the final one follows from the fact that ε ≥ 1 2 .

On the other hand, the incentive to deviate for the column player when the row player plays i is Cic - pCij - (1 - p)Cic = ε. Hence the strategy profile (i, pj + (1 - p)c) is an ε-approximate Nash equilibrium. ⊓ ⊔

1. Rrj-Rij > ε and Cic-Cij < ε is symmetric to case (2).

3.1 Upper bound in Theorem 1

We now prove that ε-APPROXIMATE NASH (R,C, ε) presented below, returns an ε-approximate Nash equilibrium with social welfare at least (2√ε - ε)opt. By the arguments above, we only have to consider the following scenarios: (1) Rrj-Rij ≤ ε and Cic-Cij ≤ ε, (2) Rrj-Rij < ε and Cic - Cij > ε, (3) Rrj - Rij > ε and Cic - Cij < ε.

ε-APPROXIMATE NASH (R, C, ε)

• Find i, j such that Rij +Cij is maximized.
• Find r, c such that Rrj is maximized and Cic is maximized.
• If Rrj -Rij ≤ ε and Cic -Cij ≤ ε, then return strategy profile (i, j).
• If Rrj-Rij < ε andCic-Cij > ε, then set p = ε Cic-Cij and return strategy profile (i, pj + (1 - p)c).
• If Rrj-Rij > ε andCic-Cij < ε, then set p = ε Rrj -Rij and return strategy profile (pi + (1 - p)r, j).

Let us recall that if Rrj -Rij ≤ ε and Cic -Cij ≤ ε, then the strategy (i, j) is an ε-approximate Nash equilibrium with social welfare opt, and therefore the algorithm will return an optimum solution that is an ε-approximate Nash equilibrium. Therefore, we only have to consider scenarios (2) and (3). Since these scenarios are symmetric, we focus only on scenario (2), when Rrj - Rij < ε and Cic - Cij > ε: we prove that the strategy profile (i, pj + (1 - p)c) with p = ε Cic-Cij has social welfare at least (2√ε - ε)opt.

The social welfare of our solution is cost = p(Rij +Cij )+ (1 - p)(Ric + Cic). Let

Observe that if we consider the last bound as a function of Rij, we obtain a function of the form f(x) = x+β px+γ , with 0 ≤ p ≤ 1, β = Cij and γ = pCij + (1 - p)Cic. Notice further that since by (5), we have pCij +(1-p)Cic > pCij + (1 - p)Cij = Cij ≥ 0, we obtain γ > β ≥ 0. Therefore, by considering the derivative f ′ (x) = γ-pβ (px+γ)2 > 0, we observe that f is increasing in x. Thus, the right hand side of (6) takes the maximum value when Rij is maximum, that is, is equal to 1, independently from the other variables. Hence,

We note that the right hand side of (7) takes maximum when Cic = Cij + √ε, and hence when p = √ε. If we plug this in (7), then we obtain ρ ≤ 1+Cij 2√ε-ε+Cij . Next, we observe that since ε ∈ [ 12 , 1] we have 2√ε-ε ≤ 1, and hence the right hand side of is decreasing and takes the maximum at Cij = 0. Therefore ρ ≤ 1 2√ε-ε . This completes the proof of the first part (upper bound) of Theorem 1.

Figure 1 depicts the upper bound as a function of ε.

3.2 Lower bound in Theorem 1

We now show the second part of Theorem 1 and for every ε ∈ [ 1 2 , 1], we present a game for which the social welfare of every ε-approximate Nash equilibrium is at most (2√ε - ε)opt.

Fix ε, 12 ≤ ε ≤ 1. Consider a bimatrix game with one strategy for the row player, strategy i, and with two strategies for the column player, strategies j and c. Set Rij = 1, Cij = 0, Ric = 0, and Cic = √ε, resulting in the following game:

The optimal strategy is (i, j) with the social welfare opt = 1. In order to obtain an ε-approximate Nash equilibrium the column player needs to randomize between her strategies, playing strategy j with probability p and strategy c with probability (1 - p). Then, the strategy profile (i, pj + (1 - p)c) is an ε-approximate Nash equilibrium if and only if √ε ≤ (1-p)√ε+ε. This is equivalent to p ≤ √ε. Conditioned on this, we bound the social welfare of any ε-approximate Nash equilibrium for this game. For any 0 ≤ p ≤ √ε, if we denote the social welfare of an ε-approximate Nash equilibrium with fixed p by costp, then we obtain, costp = p + (1 - p)√ε ≤ √ε + √ε(1 - √ε) = 2√ε - ε. Therefore, since opt = 1, we conclude that for the game defined above, the social welfare of every ε-approximate Nash equilibrium is at most 2√ε - ε times the optimal social welfare. This completes the proof of the second part (lower bound) of Theorem 1.

3.3 Win-lose games with ε ≥ 12

We note that for the class of win-lose games, one can easily show the following stronger bound.

Theorem 5 For any win-lose bimatrix game with values in {0,1} and any ε ∈ [ 12 , 1], we can find in polynomial time an ε-approximate Nash equilibrium with optimal social welfare.

4 Approximation with ε < 12

The analysis of the case ε < 12 is more complicated and our results are not as tight as those for the case ε ≥ 1 2 . One important reason why this case is more challenging is that for ε < 12 , we know that we have to consider large support size of the strategies. This follows from [Feder et al., 2007], who showed that for ε < 12 , to find an ε-approximate-Nash equilibrium the support needs to be of size logarithmic in the number of strategies available to the players.

We begin with a general transformation that takes an arbitrary ε∗ -approximate Nash equilibria with arbitrary social welfare and outputs an ε-approximate Nash equilibrium, ε∗ < ε, with social welfare at least a constant fraction the optimal social welfare. This is achieved by considering an appropriate mixture of a strategy profile with the optimal social welfare and an ε∗ -approximate Nash equilibrium. We also show that our transformation runs in polynomial time, and thus if there is a polynomial-time algorithm finding an ε∗ -approximate Nash equilibrium then our scheme can find in polynomial time an ε-approximate Nash equilibrium, ε∗ < ε, with social welfare at least a constant fraction the optimal social welfare. Next, we will analyze the special case where the social welfare is greater or equal to 2-3ε 1-ε , when we find ε-approximate Nash equilibria with high social welfare.

4.1 Reducing social welfare

As mentioned earlier, if ε < 1 2 then we cannot hope to find an ε-approximate Nash equilibrium with constant size support, which is the approach we used in Section 3. However, we will show that using an existing ε∗ -approximate Nash equilibrium, ε∗ < ε, with an arbitrary social welfare, we can construct an ε-approximate Nash equilibrium with social welfare that is at least a constant times optimal, to conclude Theorem 2. We begin with the following key lemma.

Lemma 6 Let 0 ≤ ε∗ < 1, and ε∗ < ε < 1. Let (x∗ , y∗ ) be the strategy profile of an ε∗ -approximate Nash equilibrium. Then, for p = 1 - √(1- ε)/(1- ε∗ ), the strategy profile (pi + (1 - p)x∗ , pj + (1 - p)y∗ ) is an ε-approximate Nash equilibrium with the social welfare cost ≥ p2 opt.

Proof. Since (x∗ , y∗ ) is a strategy profile of an ε∗ - approximate Nash equilibrium, the maximum incentive to deviate for any player in the strategy profile (x∗ , y∗ ) is ε∗ . Therefore, since under strategies (i, j), (i, y∗ ), (x∗ , j) no player can improve its payoff by more than 1, we obtain that if the players play the strategy profile (pi + (1 - p)x∗ , pj + (1 - p)y∗ ), then the maximum incentive to deviate for any player is upper bounded by the following:

Hence, to ensure that this strategy is an ε-approximate Nash equilibrium for 0 ≤ ε∗ < ε < 1, we set p =

1 - √(1 - ε)/(1 - ε∗ ). It is easy to check that 0 ≤ p ≤ 1.

Proof of Theorem 2: We choose ε∗ = 0 in Lemma 6 (here we use Nash theorem [Nash, 1951] to guarantee the existence of an exact Nash equilibrium (x∗ , y∗ )) to ensure that one can use the strategy profile (pi + (1 - p)x∗ , pj + (1 - p)y∗ ) with p = 1- √1 - ε to obtain an ε-approximate Nash equilibrium with cost ≥ p2 opt = (1 - √1 - ε)2 opt. ⊓ ⊔

Our construction above can be trivially transformed into a polynomial time algorithm, assuming that we have at hand a polynomial-time algorithm for finding an ε∗ -approximate Nash equilibrium in any bimatrix game. This proves Theorem 3 with ζε,ε∗ = (1-√ 1-ε 1-ε∗ )2 . Since the best currently known value for ε∗ is 0.3393 [Tsaknakis and Spirakis, 2008], this approach works (currently) only for ε > 0.3393.

4.2 Analysis of the case opt ≥ 2-3ε 1-ε

We consider a special case, when opt ≥ 2-3ε 1-ε , for which we can construct approximate Nash equilibria with high social welfare. We will show in Theorem 8 that there is a good ε-approximate Nash equilibrium that has a constant size support and high social welfare. This result is complemented by Theorem 9 that shows that if opt < 2-3ε 1-ε , then an ε-Nash equilibrium may require a logarithmic size support.

Lemma 7 Let ε ∈ [0, 12 ), Rrj -Rij < ε, Cic-Cij > ε, and p = 1-ε -1+2ε+2Rij(1-ε) . If opt ≥ 2-3ε 1-ε then the strategy profile (i, pj + (1 - p)c) is an ε-approximate Nash equilibrium with social welfare greater than 2-4ε+ε2 2-3ε ·opt = (1- ε(1-ε) 2-3ε )·opt.

Proof. We first show that p is well defined with 0 ≤ p ≤ 1. Since Cic - Cij > ε, we get Cij < 1 - ε. Thus, if opt ≥ 2-3ε 1-ε , then opt = Rij + Cij yields Rij ∈ ( 1-ε-ε2 1-ε , 1] and Cij ∈ [ 1-2ε 1-ε , 1 - ε). Hence, -1 + 2ε + 2Rij(1 - ε) > -1+2ε+2(1-ε-ε2 ) ≥ 1-ε, and thus p is well defined.

Next, we prove that the strategy profile (i, pj + (1 - p)c) is an ε-approximate Nash equilibrium. Let b be the best response strategy of the row player to the strategy profile

(pj + (1 - p)c) of the column player. Then the incentive of the row player to deviate from strategy i is:

and the incentive of the column player to deviate is:

Here we use the facts that c is the best response strategy of the column player to the strategy i of the row player, and that Cic ≤ 1 and Cij = opt - Rij ≥ 2-3ε 1-ε -Rij.

Therefore 1 - pRij ≤ -1+2ε+(1-ε) -1+2ε+2(1-ε) = ε, what implies that the strategy profile (i, pj + (1 - p)c) is an ε-approximate Nash equilibrium. This yields the following lower bound for the social welfare cost of the strategy profile (i, pj+(1-p)c):

With Lemma 7 at hand, we can prove the following.

Theorem 8 Let ε ∈ [0, 12 ) and opt ≥ 2-3ε 1-ε . Then one can find in polynomial-time an ε-approximate Nash equilibrium with constant support size and with social welfare at least (1 - ε(1-ε) 2-3ε ) · opt ≥ 0.5 · opt.

Proof. We consider three cases:

• If Rrj -Rij ≤ ε and Cic -Cij ≤ ε, then the strategy profile (i, j) is an ε-approximate Nash equilibrium with cost = opt.
• If Rrj -Rij ≥ ε and Cic -Cij > ε (the Rrj -Rij > ε and Cic-Cij ≥ ε is symmetric), then opt = Rij+Cij < (Rrj - ε) + (Cic - ε) ≤ 2(1 - ε). But is impossible if at the same time ε < 1 2 and opt ≥ 2-3ε 1-ε , and therefore this case cannot happen.
• Finally, if Rrj -Rij < ε and Cic -Cij > ε (the case Rrj -Rij > ε and Cic-Cij < ε is symmetric), then by Lemma 7, the strategy profile (i, pj +(1-p)c) with p = 1-ε -1+2ε+2Rij (1-ε) , is an ε-approximate Nash equilibrium

The bound (1- ε(1-ε) 2-3ε )opt ≥ 12 opt follows from the fact that in the interval ε ∈ [0, 1 2 ], function 1- ε(1-ε) 2-3ε is non-increasing in ε, and hence it is minimized at ε = 12 with the value 12 . All required strategies can be found in polynomial-time. ⊓ ⊔

Theorem 8 ensures that if opt ≥ 2-3ε 1-ε and ε < 12 , then we can create an ε-approximate Nash equilibrium with social welfare greater than or equal to 12 opt, which is a superior upper bound to the general case from Theorem 2.

Lower bound. We can prove also a lower bound that for any ε ≤ 1 2 , if opt = 2-3ε 1-ε then for any ˆ ε < ε, we may need support of size Ω(log n) to construct an ˆ ε-Nash equilibrium.

Theorem 9 Let ε ≤ 12 . There exists a bimatrix game (R, C) in [0, 1]n×n for which the maximum sum of the payoffs of the players is opt = 2-3ε 1-ε , and for any ˆ ε < ε, any ˆ ε-Nash equilibrium requires logarithmic support.

Proof. Let k = logn - 2 log logn. Let (R,C) be the two payoff matrices in [0, 1]n×n in which every entry is chosen independently at random from the set {(1, 1-2ε 1-ε ), (0, 1)}. We consider the row player; the case of the column player is analogous. We will show that with high probability, for any k columns in the payoff matrix of the column player, there is at least one row that has all 1s in these k columns.

Fix any set of k columns. The probability that a single row has at least one 0 in these k columns is 1 - 2-k . Thus, the probability that every row has at least one 0 in these k columns is (1 - 2-k )n . Hence, the probability that there is a set of k columns for which all rows have at least one 0 in these k columns is at most (nk)(1 - 2-k )n . Since our choice of k yields (nk)(1 - 2-k )n ≪ 1, we conclude that with high probability, for every set of k columns there is at least one row that has all 1s in these k columns. Analogous arguments hold for the column player. Let us condition on the two events and assume that for every set of k columns in the payoff matrix of the row player there is a row that has all 1s in these columns, and that for every set of k rows in the payoff matrix of the column player there is a column that has all 1s in these rows.

Let us assume that there is an ˆ ε-Nash equilibrium (x∗ , y∗ ) for some ˆ ε < ε ≤ 12 , with the support of size k. Let p = ∑ℓ,m x∗ℓ y∗m, where the sum is over all pairs (ℓ,m), 1 ≤ ℓ,m ≤ n, such that (Rℓm,Cℓm) = (1, 1-2ε 1-ε ). p is the probability that the players play the strategy profile (1, 1-2ε 1-ε ) in the ˆ ε-Nash equilibrium, and 1 - p is the probability that the players play the strategy profile (0, 1) in the ˆ ε-Nash equilibrium. The expected payoff of the row player is p, and the expected payoff of the column player is p ( 1-2ε 1-ε ) + (1 - p).

Since (x∗ , y∗ ) is an ˆ ε-Nash equilibrium, p + ˆ ε ≥ 1 for the row player, and thus p > 1-ε. Hence, the expected payoff of the column player is p ( 1-2ε 1-ε )+(1-p) = 1- pε 1-ε < 1-ε < 1- ˆ ε. But this contradicts the condition for the column player in the assumption that (x∗ , y∗ ) is an ˆ ε-Nash equilibrium. ⊓ ⊔