Approximate Well-supported Nash Equilibria below Two-thirds

Introduction

In a bimatrix game, a Nash equilibrium is a pair of strategies in which the two players only assign probability to best response strategies. The apparent hardness of computing an exact Nash equilibrium DGP ; CDT has led to work on computing approximate Nash equilibria, and two notions of approximate Nash equilibria have been developed. The first, and more widely studied, notion is of an $\epsilon$-approximate Nash equilibrium ($\epsilon$-Nash), where each player is required to achieve an expected payoff that is within $\epsilon$ of a best response. A line of work DMP ; Progress ; Bosse has investigated the value of $\epsilon$ that can be guaranteed in polynomial time. The current best result in this setting is a polynomial time algorithm that always finds a 0.3393-Nash equilibrium TS .

However, $\epsilon$-Nash equilibria have a drawback: since they only require that the expected payoff is within $\epsilon$ of a pure best response, it is possible that a player could be required to place probability on a strategy that is arbitrarily far from being a best response. This issue is addressed by the second notion of an approximate Nash equilibrium. An $\epsilon$-well supported approximate Nash equilibrium ($\epsilon$-WSNE), requires that both players only place probability on strategies that have payoff within $\epsilon$ of a pure best response. This is a stronger notion of equilibrium, because every $\epsilon$-WSNE is an $\epsilon$-Nash, but the converse is not true.

In contrast to $\epsilon$-Nash, there has been relatively little work $\epsilon$-WSNE. The first result on the subject gave a $\frac{5}{6}$ additive approximation DMP , but this only holds if a certain a graph-theoretic conjecture is true. The best-known polynomial-time additive approximation algorithm was given by Kontogiannis and Spirakis, and achieves a $\frac{2}{3}$-approximation KS . We will call this algorithm the KS algorithm. In KS07 , which is an earlier conference version of KS , the authors presented an algorithm that they claimed was polynomial-time and achieves a $\phi$-WSNE, where $\phi=\frac{\sqrt{11}}{2}-1\approx 0.6583$, but this was later withdrawn, and instead the polynomial-time $\frac{2}{3}$-approximation algorithm was presented in KS . Recently, it has been shown that for every $\delta>0$, a $(\frac{1}{2}+\delta)$-WSNE can be found in polynomial times for symmetric bimatrix games CFJ14 . It has also been shown that there is a PTAS for $\epsilon$-WSNE if and only if there is a PTAS for $\epsilon$-Nash CDT .

In this paper, we develop an algorithm for finding an $\epsilon$-WSNE with $\epsilon<\frac{2}{3}$. Our approach to modifying the KS algorithm for finding a $\frac{2}{3}$-WSNE, by adding two additional procedures: we perform a brute-force search that finds the best WSNE with a $2\times 2$ support, and we attempt to improve the $\epsilon$-WSNE returned by the KS algorithm by shifting the probabilities of the two players. We show that one of these two approaches will always find an $\epsilon$-WSNE with $\epsilon=\frac{2}{3}-0.005913759$. Our results are particularly interesting when compared to a recent support size lower bound of Anbalagan, Norin, Savani, and Vetta, who showed that there exist games in which all $\epsilon$-WSNE with $\epsilon<\frac{2}{3}$ have super-constant sized supports ANSV13 .

A preliminary version of this paper was published in the proceedings of SAGT 2012 SAGT . In that version of the paper, we gave a polynomial time algorithm for finding an $\epsilon$-WSNE with $\epsilon=\frac{2}{3}-0.004735$. It turns out that one of the inequalities used to show this resultThe inequality in question appeared in Proposition 16 of the preliminary version, and is now part of Proposition 7. was not as strong as it could have been, and correcting this led to the improved bound in this version of the paper. We have also greatly simplified the computer-assisted proof that is used at the end of the paper. The preliminary version of the paper used a rather opaque method involving sensitivity analysis of a linear program. We have reformulated the LP so that the relevant values can be read directly from the solution of the LP.

The paper will proceed as follows. In Section 2 we give the basic definitions that will be needed in this paper. In Section 3 we give a high level overview of our algorithms, along with the intuition behind our two modifications. In Section 4, we formally define our algorithm and state our main theorem. In Section 5 we give a high level overview of the proof, before then proceeding with the proof in Sections 6 through 9.

Definitions

A bimatrix game is a pair $(R,C)$ of two $n\times n$ matrices: $R$ gives payoffs for the row player, and $C$ gives payoffs for the column player. We assume that all payoffs are in the range $$. We use$[n]=\{1,2,\ldots n\}$to denote the pure strategies for each player. 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$R_{i,j}$, and the column player receives$C_{i,j}$.

A mixed strategy is a probability distribution over $[n]$. We denote a mixed strategy as a vector $\mathbf{x}$ of length $n$, such that $\mathbf{x}_{i}$ is the probability that the pure strategy $i$ is played. The support of mixed strategy $\mathbf{x}$, denoted $\operatorname{Supp}(\mathbf{x})$, is the set of pure strategies $i$ with $\mathbf{x}_{i}>0$. If $\mathbf{x}$ and $\mathbf{y}$ are mixed strategies for the row and column player, respectively, then we call $(\mathbf{x},\mathbf{y})$ a mixed strategy profile.

Let $\mathbf{y}$ be a mixed strategy for the column player. The 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. A mixed strategy profile $(\mathbf{x},\mathbf{y})$ is a mixed Nash equilibrium if every pure strategy in $\operatorname{Supp}(\mathbf{x})$ is a best response against $\mathbf{y}$, and every pure strategy in $\operatorname{Supp}(\mathbf{y})$ is a best response against $\mathbf{x}$. Nash N showed that all bimatrix games have a mixed Nash equilibrium.

An approximate well-supported Nash equilibrium weakens the requirements of a mixed Nash equilibrium. For a mixed strategy $\mathbf{y}$ of the column player, a pure strategy $i\in[n]$ is an $\epsilon$-best response for the row player 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}-\epsilon$. We define $\epsilon$-best responses for the column player analogously. A mixed strategy profile $(\mathbf{x},\mathbf{y})$ is an $\epsilon$-well-supported Nash equilibrium ($\epsilon$-WSNE) if every pure strategy in $\operatorname{Supp}(\mathbf{x})$ is an $\epsilon$-best response against $\mathbf{y}$, and every pure strategy in $\operatorname{Supp}(\mathbf{y})$ is an $\epsilon$-best response against $\mathbf{x}$.

Outline

Before we give a technical presentation of our algorithm, we begin by giving the high level ideas behind our techniques. Our approach builds upon the algorithm of Kontogiannis and Spirakis for finding a $\frac{2}{3}$-WSNE, so let us begin by describing their algorithm. Given a bimatrix game $(R,C)$, the KS algorithm performs two steps:

Check if there is a pure strategy profile under which both players get payoff at least $\frac{1}{3}$. If so, that pure strategy profile is a $\frac{2}{3}$-WSNE.

Construct the zero-sum game $(D,-D)$ where $D=\frac{1}{2}(R-C)$, and let $(\mathbf{x},\mathbf{y})$ be a Nash-equilibrium of $(D,-D)$.

Kontogiannis and Spirakis showed that if step 1 failed to find a pure $\frac{2}{3}$-WSNE of $(R,C)$, then $(\mathbf{x},\mathbf{y})$ is a $\frac{2}{3}$-WSNE of $(R,C)$. Our goal is to show that the WSNEs found by the KS algorithm can be improved: either by shifting probabilities, or by finding a matching pennies sub-game. We now show the motivation behind these two procedures.

Matching pennies

Our approach

We will show that one of these two techniques can always be applied. Our algorithm will first perform a brute force search over all $2\times 2$ sub-games in order to determine whether there is a matching pennies sub game. If such a game is not found, then we run the KS algorithm and attempt to shift probabilities in the resulting strategy profile. Ultimately, we show that this algorithm always produces a $(\frac{2}{3}-0.005913759)$-WSNE.

Our Algorithm

In this section we formally describe our algorithm for finding a WSNE. We begin by describing a method for finding the best WSNE on a given pair of supports, and then move on to describe the three procedures that make up our algorithm.

Let $S_{c}$ and $S_{r}$ be supports for the column and row player, respectively. We first define an LP, which assumes that the row player uses a strategy with support $S_{r}$, and then finds a strategy on $S_{c}$ that minimizes the difference between the row player’s best response payoff, and the payoff of the strategies in $S_{r}$.

Similarly, the following LP assumes that the column player uses a strategy with support $S_{c}$, and finds a strategy on $S_{r}$ that minimizes the difference between the column player’s best response payoff, and the payoff of the strategies in $S_{c}$.

We now prove that these two LPs give a WSNE that is at least as good as the best WSNE on the supports $S_{r}$ and $S_{c}$. Let $(\mathbf{y}^{*},\epsilon_{\mathbf{y}})$ be a solution of $BestR(S_{r},S_{c})$, let $(\mathbf{x}^{*},\epsilon_{\mathbf{x}})$ be a solution of $BestC(S_{r},S_{c})$, and let $\epsilon^{*}$ to be $\max(\epsilon_{\mathbf{x}},\epsilon_{\mathbf{y}})$.

$(\mathbf{x}^{*},\mathbf{y}^{*})$ is an $\epsilon^{*}$-WSNE.

For every $\epsilon$-WSNE $(\mathbf{x},\mathbf{y})$ with $\operatorname{Supp}(\mathbf{x})=S_{r}$ and $\operatorname{Supp}(\mathbf{y})=S_{c}$, we have $\epsilon^{*}\leq\epsilon$.

The first claim is straightforward, because Constraint 1 ensures that every strategy $i\in\operatorname{Supp}(\mathbf{x}^{*})\subseteq S_{r}$ is an $\epsilon_{\mathbf{y}}$-best response against $\mathbf{y}^{*}$, and every strategy $j\in\operatorname{Supp}(\mathbf{y}^{*})\subseteq S_{c}$ is an $\epsilon_{\mathbf{x}}$-best response against $\mathbf{x}^{*}$. Therefore $(\mathbf{x}^{*},\mathbf{y}^{*})$ is a $\epsilon^{*}$-WSNE.

For the second claim, let $(\mathbf{x},\mathbf{y})$ be an $\epsilon$-WSNE on the supports $S_{r}$ and $S_{c}$. Since every row $i\in\operatorname{Supp}(\mathbf{x})=S_{r}$ is an $\epsilon$-best response against $\mathbf{y}$, we must have that $\mathbf{y}$ and $\epsilon$ are feasible in $BestR(S_{r},S_{c})$. For the same reason, we have that $\mathbf{x}$ and $\epsilon$ are feasible in $BestC(S_{r},S_{c})$. Therefore, we must have $\epsilon^{*}\leq\epsilon$.

Proposition 1 implies that $(\mathbf{x}^{*},\mathbf{y}^{*})$ is at least as good as the best WSNE on the supports $S_{r}$ and $S_{c}$. Note that it is possible that $(\mathbf{x}^{*},\mathbf{y}^{*})$ may actually be better than any WSNE on these supports, because the LPs do not require that $\mathbf{x}^{*}$ places probability on all strategies in $S_{r}$, or that $\mathbf{y}^{*}$ places probability on all strategies in $S_{c}$.

Our Algorithm

We now describe our algorithm for finding a WSNE in a bimatrix game. Our algorithm for finding a WSNE consists of three distinct procedures.

Procedure 1: find the best pure WSNE. The KS algorithm requires a preprocessing step that eliminates all games that have a pure $\frac{2}{3}$-WSNE, and this is a generalisation of that step. Suppose that the row player plays row $i$, and that the column player plays column $j$. Let: $\epsilon_{r}=\max_{i^{\prime}}(R_{{i^{\prime}},j})-R_{i,j}$, and $\epsilon_{c}=\max_{j^{\prime}}(C_{i,{j^{\prime}}})-C_{i,j}$. Thus $i$ is an $\epsilon_{r}$-best response against $j$, and that $j$ is an $\epsilon_{c}$-best response against $i$. Therefore, $(i,j)$ is a $\max(\epsilon_{r},\epsilon_{c})$-WSNE. We can find the best pure WSNE by checking all $O(n^{2})$ possible pairs of pure strategies. Let $\epsilon_{p}$ be the best approximation guarantee that is found by this procedure.

Procedure 2: find the best WSNE with $2\times 2$ support. We can use the linear programs from Definitions 1 and 2 to implement this procedure. For each of the $O(n^{4})$ possible $2\times 2$ supports, we solve the LPs to find a WSNE. Proposition 1 implies that this WSNE is at least as good as the best WSNE on those supports. Let $\epsilon_{m}$ be the best approximation guarantee that is found by this procedure.

Procedure 3: find an improvement over the KS algorithm. The KS algorithm finds an exact Nash equilibrium $(\mathbf{x},\mathbf{y})$ of the zero-sum game $(D,-D)$, where $D=\frac{1}{2}(R-C)$. To find an improvement over the KS algorithm we use the linear programs from Definitions 1 and 2 with parameters $S_{r}=\operatorname{Supp}(\mathbf{x})$ and $S_{c}=\operatorname{Supp}(\mathbf{y})$. Let $(\mathbf{x}^{*},\mathbf{y}^{*})$ be the mixed strategy profile returned by the LPs, and let $\epsilon_{i}$ be the smallest value such that $(\mathbf{x}^{*},\mathbf{y}^{*})$ is a $\epsilon_{i}$-WSNE.

After executing these three procedures, we take the smallest of $\epsilon_{p}$, $\epsilon_{m}$, and $\epsilon_{i}$, and return the corresponding WSNE. Since all three procedures can be implemented in polynomial time, this is a polynomial time algorithm. The rest of this paper is dedicated to proving the following theorem.

Our algorithm finds a $(\frac{2}{3}-0.005913759)$-WSNE.

Proof Outline

In order for our proof to be as informative as possible, we will parameterize it using a constant $z>0$. We will show the conditions under which our algorithm can produce a $(\frac{2}{3}-z)$-WSNE. At the end of the proof we will show that these conditions are satisfied for $z=0.005913759$, which provides a proof Theorem 4.1.

Our approach is to assume that Procedures 1 and 2 did not produce a $(\frac{2}{3}-z)$-WSNE, and then to use that assumption to determine the conditions under which Procedure 3 does find a $(\frac{2}{3}-z)$-WSNE. This comprises of the following steps.

Reanalyze the KS algorithm. The original analysis for the KS algorithm assumed that the game does not have a pure $\frac{2}{3}$-WSNE. However, in our analysis, we have assumed only that Procedure 1 did not find a pure $(\frac{2}{3}-z)$-WSNE, so the original KS analysis is no longer valid. In Section 6 we show that, assuming there is no pure $(\frac{2}{3}-z)$-WSNE, the KS algorithm will produce a strategy profile $(\mathbf{x},\mathbf{y})$ where all strategies have payoff at most $\frac{2}{3}+2z$, and therefore $(\mathbf{x},\mathbf{y})$ is a $(\frac{2}{3}+2z)$-WSNE.

Study the bad strategies. Our goal is to show that $(\mathbf{x},\mathbf{y})$ can be improved from a $(\frac{2}{3}+2z)$-WSNE to a $(\frac{2}{3}-z)$-WSNE. To achieve this, we show how to reduce the payoffs of all strategies from $\frac{2}{3}+2z$ to $\frac{2}{3}-z$. While describing our approach, we will focus on the row player, but all of our techniques will actually be applied to both players. We define a bad row to be a row that has payoff strictly more than $\frac{2}{3}-z$. In Section 7 we study the properties of bad rows, and we prove that all bad rows are similar in structure to the games shown in Figures 1 and 2. That is, most of the columns in a bad row are either big (ie. close to $1$,) or small (ie. close to $\frac{1}{3}$.) We prove lower bounds on the amount of probability that the column player’s strategy assigns to big and small payoffs. We then define a new strategy for the column player $\mathbf{y}^{\text{imp}}$, that finds the worst bad row ${\bar{\imath}}$ (ie. the row with the largest payoff,) and shifts all probability from the big columns in ${\bar{\imath}}$ to the small columns in ${\bar{\imath}}$.

Apply the matching pennies argument. In Section 8 we use the fact that Procedure 2 did not find an $\epsilon$-WSNE on a $2\times 2$ support with $\epsilon<\frac{2}{3}-z$. Intuitively, this corresponds to ruling out cases like the one shown in Figure 2. We prove that, if Procedure 2 failed to find a $(\frac{2}{3}-z)$-WSNE, then the bad rows cannot be arranged like they are in Figure 2. This gives a formal condition on how the probability of $\mathbf{y}$ can be distributed over the columns of the bad rows, which will be used later in the proof.

Find an improved strategy. Since the strategy shifts all probability from big payoffs in row ${\bar{\imath}}$ to small payoffs in row ${\bar{\imath}}$, by definition, we must have that the payoff of ${\bar{\imath}}$ against $\mathbf{y}^{\text{imp}}$ is small. However, the payoff of other rows may increase as we move from $\mathbf{y}$ and $\mathbf{y}^{\text{imp}}$. We must find a trade-off between the bad rows decreasing in payoff, and other rows increasing in payoff, so we define a strategy $\mathbf{y}(t)=(1-t)\cdot\mathbf{y}+t\cdot\mathbf{y}^{\text{imp}}$, which mixes between $\mathbf{y}$ and $\mathbf{y}^{\text{imp}}$. We show that there exists a $t$ such that all rows $i$ have payoff less than or equal to $\frac{2}{3}-z$ against $\mathbf{y}(t)$. In Section 9 we develop a computer assisted proof for this task. For each $z$ and $t$ we formulate a linear program that gives the largest possible payoff of a row against $\mathbf{y}(t)$, and then we perform a grid search over $z$ and $t$ in order to find a strategy $\mathbf{y}(t)$ against which all rows have payoff at most $\frac{2}{3}-z$. Ultimately, we find that this occurs for $z=0.005913759$, which proves Theorem 4.1.

Before we continue with the proof, we justify why it is possible to treat the two players independently in our analysis. In our proof, we will start with a strategy profile $(\mathbf{x},\mathbf{y})$. At a high level, the idea is to rearrange the probabilities in $\mathbf{x}$ to create $\mathbf{x}^{\prime}$ such that the column player happier when he plays $\mathbf{y}$ against $\mathbf{x}^{\prime}$. Simultaneously, we rearrange the probabilities in $\mathbf{y}$ to create $\mathbf{y}^{\prime}$ such that the row player is happier when he plays $\mathbf{x}$ against $\mathbf{y}^{\prime}$. We then claim that both players are happier in the profile $(\mathbf{x}^{\prime},\mathbf{y}^{\prime})$. To see why, observe that an approximate well supported Nash equilibrium is defined entirely by the supports that the strategies use. Since we only rearrange probabilities, ie. we have $\operatorname{Supp}(\mathbf{x}^{\prime})\subseteq\operatorname{Supp}(\mathbf{x})$ and $\operatorname{Supp}(\mathbf{y}^{\prime})\subseteq\operatorname{Supp}(\mathbf{y})$, it is sufficient to consider only $\mathbf{x}^{\prime}$ played against $\mathbf{y}$ and $\mathbf{y}^{\prime}$ played against $\mathbf{x}$ in order to prove properties of $(\mathbf{x}^{\prime},\mathbf{y}^{\prime})$.

Reanalyzing the KS algorithm

In this section we analyse the KS algorithm under the assumption that Procedure 1 did not find a $(\frac{2}{3}-z)$-WSNE. Note that if there is a pure strategy profile $(i,j)$, such that $R_{i,j}\geq\frac{1}{3}+z$ and $C_{i,j}\geq\frac{1}{3}+z$, then $(i,j)$ is a $(\frac{2}{3}-z)$-WSNE. Therefore, our assumption allows us to conclude that for all $i$ and $j$ we have:

This inequality replaces the inequality $0\leq R_{i,j}+C_{i,j}\leq\frac{4}{3}$, which was used in the original analysis.

From now on, our analysis will be stated for the row player, with the understanding that all of our proofs can be apply symmetrically to the column player. Our goal is to show that all “worst-case” examples for the KS algorithm are similar to Figures 1 and 2. More precisely, if $(\mathbf{x},\mathbf{y})$ is the strategy profile returned by the KS algorithm, then we are interested in the following properties of Figures 1 and 2:

There exists a row $i\in\operatorname{Supp}(\mathbf{x})$ such that $R_{i}\cdot\mathbf{y}=0$ and $C_{i}\cdot\mathbf{y}=0$.

Every row $i$ with $R_{i}\cdot\mathbf{y}=\frac{2}{3}$ also has $C_{i}\cdot\mathbf{y}=\frac{2}{3}$.

We will show that our “worst-case” examples have similar properties.

We begin with the first property. Here we show that, if $(\mathbf{x},\mathbf{y})$ is not a $(\frac{2}{3}-z)$-WSNE, then there exists a row in the row player’s support where both players have payoff close to .

If $(\mathbf{x},\mathbf{y})$ is a solution of $(D,-D)$ such that there is an $i\in\operatorname{Supp}(\mathbf{x})$ where $i$ is not a $(\frac{2}{3}-z)$-best response against $\mathbf{y}$ in $(R,C)$, then there is a row $i\in\operatorname{Supp}(\mathbf{x})$ such that both of the following hold:

We begin by noting that, since $D=\frac{1}{2}(R-C)$, if $X=-\frac{1}{2}(R+C)$, then we have two equalities:

Since $\mathbf{x}$ is a min-max strategy in $(D,-D)$, if $i$ is a row in $\operatorname{Supp}(\mathbf{x})$, then for all rows ${i^{\prime}}$ we have:

Let $i\in\operatorname{Supp}(\mathbf{x})$ be a row that is not a $(\frac{2}{3}-z)$-best response against $\mathbf{y}$, which exists by assumption, and let ${i^{\prime}}$ be a best-response against $\mathbf{y}$. We have:

Note that, by Equation (3), all entries of $X$ must lie in the range $[-\frac{2}{3}-\frac{1}{2}z,0]$. In particular, this implies that:

This implies that $-\frac{3}{2}z<X_{i}\cdot\mathbf{y}\leq 0$. Now, using the definition of $X$ we obtain:

Since both $R$ and $C$ are non-negative, we have completed the proof.

We now consider the second property. Here we show that, if $(\mathbf{x},\mathbf{y})$ is not a $(\frac{2}{3}-z)$-WSNE, then every row has payoff at most $\frac{2}{3}+2z$, and that for all rows $i$ we have that $R_{i}\cdot\mathbf{y}-C_{i}\cdot\mathbf{y}$ is small.

If $(\mathbf{x},\mathbf{y})$ is a solution of $(D,-D)$ such that there is an $i\in\operatorname{Supp}(\mathbf{x})$ where $i$ is not a $(\frac{2}{3}-z)$-best response against $\mathbf{y}$ in $(R,C)$, then for all rows ${i^{\prime}}$ both of the following hold:

Let $i$ be the row in $\operatorname{Supp}(\mathbf{x})$ whose existence is implied by Proposition 2. This proposition, along with the fact that all entries in $R$ and $C$ are non-negative, implies that:

By definition we have $D=\frac{1}{2}(R-C)$, and therefore, we have:

Now, since $x$ is a min-max strategy for the zero-sum game $(D,-D)$, we must have, for all rows ${i^{\prime}}$:

Rearranging this yields one of our two conclusions:

We can obtain the other conclusion by rearranging Equation (3), to argue that for all rows $i$ and all columns $j$ we have:

This implies that $2\cdot R_{{i^{\prime}}}\cdot\mathbf{y}\leq\frac{4}{3}+4z$, and so we have $R_{{i^{\prime}}}\cdot\mathbf{y}\leq\frac{2}{3}+2z$.

Proposition 3 shows that $R_{{i^{\prime}}}\cdot\mathbf{y}\leq\frac{2}{3}+2z$ holds for all rows ${i^{\prime}}$. Using the same argument symmetrically, we can also show that $C_{{j^{\prime}}}\cdot\mathbf{x}\leq\frac{2}{3}+2z$ for all columns ${j^{\prime}}$. Thus, we have shown that if there is no pure $(\frac{2}{3}-z)$-WSNE, then the KS algorithm will produce a mixed strategy pair $(\mathbf{x},\mathbf{y})$ that is a $(\frac{2}{3}+2z)$-WSNE.

The main goal of our proof is to show that the probabilities in $\mathbf{x}$ and $\mathbf{y}$ can be rearranged to construct a $(\frac{2}{3}-z)$-WSNE. From this point onwards, we only focus on improving the strategy $\mathbf{y}$, with the understanding that all of our techniques can be applied in the same way to improve the strategy $\mathbf{x}$. For the rest of the paper, we will fix $(\mathbf{x},\mathbf{y})$ to be the strategy profile produced by the KS algorithm, and we will assume that it is not a $(\frac{2}{3}-z)$-WSNE.

Bad Rows

In order to transform $(\mathbf{x},\mathbf{y})$ to a $(\frac{2}{3}-z)$-WSNE, we will ensure that there are no rows with payoff greater than $\frac{2}{3}-z$. Thus, we define a bad row to be a row $i$ whose payoff lies in the range $\frac{2}{3}-z<R_{i}\cdot\mathbf{y}\leq\frac{2}{3}+2z$. Furthermore, we classify the bad rows according to how bad they are.

A row $i$ is $q$-bad if $R_{i}\cdot\mathbf{y}=\frac{2}{3}+2z-qz$.

Since $(\mathbf{x},\mathbf{y})$ is a $(\frac{2}{3}+2z)$-WSNE, we have that every row is $q$-bad for some $q\geq 0$. Moreover, we are interested in improving the $q$-bad rows with $0\leq q<3$. In this section, we study the properties of $q$-bad rows, and we show that they must look similar to the bad rows in Figures 1 and 2.

To begin, we observe that if $i$ is a $q$-bad row, then we can apply the second inequality of Proposition 3 to obtain:

Now consider a $q$-bad row $i$ with $q<3$. We can deduce the following three properties about row $i$.

Definition 3 tells us that $R_{i}\cdot\mathbf{y}$ is close to $\frac{2}{3}$.

Equation (5) tells us that $C_{i}\cdot\mathbf{y}$ is close to $\frac{2}{3}$.

The fact that there are no pure $(\frac{2}{3}-z)$-WSNEs implies that, for each column $j$, we must either have $R_{i,j}<\frac{1}{3}+z$ or $C_{i,j}<\frac{1}{3}+z$, because otherwise $(i,j)$ would be a pure $(\frac{2}{3}-z)$-WSNE.

In order to satisfy all three of these conditions simultaneously, the row $i$ must have a very particular form: approximately half of the probability assigned by $\mathbf{y}$ must be given to columns $j$ where $R_{i,j}$ is close to $1$ and $C_{i,j}$ is close to $\frac{1}{3}$, and approximately half of the probability assigned by $\mathbf{y}$ must be given to columns $j$ where $R_{i,j}$ is close to $\frac{1}{3}$ and $C_{i,j}$ is close to $1$.

Building on this observation, we split the columns of each row $i$ into three sets. We define the set $B_{i}$ of big columns to be $B_{i}=\{j\;:\;R_{i,j}\geq\frac{2}{3}+2z\}$, and the set $S_{i}$ of small columns to be $S_{i}=\{j\;:\;C_{i,j}\geq\frac{2}{3}+2z\}$. Finally, we have the set of other columns $O_{i}=\{1,2,\dots,n\}\setminus(B_{i}\cup S_{i})$, which contains all columns that are neither big nor small.

We now formalise our observations by giving inequalities about the amount of probability that $\mathbf{y}$ can assign to $B_{i}$, $S_{i}$, and $O_{i}$, for every $q$-bad row $i$. The following proposition proves three inequalities. The first inequality is proved using Markov’s inequality. The second and third inequalities arise from substituting the first inequality into Definition 3 and Equation (5), respectively. The full proof of this proposition is presented in A.

We now define our improved strategies. Let ${\bar{\imath}}$ to be a worst bad row. That is ${\bar{\imath}}$ is a row that satisfies $\arg\max_{i}(R_{i}\cdot\mathbf{y})$, and therefore ${{\bar{\imath}}}$ is a $\bar{q}$-bad row such that there is no $q$-bad row with $q<\bar{q}$. We fix ${\bar{\imath}}$ and $\bar{q}$ to be these choices for the rest of this paper. Note that we can assume that $\bar{q}<3$, because if this is not the case, then all rows have payoff less than or equal to $\frac{2}{3}-z$, and $\mathbf{y}$ does not need to be improved.

We begin by defining a strategy that improve row ${\bar{\imath}}$. We will improve row ${{\bar{\imath}}}$ by moving the probability assigned to $B_{{\bar{\imath}}}$ to $S_{{\bar{\imath}}}$. Formally, we define the strategy $\mathbf{y}^{\text{imp}}$ as follows. For each $j$ with $1\leq j\leq n$, we have:

The strategy $\mathbf{y}^{\text{imp}}$ improves the specific bad row ${\bar{\imath}}$, but other rows may not improve, or even get worse in $\mathbf{y}^{\text{imp}}$. Therefore, we will study convex combinations of $\mathbf{y}$ and $\mathbf{y}^{\text{imp}}$. More formally, for the parameter $t\in$, we define the strategy $\mathbf{y}(t)$ to be $(1-t)\cdot\mathbf{y}+t\cdot\mathbf{y}^{\text{imp}}$.

Applying the matching pennies argument

So far, we have not used the assumption that Procedure 2 did not find a $(\frac{2}{3}-z)$-WSNE. In this section we will see how this assumption can be used to prove properties about the $q$-bad rows. We begin by defining the concept of a matching pennies sub-game.

Let $\mathbf{y}$ be a column player strategy, let $i$ and ${i^{\prime}}$ be two rows, and let $j$ and ${j^{\prime}}$ be two columns. If $j\in B_{i}\cap S_{{i^{\prime}}}$ and ${j^{\prime}}\in B_{{i^{\prime}}}\cap S_{i}$, then we say that $i$, ${i^{\prime}}$, $j$, and ${j^{\prime}}$ form a matching pennies sub-game in $\mathbf{y}$.

An example of a matching pennies sub-game is given by $l$, $r$, $T$, and $M$ in Figure 2, because we have $l\in B_{M}\cap S_{T}$, and we have $r\in B_{T}\cap S_{M}$. In this example, we can obtain an exact Nash equilibrium by making the row player mix uniformly between $T$ and $M$, and making the column player mix uniformly between $l$ and $r$. However, in general we can only expect to obtain an $(\frac{2}{3}-z)$-WSNE using this technique, as the following proposition shows.

Let $\mathbf{y}$ be a column player strategy. If there is a matching pennies sub-game in $\mathbf{y}$, then we can construct a $(\frac{2}{3}-z)$-WSNE with a $2\times 2$ support.

Let $i$, ${i^{\prime}}$, $j$, and ${j^{\prime}}$ be a matching pennies sub-game in $\mathbf{y}$. We define two strategies $\mathbf{x}^{\prime}$ and $\mathbf{y}^{\prime}$ as follows:

We will prove that $(\mathbf{x}^{\prime},\mathbf{y}^{\prime})$ is a $(\frac{2}{3}-z)$-WSNE. Note that when the column player plays $\mathbf{y}^{\prime}$, the payoff to the row player from row $i$ is:

Since $j\in B_{i}$ we have $R_{i,j}\geq\frac{2}{3}+2z$, Hence, we have:

An identical argument can be used to argue that $R_{{i^{\prime}}}\cdot\mathbf{y}^{\prime}$, ${C^{T}}_{j}\cdot\mathbf{x}^{\prime}$, and ${C^{T}}_{{j^{\prime}}}\cdot\mathbf{x}^{\prime}$ are all greater than or equal to $\frac{1}{3}+z$.

Thus, we have shown that all pure strategies in the support of $\mathbf{x}^{\prime}$ and $\mathbf{y}^{\prime}$ are $(\frac{2}{3}-z)$-best responses. Hence, $(\mathbf{x}^{\prime},\mathbf{y}^{\prime})$ is a $(\frac{2}{3}-z)$-WSNE.

Proposition 5 allows us to assume that the game does not contain a matching pennies sub-game, because otherwise Procedure 2 would have found a $(\frac{2}{3}-z)$-WSNE. Note that, by definition, if the game does not contain a matching pennies sub-game, then for all rows $i$ we must have either $B_{\bar{\imath}}\cap S_{i}=\emptyset$, or $B_{i}\cap S_{\bar{\imath}}=\emptyset$.

An Improved Strategy Exists

Our goal is to show that there exists a $t$ in the range $0\leq t\leq 1$ and a $z>0$ such that for every row $i$, we have $R_{i}\cdot\mathbf{y}(t)\leq\frac{2}{3}-z$. In this section, we develop a computer assisted proof of this fact.

Recall that the strategy $\mathbf{y}^{\text{imp}}$ is defined by moving all probability from the columns in $B_{{\bar{\imath}}}$ to the columns in $S_{{\bar{\imath}}}$. We are interested in how other rows $i$ are affected by this operation. This will depend on how much probability mass is shared between the partition $(B_{i},S_{i},O_{i})$, and the partition $(B_{{\bar{\imath}}},S_{{\bar{\imath}}},O_{{\bar{\imath}}})$. Figure 3 shows the nine possible intersections.

We are interested in the amount of probability that $\mathbf{y}$ assigns to each of these nine sets. We define a shorthand for this purpose:

As $t$ is increased away from , probability will be shifted from $\mathbf{bb}$, $\mathbf{bs}$, and $\mathbf{bo}$ to $\mathbf{sb}$, $\mathbf{ss}$, and $\mathbf{so}$, while the amount of probability assigned to $\mathbf{ob}$, $\mathbf{os}$, and $\mathbf{oo}$ will remain constant.

For each fixed $t$ in the range $0\leq t\leq 1$, and each fixed $z>0$, we are interested in the worst-case value of $R_{i}\cdot\mathbf{y}(t)$. We will show that an upper bound on $R_{i}\cdot\mathbf{y}(t)$ can be obtained by solving a linear program. The linear program has eleven variables. We use nine variables, $\mathbf{bb}$, $\mathbf{bs}$, $\mathbf{bo}$, $\mathbf{sb}$, $\mathbf{ss}$, $\mathbf{so}$, $\mathbf{ob}$, $\mathbf{os}$, and $\mathbf{oo}$, to represent the amount of probability assigned to the columns in $i$. We use two additional variables $\mathbf{q}$ and $\mathbf{\bar{q}}$ to represent how bad the rows ${\bar{\imath}}$ and $i$ are. These two variables should be interpreted as follows: row ${\bar{\imath}}$ is a $\mathbf{\bar{q}}$-bad row and row $i$ is a $\mathbf{q}$-bad row.

We can now define the linear program. We begin by defining a helper function $\phi(z,\bar{q})$ as follows:

Our linear program will be parameterised: for each $z$ with $z\geq 0$, each $t$ in the range $0\leq t\leq 1$, and each $k\in\{0,1\}$ we define $LP(z,t,k)$ to be the linear program shown in Figure 4. The rest of this section is dedicated to showing that this linear program can be used to find an upper bound on $R_{i}\cdot\mathbf{y}(t)$, for all rows $i$.

We begin by arguing that all of the constraints in the LP are valid. Firstly, since $z$ and $t$ are both constants, it can be seen that all of the constraints are indeed linear. Constraints (7) through (12) are taken directly from Proposition 4. Each inequality in Proposition 4 appears twice: once for the row $i$ and once for the row ${\bar{\imath}}$.

Constraint (13) encodes the matching pennies argument. By Proposition 5 if we have both $\mathbf{bs}>0$ and $\mathbf{sb}>0$, then we can find a $(\frac{2}{3}-z)$-WSNE. Thus, we can assume that either $\mathbf{sb}=0$ or $\mathbf{sb}=0$. Constraint (13) encodes this using the parameter $k$: if $k=0$ then $\mathbf{bs}$ is constrained to be , and if $k=1$, then $\mathbf{sb}$ is constrained to be .

Constraints (14) and (15) provide bounds for $\mathbf{q}$ and $\mathbf{\bar{q}}$. Recall that a row $i$ is $q$-bad if $R_{i}\cdot\mathbf{y}=\frac{2}{3}+2z-qz$. Since $\mathbf{\bar{q}}$ is the $q$-value for a worst bad row, and since a worst bad row ${\bar{\imath}}$ must have $R_{{\bar{\imath}}}\cdot\mathbf{y}\geq\frac{2}{3}-z$, we must have $\mathbf{\bar{q}}\leq 3$. This is encoded in Constraint (14). Constraint (15) again uses the fact that $\mathbf{\bar{q}}$ is the $q$-value of a worst bad row: the $q$ value for every other row must be greater than or equal to $\mathbf{\bar{q}}$.

Finally, Constraints (16) and (17) specify that the nine variables must be a probability distribution. They also specify that both $\mathbf{q}$ and $\mathbf{\bar{q}}$ must be non-negative, which is valid because Proposition 3 implies that no row $i$ can have $R_{i}\cdot\mathbf{y}>\frac{2}{3}+2z$.

The Objective

We now show that the objective function of the linear program provides an upper bound on $R_{i}\cdot\mathbf{y}(t)$. To prove this, we first observe that by definition we have

Since $i$ is a $\mathbf{q}$-bad row, we have that $R_{i}\cdot\mathbf{y}=\frac{2}{3}+2z-\mathbf{q}z$. In the following proposition, we show an upper bound for $R_{i}\cdot\mathbf{y}^{\text{imp}}$.

We have that $R_{i}\cdot\mathbf{y}^{\text{imp}}$ is less than or equal to:

Since $\mathbf{y}^{\text{imp}}$ is obtained from $\mathbf{y}$ by shifting all probability from $B_{{\bar{\imath}}}$ to $S_{{\bar{\imath}}}$, we have that:

The second and third equalities were obtained directly from the definition of $\mathbf{y}^{\text{imp}}$ given in (6).

Now to obtain the claimed result we split the two sums into their constituent parts. Firstly, we have that $\sum_{j\in S_{{\bar{\imath}}}}\mathbf{y}=\mathbf{sb}+\mathbf{ss}+\mathbf{so}$, and by definition we have that:

$R_{i,j}\leq\frac{1}{3}+z$ for each $j\in S_{i}$, and

$R_{i,j}\leq\frac{2}{3}+2z$ for each $j\in O_{i}$.

Similarly, we split the sum $\sum_{j\in O_{{\bar{\imath}}}}\mathbf{y}$ into $\mathbf{ob}+\mathbf{os}+\mathbf{oo}$, and apply the same bounds as above. Combining all of these bounds and substituting them into Equation (19) yields the claimed result.

Substituting our two bounds into Equation (18) does give an upper bound on $R_{i}\cdot\mathbf{y}(t)$, but this upper bound is not linear in the variables of the linear program. To resolve this, in the next proposition we provide a constant upper bound for one of the terms in the LP, using the auxiliary function $\phi(z,\bar{q})$ that was defined earlier.

If $z<\frac{13-3\sqrt{17}}{24}\approx 0.02627$, then

Proposition 4 implies that $\mathbf{sb}+\mathbf{ss}+\mathbf{so}\geq\frac{\frac{1}{3}-2z-\bar{q}z-(\frac{1}{3}+z)(\mathbf{ob}+\mathbf{os}+\mathbf{oo})}{\frac{2}{3}-z}$. We can apply this in order to determine the following upper bound for $\mathbf{bb}+\mathbf{bs}+\mathbf{bo}$.

Substituting this gives the following upper bound.

In order to proceed we must now use a lower bound for $(\frac{2}{3}-z)\cdot(\mathbf{sb}+\mathbf{ss}+\mathbf{so})$. By Proposition 4 we have that:

In order to substitute Inequality (21) into Inequality (20), we must have that $2z+\bar{q}z+(\frac{1}{3}+z)\cdot\frac{2\bar{q}z}{\frac{1}{3}-2z}<\frac{1}{3}$, because otherwise the denominator of Inequality (20) will be or negative. Since $\bar{q}$ can be at most $3$, this holds whenever:

Solving this inequality for $z$ gives that $z<\frac{13\pm 3\sqrt{17}}{24}$. Taking the smaller of the two solutions gives $z<\frac{13-3\sqrt{17}}{24}\approx 0.02627$.

So, if we have $z<\frac{13-3\sqrt{17}}{24}$, then we can conclude:

To complete the proof we observe that, so long as $0\leq z<\frac{13-3\sqrt{17}}{24}$, we have that $\phi(z,\bar{q})$ is monotonically increasing in $\bar{q}$. This holds because $\bar{q}$ only occurs positively in the numerator and negatively in the denominator, and because the denominator is strictly positive. Thus, since $\bar{q}$ can be at most $3$, we have $\phi(z,\bar{q})\leq\phi(z,3)$.

Combining the upper bound from Proposition 7 with the upper bound from Proposition 6, and substituting the result into Equation (18) gives a linear upper bound on $R_{i}\cdot\mathbf{y}(t)$, and this linear bound is used as the objective function of the LP.

The Upper Bound

We can now prove that the linear program provides an upper bound on the quality of WSNE provided by $\mathbf{y}(t)$. For each problem $LP(z,t,k)$, let $\operatorname{Sol}(LP(z,t,k))$ be the value of the objective function in the solution of $LP(z,t,k)$.

For every $z>0$ and $t$ in the range $0\leq t\leq 1$:

if $\sum_{j\in B_{{\bar{\imath}}}\cap S_{i}}\mathbf{y}=0$ then $R_{i}\cdot\mathbf{y}(t)\leq\operatorname{Sol}(LP(z,t,0))$.

if $\sum_{j\in S_{{\bar{\imath}}}\cap B_{i}}\mathbf{y}=0$ then $R_{i}\cdot\mathbf{y}(t)\leq\operatorname{Sol}(LP(z,t,1))$.

We will prove only the case where $\sum_{j\in B_{{\bar{\imath}}}\cap S_{i}}\mathbf{y}=0$, because the other case is entirely symmetric. Let $i$ be a row that maximizes $R_{i}\cdot\mathbf{y}(t)$, and let ${\bar{\imath}}$ be the worst bad row in $\mathbf{y}$. It is not difficult to construct a feasible point in $LP(z,t,0)$ that represents these two rows: the variables $\mathbf{bb},\mathbf{bs},\dots$ are set according to the probability assigned to the corresponding intersection sets by $\mathbf{y}$, while $\mathbf{q}$ and $\mathbf{\bar{q}}$ are set to be the $q$-values of $i$ and ${\bar{\imath}}$, respectively.

Obviously, this point satisfies $\mathbf{\bar{q}}\leq 3$ and $\mathbf{\bar{q}}\leq 3$, and it also satisfies the non-negativities and the sum-to-one constraint. Furthermore, by assumption we have that $\mathbf{bs}=0$, so Constraint (13) is satisfied. Since all other constraints of the LP were derived from the properties of either $\mathbf{q}$-bad or $\mathbf{\bar{q}}$-bad rows, we have that the point is feasible in $LP(z,t,0)$.

Since Propositions 6 and 7 show that the objective function of the LP provides an upper bound on $R_{i}\cdot\mathbf{y}(y)$, and since the LP is a maximization problem, we must have $R_{i}\cdot\mathbf{y}(t)\leq\operatorname{Sol}(LP(z,t,0))$.

Finding z𝑧z

We now describe how the linear programs can be used to determine a value of $z$ such that $\mathbf{y}(t)$ is a $(\frac{2}{3}-z)$-WSNE. For every $z>0$, if we want to prove that we can produce a $(\frac{2}{3}-z)$-WSNE, we require a witness $(z,t_{0},t_{1})$ that satisfies both of the following conditions:

A $t_{0}$ in the range $0\leq t_{0}\leq 1$ such that $\operatorname{Sol}(z,t_{0},0)\leq\frac{2}{3}-z$.

A $t_{1}$ in the range $0\leq t_{1}\leq 1$ such that $\operatorname{Sol}(z,t_{1},1)\leq\frac{2}{3}-z$.

If a pair $(t_{0},t_{1})$ can be found that satisfy these properties, then $\mathbf{y}(t_{0})$ is a $(\frac{2}{3}-z)$-WSNE in the case where $\mathbf{bs}=0$, and $\mathbf{y}(t_{1})$ is a $(\frac{2}{3}-z)$-WSNE in the case where $\mathbf{sb}=0$.

Our strategy for finding a witness $(z,t_{0},t_{1})$ was to perform a grid search over all possible values for $z$, $t_{0}$, and $t_{1}$ using a suitably small increment. We implemented this approach in Mathematica, where for each candidate witness, we solved the two linear programs in exact arithmetic. Ultimately, we were able to find a witness $(0.005913759,0.120,0.168)$. We were unable to find a witness for $z=0.005913760$. Thus, we have completed the proof of Theorem 4.1.

Conclusion

We have shown that our algorithm always finds a $(\frac{2}{3}-0.005913759)$-WSNE. Our computer assisted proof relied upon a linear program. We tried several ways to improve this analysis, all of which were ultimately unsuccessful.

The current proof finds two values of $t$: one for the case where $\mathbf{bb}=0$, and one for the case where $\mathbf{sb}=0$. One obvious approach towards improving the analysis is to split the analysis into more cases, and compute a $t$ for each case. One of our unsuccessful attempts in this direction was to parameterise the LP for different values of $\mathbf{\bar{q}}$. The existing LP allows $\mathbf{\bar{q}}$ to take any value in the range $$, but we could, for example, use one LP for the case where$\mathbf{\bar{q}}\in[0,1.5]$and another for the case where$\mathbf{\bar{q}}\in[1.5,3]$, and then compute two different values of$t$ for these two cases. Unfortunately, this did not yield a better analysis no matter how many different bands we used.

The objective function of the LP uses a linear upper bound on the non-linear expression from Proposition 6. We could, in principle, attempt to solve the non-linear optimization problem that is obtained when the expression from Proposition 6 is used directly as the objective function. Unfortunately, it seems that this task is beyond current technology. In particular, the need to solve the problem in exact arithmetic thwarted our attempts to solve the problem within a reasonable running time.

References

Appendix A Proof of Proposition 4

We begin by proving the inequality for $O_{i}$. The first thing that we note is that, if a column $j$ is in $O_{i}$, then $R_{i,j}+C_{i,j}$ must be significantly smaller than $\frac{4}{3}+z$.

For each row ${i}$, and each column ${j}\in O_{i}$, we have $R_{i,j}+C_{i,j}<1+3z$.

For each column $j\in O_{i}$ we have both of the following properties:

Since $j\notin B_{i}$, we have $R_{i,j}<\frac{2}{3}+2z$.

Since $j\notin S_{i}$, we have $C_{i,j}<\frac{2}{3}+2z$.

Furthermore, our assumption that Procedure (1) does not find a pure $(\frac{2}{3}-z)$-WSNE implies that:

If $R_{i,j}\geq\frac{1}{3}+z$, then $C_{i,j}<\frac{1}{3}+z$.

If $C_{i,j}\geq\frac{1}{3}+z$, then $R_{i,j}<\frac{1}{3}+z$.

This is because, if these inequalities did not hold for some pair $i$ and $j$, then it is easy to show that $(i,j)$ is a $(\frac{2}{3}-z)$-WSNE. From these properties it is easy to see that $R_{i,j}+C_{i,j}<\frac{2}{3}+2z+\frac{1}{3}+z=1+3z$.