Semidefinite Programming
and Nash Equilibria in Bimatrix Games

arXiv:1706.08550v2 [math.OC] 27 Feb 2018

Amir Ali Ahmadi and Jeffrey Zhang

∗

Abstract
We explore the power of semidefinite programming (SDP) for finding additive -approximate
Nash equilibria in bimatrix games. We introduce an SDP relaxation for a quadratic programming
formulation of the Nash equilibrium (NE) problem and provide a number of valid inequalities to
improve the quality of the relaxation. If a rank-1 solution to this SDP is found, then an exact
NE can be recovered. We show that for a strictly competitive game, our SDP is guaranteed to
return a rank-1 solution. Furthermore, we prove that if a rank-2 solution to our SDP is found,
5
-NE can be recovered for any game, or a 31 -NE for a symmetric game. We propose
then a 11
two algorithms based on iterative linearization of smooth nonconvex objective functions that are
designed so that their global minima coincide with rank-1 solutions. Empirically, we demonstrate
that these algorithms often recover solutions of rank at most two and  close to zero. We then
show how our SDP approach can address two (NP-hard) problems of economic interest: finding
the maximum welfare achievable under any NE, and testing whether there exists a NE where a
particular set of strategies is not played. Finally, we show the connection between our SDP and
the first level of the Lasserre/sum of squares hierarchy.

1

Introduction

A bimatrix game is a game between two players (referred to in this paper as players A and B)
defined by a pair of m × n payoff matrices A and B. Let 4m and 4n denote the m-dimensional
and n-dimensional simplices
m

4m = {x ∈ R | xi ≥ 0, ∀i,

m
X

n

xi = 1}, 4n = {y ∈ R | yi ≥ 0, ∀i,

i=1

n
X

yi = 1}.

i=1

These form the strategy spaces of player A and player B respectively. For a strategy pair (x, y) ∈
4m × 4n , the payoff received by player A (resp. player B) is xT Ay (resp. xT By). In particular,
if the players pick vertices i and j of their respective simplices (also called pure strategies), their
payoffs will be Ai,j and Bi,j . One of the prevailing solution concepts for bimatrix games is the
notion of Nash equilibrium. At such an equilibrium, the players are playing mutual best responses,
i.e., a payoff maximizing strategy against the opposing player’s strategy. In our notation, a Nash
equilibrium for the game (A, B) is a pair of strategies (x∗ , y ∗ ) ∈ 4m × 4n such that
x∗T Ay ∗ ≥ xT Ay ∗ , ∀x ∈ 4m ,
and
x∗T By ∗ ≥ x∗T By, ∀y ∈ 4n .1
∗
The authors are partially supported by the DARPA Young Faculty Award, the Young Investigator Award of the
AFOSR, the CAREER Award of the NSF, the Google Faculty Award, and the Sloan Fellowship.
1
In this paper we assume that all entries of A and B are between 0 and 1, and argue at the beginning of Section 2
why this is without loss of generality for the purpose of computing Nash equilibria.

1

Nash [29] proved that for any bimatrix game, such pairs of strategies exist (in fact his result more
generally applies to games with a finite number of players and a finite number of pure strategies).
While existence of these equilibria is guaranteed, finding them is believed to be a computationally
intractable problem. More precisely, a result of Daskalakis, Goldberg, and Papadimitriou [12]
implies that computing Nash equilibria is PPAD-complete (see [12] for a definition) even when the
number of players is 3. This result was later improved by Chen and Deng [9] who showed the same
hardness result for bimatrix games.
These results motivate the notion of an approximate Nash equilibrium, a solution concept in
which players receive payoffs “close” to their best response payoffs. More precisely, a pair of
strategies (x∗ , y ∗ ) ∈ 4m × 4n is an (additive) -Nash equilibrium for the game (A, B) if
x∗T Ay ∗ ≥ xT Ay ∗ − , ∀x ∈ 4m ,
and
x∗T By ∗ ≥ x∗T By − , ∀y ∈ 4n .
Note that when  = 0, (x∗ , y ∗ ) form an exact Nash equilibrium, and hence it is of interest to find
-Nash equilibria with  small. Unfortunately, approximation of Nash equilibria has also proved to
be computationally difficult. Cheng, Deng, and Teng have shown in [10] that, unless PPAD ⊆ P,
there cannot be a fully polynomial-time approximation scheme for computing Nash equilibria in
bimatrix games. There have, however, been a series of constant factor approximation algorithms
for this problem [14, 13, 20, 37], with the current best producing a .3393 approximation via an
algorithm by Tsaknakis and Spirakis [37].
We remark that there are exponential-time algorithms for computing Nash equilibria, such as
the Lemke-Howson algorithm [25, 34]. There are also certain subclasses of the problem which can
be solved in polynomial time, the most notable example being the case of zero-sum games (i.e.
when B = −A). This problem was shown to be solvable via linear programming by Dantzig [11],
and later shown to be polynomially equivalent to linear programming by Adler [2]. Aside from
computation of Nash equilibria, there are a number of related decision questions which are of
economic interest but unfortunately NP-hard. Examples include deciding whether a player’s payoff
exceeds a certain threshold in some Nash equilibrium, deciding whether a game has a unique Nash
equilibrium, or testing whether there exists a Nash equilibrium where a particular set of strategies
is not played [16].
Our focus in this paper is on understanding the power of semidefinite programming2 (SDP) for
finding approximate Nash equilibria in bimatrix games or providing certificates for related decision
questions. The goal is not to develop a competitive solver, but rather to analyze the algorithmic
power of SDP when applied to basic problems around computation of Nash equilibria. Semidefinite
programming relaxations have been analyzed in the past for an array of intractable problems
in computational mathematics (most notably in combinatorial optimization [17], [26] and systems
theory [8]), but to our knowledge not for computation of Nash equilibria in general bimatrix games.
SDPs have appeared however elsewhere in the literature on game theory for finding equilibria, e.g.
by Stein for exchangeable equilibria in symmetric games [36], by Parrilo, Laraki, and Lasserre
for Nash equilibria in zero-sum polynomial games [31, 21], or by Parrilo and Shah for zero-sum
stochastic games [35].

1.1

Organization and Contributions of the Paper

In Section 2, we formulate the problem of finding a Nash equilibrium in a bimatrix game as a
nonconvex quadratically constrained quadratic program and pose a natural SDP relaxation for it. In
Section 3, we show that our SDP is exact when the game is strictly competitive; see Definition 3.3).
2

The unfamiliar reader is referred to [38] for the theory of SDPs and a description of polynomial-time algorithms
for them based on interior point methods.

2

In Section 4, we establish a number of bounds on the quality of the approximate Nash equilibria
that can be read off of feasible solutions to our SDP. We show that if the SDP has a rank-k
solution with nonzero eigenvalues λ1 , . . . , λk , then one can recover from it an -Nash equilibrium
Pk
with  ≤ m+n
i=2 λi (Theorem 4.5). We then present an improved analysis in the rank-2 case
2
5
which shows how one can recover a 11
-Nash equilibrium from the SDP solution (Theorem 4.12). We
further prove that for symmetric games (i.e., when B = AT ), a 13 -Nash equilibrium can be recovered
in the rank-2 case (Theorem 4.16). We do not currently know of a polynomial-time algorithm to
find rank-2 solutions to our SDP. If such an algorithm were found, it would, together with our
analysis, improve the best known approximation bound for symmetric games. This motivates us to
design, in Section 5, two continuous but nonconvex objective functions for our SDP whose global
minima coincide with minimum-rank solutions. We prove an upper bound on  based on the value
of one of these objective functions (Theorem 5.6) and provide a heuristic for minimizing them both
that is based on iterative linearization. We show empirically that these approaches produce  very
close to zero (on average in the order of 10−3 ). In Section 6, we show how our SDP formulation
can be used to provide certificates for certain (NP-hard) questions of economic interest about Nash
equilibria. These are the problems of testing whether the maximum welfare achievable under any
Nash equilibrium exceeds some threshold, and whether a set of strategies is played in every Nash
equilibrium. In Section 7, we show that the SDP analyzed in this paper dominates the first level
of the Lasserre hierarchy (Proposition 7.1). Some directions for future research are discussed in
Section 8.

2

The Formulation of our SDP Relaxation

In this section we present an SDP relaxation for the problem of finding Nash equilibria in bimatrix games. This is done after a straightforward reformulation of the problem as a nonconvex
quadratically constrained quadratic program. Throughout the paper the following notation is used.
·
·
·
·
·
·
·
·
·
·
·
·
·
·

Ai, refers to the i-th row of a matrix A.
A,j refers to the j-th column of a matrix A.
ei refers to the elementary vector (0, . . . , 0, 1, 0, . . . , 0)T with the 1 being in position i.
4k refers to the k-dimensional simplex.
1m refers to the m-dimensional vector of one’s.
0m refers to the m-dimensional vector of zero’s.
Jm,n refers to the m × n matrix of one’s.
A  0 denotes that the matrix A is positive semidefinite (psd), i.e., has nonnegative eigenvalues.
A ≥ 0 denotes that the matrix A is nonnegative, i.e., has nonnegative entries.
A  B denotes that A − B  0.
Sk×k denotes the set of symmetric k × k matrices.
Tr(A) denotes the trace of a matrix A, i.e., the sum of its diagonal elements.
A ⊗ B denotes the Kronecker product of matrices A and B.
vec(M ) denotes the vectorized version of a matrix M , and diag(M ) denotes the vector containing its diagonal entries.

We also assume that all entries of the payoff matrices A and B are between 0 and 1. This
can be done without loss of generality because Nash equilibria are invariant under certain affine
transformations in the payoffs. In particular, the games (A, B) and (cA + dJm×n , eB + f Jm×n )

3

have the same Nash equilibria for any scalars c, d, e, and f , with c and e positive. This is because
x∗T Ay ≥ xT Ay
⇔ c(x∗T Ay ∗ ) + d ≥ c(xT Ay ∗ ) + d
⇔ c(x∗T Ay ∗ ) + d(x∗T Jm×n y ∗ ) ≥ c(xT Ay ∗ ) + d(xT Jm×n y ∗ )
⇔ x∗T (cA + dJm×n )y ∗ ≥ xT (cA + dJm×n )y
Identical reasoning applies for player B.

2.1

Nash Equilibria as Solutions to Quadratic Programs

Recall the definition of a Nash equilibrium from Section 1. An equivalent characterizaiton is that
a strategy pair (x∗ , y ∗ ) ∈ 4m × 4n is a Nash equilibrium for the game (A, B) if and only if
x∗T Ay ∗ ≥ eTi Ay ∗ , ∀i ∈ {1, . . . , m},
x∗T By ∗ ≥ x∗T Bei , ∀i ∈ {1, . . . , n}.

(1)

The equivalence can be seen by noting that because the payoff from playing any mixed strategy
is a convex combination of payoffs from playing pure strategies, there is always a pure strategy best
response to the other player’s strategy.
We now treat the Nash problem as the following quadratic programming (QP) feasibility problem:
min

x∈Rm ,y∈Rn

0

subject to xT Ay ≥ eTi Ay, ∀i ∈ {1, . . . , m},
xT By ≥ xT Bej , ∀j ∈ {1, . . . , n},
xi ≥ 0, ∀i ∈ {1, . . . , m},
yi ≥ 0, ∀j ∈ {1, . . . , n},
m
X
xi = 1,

(2)

i=1
n
X

yi = 1.

i=1

Similary, a pair of strategies x∗ ∈ 4m and y ∗ ∈ 4n form an -Nash equilibrium for the game
(A, B) if and only if
x∗T Ay ∗ ≥ eTi Ay ∗ − , ∀i ∈ {1, . . . , m},
x∗T By ∗ ≥ x∗T Bei − , ∀i ∈ {1, . . . , n}.
Observe that any pair of simplex vectors (x, y) is an -Nash equilibrium for the game (A, B) for
any  that satisfies
 ≥ max{max eTi Ay − xT Ay, max xT Bei − xT By}.
i

i

We use the following notation throughout the paper:
· A (x, y) := max eTi Ay − xT Ay,
i

· B (x, y) := max xT Bei − xT By,
i

· (x, y) := max{A (x, y), B (x, y)},
and the function parameters are later omitted if they are clear from the context.
4

2.2

SDP Relaxation

The QP formulation in (2) lends itself to a natural SDP relaxation. We define a matrix


X P
M :=
,
Z Y
and an augmented matrix

X P
0

:=
Z Y
M
x y


x
y ,
1

with X ∈ S m×m , Z ∈ Rn×m , Y ∈ S n×n , x ∈ Rm , y ∈ Rn and P = Z T .
The SDP relaxation can then be expressed as
min

M0 ∈Sm+n+1,m+n+1

subject to

0

(SDP1)

Tr(AZ) ≥ eTi Ay, ∀i ∈ {1, . . . , m},

(3)

Tr(BZ) ≥ xT Bej , ∀j ∈ {1, . . . , n},
m
X
xi = 1,

(4)
(5)

i=1
n
X

yi = 1,

(6)

i=1

M0ij ≥ 0 ∀i, j ∈ {1, . . . , m + n + 1},

(7)

M0m+n+1,m+n+1
0

(8)

= 1,

M  0.

(9)

We refer to the constraints (3) and (4) as the relaxed Nash constraints and the constraints (5)
and (6) as the unity constraints. This SDP is motivated by the following observation.
Proposition 2.1. Let M0 be any rank-1 feasible solution to SDP1. Then the vectors x and y from
its last column constitute a Nash equilibrium for the game (A, B).
Proof. We know that x and y are in the simplex from the constraints (5), (6), and (7).
If the matrix M0 is rank-1, then it takes the form
 T
    T
xx
xy T x
x
x
yxT yy T y  = y  y  .
1
1
xT
yT 1

(10)

Then, from the relaxed Nash constraints we have that
eTi Ay ≤ Tr(AZ) = Tr(AyxT ) = Tr(xT Ay) = xT Ay,
xT Aei ≤ Tr(BZ) = Tr(ByxT ) = Tr(xT By) = xT By.
The claim now follows from the characterization given in (1).
Remark 2.1. Because a Nash equilibrium always exists, there will always be a matrix of the form (10)
which is feasible to SDP1. Thus we can disregard any concerns about SDP1 being feasible, even
when we add valid inequalities to it in Section 2.3.
5

Remark 2.2. It is intuitive to note that the submatrix P = Z T of the matrix M0 corresponds to a
probability distribution over the strategies, and that seeking a rank-1 solution to our SDP can be
interpreted as making P a product distribution.
The following theorem shows that SDP1 is a weak relaxation and stresses the necessity of
additional valid constraints.
Theorem 2.2. Consider a bimatrix game with payoff matrices bounded in [0, 1]. Then
 for any
x
two vectors x ∈ 4m and y ∈ 4n , there exists a feasible solution M0 to SDP1 with y  as its last
1
column.
Proof. Consider any x, y, γ > 0, and the matrix
   T


x
x
γJ
0
m+n,m+n
m+n
y  y  +
.
0Tm+n
0
1
1
This matrix is the sum of two nonnegative psd matrices and is hence nonnegative and psd. By
assumption x and y are in the simplex, and so constraints (5) − (9) of SDP1 are satisfied. To check
that constraints (3) and (4) hold, note that since A and B are nonnegative, as long as the matrices
A and B are not the zero matrices, the quantities Tr(AZ) and Tr(BZ) will become arbitrarily
large as γ increases. Since eTi Ay and xT Bei are bounded by 1 by assumption, we will have that
constraints (3) and (4) hold for γ large enough. In the case where A or B is the zero matrix, the
Nash constraints are trivially satisfied for the respective player.

2.3

Valid Inequalities

In this subsection, we introduce a number of valid inequalities to improve upon the SDP relaxation
in SDP1. These inequalities are justified by being valid if the matrix returned by the SDP is
rank-1. The terminology we introduce here to refer to these constraints is used throughout the
paper. Constraints (11) and (12) will be referred to as the row inequalities, and (13) and (14) will
be referred to as the correlated equilibrium inequalities.
Proposition 2.3. Any rank-1 solution M0 to SDP1 must satisfy the following:
m
X

Xi,j =

j=1
n
X
j=1
n
X

n
X

Pi,j = xi , ∀i ∈ {1, . . . , m},

(11)

Zi,j = yi , ∀i ∈ {1, . . . , n}.

(12)

j=1

Yi,j =

m
X
j=1

Ai,j Pi,j ≥

n
X

j=1

j=1

m
X

m
X

j=1

Bj,i Pj,i ≥

Ak,j Pi,j , ∀i, k ∈ {1, . . . , m},

(13)

Bj,k Pj,i , ∀i, k ∈ {1, . . . , n}.

(14)

j=1

Proof. Recall from (10) that if M0 is rank-1, it is of the form
 T
    T
xx
xy T x
x
x
yxT yy T y  = y  y  .
1
1
xT
yT 1
6

To show (11), observe that
m
X

Xi,j =

j=1

m
X

xi xj = xi , ∀i ∈ {1, . . . , m}.

j=1

An identical argument works for the remaining matrices P, Z, and Y . To show (13) and (14),
observe that a pair (x, y) is a Nash equilibrium if and only if
∀i, xi > 0 ⇒ eTi Ay = xT Ay = max eTi Ay,
i

∀i, yi > 0 ⇒ xT Bei = xT By = max xT Bei .
i

This is because the Nash conditions require that xT Ay, a convex combination of eTi Ay, be at least
eTi Ay for all i. Indeed, if xi > 0 but eTi Ay < xT Ay, the convex combination must be less than
max xT Ay.
i

For each i such that xi = 0 or yi = 0, inequalities (13) and (14) reduce to 0 ≥ 0, so we only
need to consider strategies played with positive probability. Observe that if M0 is rank-1, then
n
X

Ai,j Pi,j = xi

j=1
m
X

n
X

Ai,j yj = xi eTi Ay ≥ xi eTk Ay =

j=1

Bj,i Pj,i = yi

j=1

m
X

n
X

Ak,j Pi,j , ∀i, k

j=1

Bj,i xj = yi xT Bei ≥ yi xT Bek =

j=1

m
X

Bj,i Pj,k , ∀i, k.

j=1

Remark 2.3. There are two ways to interpret the inequalities in (13) and (14): the first is as a
relaxation of the constraint xi (eTi Ay − eTj Ay) ≥ 0, ∀i, j, which must hold since any strategy played
with positive probability must give the best response payoff. The other interpretation is to have
the distribution over outcomes defined by P be a correlated equilibrium [4]. This can be imposed
by a set of linear constraints on the entries of P as explained next.
Suppose the players have access to a public randomization device which prescribes a pure
strategy to each of them (unknown to the other player). The distribution over the assignments can
be given by a matrix P , where Pi,j is the probability that strategy i is assigned to player A and
strategy j is assigned to player B. This distribution is a correlated equilibrium if both players have
no incentive to deviate from the strategy prescribed, that is, if the prescribed pure strategies a and
b satisfy
n
n
X
X
Ai,j P rob(b = j|a = i) ≥
Ak,j P rob(b = j|a = i),
j=1
m
X

j=1

Bi,j P rob(a = i|b = j) ≥

i=1

m
X

Bi,k P rob(a = i|b = j).

i=1

If we interpret the P submatrix in our SDP as the distribution over the assignments by the
P
public device, then because of our row constraints, P rob(b = j|a = i) = xi,j
whenever xi 6= 0
i
P

(otherwise the above inequalities are trivial). Similarly, P (a = i|b = j) = yi,j
for nonzero yj .
j
Observe now that the above two inequalities imply (13) and (14). Finally, note that every Nash
equilibrium generates a correlated equilibrium, since if P is a product distribution given by xy T ,
then P rob(b = j|a = i) = yj and P (a = i|b = j) = xi .
7

2.3.1

Implied Inequalities

In addition to those explicitly mentioned in the previous section, there are other natural valid
inequalities which are omitted because they are implied by the ones we have already proposed.
We give two examples of such inequalities in the next proposition. We refer to the constraints
in (15) below as the distribution constraints. The constraints in (16) are the familiar McCormick
inequalities [27] for box-constrained quadratic programming.
 
x
Proposition 2.4. Let z :=
. Any rank-1 solution M0 to SDP1 must satisfy the following:
y
m X
m
X

Xi,j =

i=1 j=1

n X
m
X

Zi,j =

i=1 j=1

n X
n
X

Yi,j = 1.

(15)

i=1 j=1

Mi,j ≤ zi , ∀i, j ∈ {1, . . . , m + n},
Mi,j + 1 ≥ zi + zj , ∀i, j ∈ {1, . . . , m + n}.

(16)

Proof. The distribution constraints follow immediately from the row constraints (11) and (12),
along with the unity constraints (5) and (6).
The first McCormick inequality is immediate as a consequence of (11) and (12), as all entries of
M are nonnegative. To see why the second inequality holds, consider whichever submatrix X, Y, P ,
or Z that contains Mi,j . Suppose that this submatrix is, e.g., P . Then, since P is nonnegative,
0≤

m
X

n
X

(11)

Pk,l =

k=1,k6=i l=1,l6=j

m
X

(12)

(xk − Pk,j ) = (1 − xi ) − (yj − Pi,j ) = Pi,j + 1 − xi − yj .

k=1,k6=i

The same argument holds for the other submatrices, and this concludes the proof.
2.3.2

The Effect of Valid Inequalities on an Example Game

Consider the following

0.42
0.54

A = 0.53
0.19
0.08

randomly-generated 5 × 5 bimatrix game:


0.46 0.03 0.77 0.33
0.63 0.19
0.03 0.71 0.06 0.56
0.66 0.92


0.43 0.17 0.85 0.30 , B = 0.99 0.29

0.94 0.55
0.56 0.59 0.38 0.37
0.64 0.61 0.40 0.35
0.35 0.92

0.09
0.26
0.43
0.58
0.90

0.22
0.97
0.43
0.78
0.53


0.33
0.43

0.72 .
0.92
0.89

Figure 1 demonstrates the shrinkage in the feasible set of our SDP, projected onto the first two
pure strategies of player A, as valid inequalities are added. Subfigure (a) depicts the Nash equilibria
and the feasible set of SDP1 (recall from 2.2 that the feasible region without valid inequalities is the
projection of the entire simplex). The row and distribution constraints are added for subfigure (b),
and the correlated equilibrium constraints are further added for subfigure (c). Subfigure (d) depicts
the true projection of the convex hull of Nash equilibria.

2.4

Strengthened SDP Relaxation

We now write out our new SDP with all constraints in
matrix

X P
0

M := Z Y
xT y T
8

one place. Recall the representation of the

x
y ,
1

Figure 1: Reduction in the size of our spectrahedral outer approximation to the convex hull of Nash
equilibria through the addition of valid inequalities.
with P = Z T . The improved SDP is now:
min

M0 ∈S (m+n+1)×(m+n+1)

subject to

0

(SDP2)

M0  0,

(17)

M0ij ≥ 0, i, j ∈ {1, . . . , m
M0m+n+1,m+n+1 = 1,
m
n
X
X
xi =

i=1

+ n + 1},

yi = 1,

(18)
(19)
(20)

i=1

Tr(AZ) − eTi Ay ≥ 0, ∀i ∈ {1, . . . , m},

(21)

Tr(BZ) − xT Bei ≥ 0, ∀i ∈ {1, . . . , n},
m
n
X
X
Xi,j =
Zj,i = xi , ∀i ∈ {1, . . . , m},

(22)

j=1

j=1

n
X

m
X

j=1
n
X

Yi,j =

Zi,j = yi , ∀i ∈ {1, . . . , n},

(23)

(24)

j=1

Ai,j Pi,j ≥

n
X

j=1

j=1

m
X

m
X

Bj,i Pj,i ≥

Ak,j Pi,j , ∀i, k ∈ {1, . . . , m},

(25)

Bj,k Pj,i , ∀i, k ∈ {1, . . . , n}.

(26)

j=1

j=1

Constraints (21) and (22) are the relaxed Nash constraints, constraints (23) and (24) are the
row constraints, and constraints (25) and (26) are the correlated equilibrium constraints.
9

3

Exactness for Strictly Competitive Games

In this section, we show that SDP1 recovers a Nash equilibrium for any zero-sum game, and that
SDP2 recovers a Nash equilibrium for any strictly competitive game (see Definition 3.3 below).
Both these notions represent games where the two players are in direct competition, but strictly
competitive games are more general and for example, allow both players to have nonnegative
payoff matrices. These classes of games are solvable in polynomial time via linear programming.
Nonetheless, it is reassuring to know that our SDPs recover these important special cases.
Definition 3.1. A zero-sum game is a game in which the payoff matrices satisfy A = −B.
Theorem 3.2. For a zero-sum game, the vectors x and y from the last column of any feasible
solution M0 to SDP1 constitute a Nash equilibrium.
Proof. Recall that the relaxed Nash constraints (3) and (4) read
Tr(AZ) ≥ eTi Ay, ∀i ∈ {1, . . . , m},
Tr(BZ) ≥ xT Bej , ∀j ∈ {1, . . . , n}.
Since B = −A, the latter statement is equivalent to
Tr(AZ) ≤ xT Aej , ∀j ∈ {1, . . . , n}.
In conjunction these imply
eTi Ay ≤ Tr(AZ) ≤ xT Aej , ∀i ∈ {1, . . . , m}, j ∈ {1, . . . , n}.

(27)

We claim that any pair x ∈ 4m and y ∈ 4n which satisfies the above condition is a Nash
equilibrium. To see that xT Ay ≥ eTi Ay, ∀i ∈ {1, . . . , m}, observe that xT Ay is a convex combination
of xT Aej , which are at least eTi Ay by (27). To see that xT By ≥ xT Bej ⇔ xT Ay ≤ xT Aej , ∀j ∈
{1, . . . , n}, observe that xT Ay is a convex combination of eTi Ay, which are at most xT Aej by (27).
Definition 3.3. A game (A, B) is strictly competitive if for all x, x0 ∈ 4m , y, y 0 ∈ 4n , xT Ay −
x0T Ay 0 and x0T By 0 − xT By have the same sign.
The interpretation of this definition is that if one player benefits from changing from one outcome
to another, the other player must suffer. Adler, Daskalakis, and Papadimitriou show in [3] that the
following much simpler characterization is equivalent.
Theorem 3.4 (Theorem 1 of [3]). A game is strictly competitive if and only if there exist scalars
c, d, e, and f, with c > 0, e > 0, such that cA + dJm×n = −eB + f Jm×n .
One can easily show that there exist strictly competitive games for which not all feasible solutions to SDP1 have Nash equilibria as their last columns (see Theorem 2.2). However, we show
that this is the case for SDP2.
Theorem 3.5. For a strictly competitive game, the vectors x and y from the last column of any
feasible solution M0 to SDP2 constitute a Nash equilibrium.
To prove Theorem 3.5 we need the following lemma, which shows that feasibility of a matrix
M0 in SDP2 is invariant under certain transformations of A and B.
Lemma 3.6. Let c, d, e, and f be any set of scalars with c > 0 and e > 0. If a matrix M0 is
feasible to SDP2 with input payoff matrices A and B, then it is also feasible to SDP2 with input
matrices cA + dJm×n and eB + f Jm×n .
10

Proof. It suffices to check that constraints (21),(22),(25), and (26) of SDP2 still hold, as only the
relaxed Nash and correlated equilibrium constraints use the matrices A and B. We only show
that constraints (21) and (25) still hold because the arguments for constraints (22) and (26) are
identical.
First recall that due to constraints (20) and (24) of SDP2, Tr(Jm×n Z) = 1. To check that the
relaxed Nash constraints hold, observe that for scalars c > 0 and d, and for all i ∈ {1, . . . , m},
Tr(AZ) − eTi Ay ≥ 0
⇔ cTr(AZ) + d − c(eTi Ay) − d ≥ 0
⇔ cTr(AZ) + d(Tr(Jm×n Z)) − c(eTi Ay) − d(Tr(Jm×n Z)) ≥ 0
⇔ Tr((cA + dJm×n )Z) − eTi (cA + dJm×n )y ≥ 0.
P
Now recall from constraint (23) of SDP2 (keeping in mind that P = Z T ) that nj=1 (Jm×n )i,j Pi,j =
xi . To check that the correlated equilibrium constraints hold, observe that for scalars c > 0, d, and
for all i, k ∈ {1, . . . , m},
n
X

Ai,j Pi,j ≥

j=1

⇔c

⇔c

n
X

n
X

Ai,j Pi,j + d

(Jm×n )i,j Pi,j ≥ c

j=1

⇔

n
X

Ak,j Pi,j

j=1
n
X

Ai,j Pi,j + dxi ≥ c

j=1
n
X

j=1

n
X

(cAi,j + dJm×n )k,j Pi,j ≥

j=1

j=1
n
X

j=1
n
X

Ak,j Pi,j + dxi
Ak,j Pi,j

n
X
+d
(Jm×n )k,j Pi,j
j=1

(cAi,j + dJm×n )k,j Pi,j .

j=1

Proof (of Theorem 3.5). Let A and B be the payoff matrices of the given strictly competitive game
and let M0 be a feasible solution to SDP2. Since the game is strictly competitive, we know that
cA + dJm×n = −eB + f Jm×n for some scalars c > 0, e > 0, d, f . Consider a new game with input
matrices Ã = cA + dJm×n and B̃ = eB − f Jm×n . By Lemma 3.6, M0 is still feasible to SDP2 with
input matrices Ã and B̃. Furthermore, since the constraints of SDP1 are a subset of the constraints
of SDP2, M0 is also feasible to SDP1. Now notice that since Ã = −B̃, Theorem 3.2 implies that
the vectors x and y in the last column form a Nash equilibrium to the game (Ã, B̃). Finally recall
from Section 2 that Nash equilibria are invariant to scaling and shifting of the payoff matrices, and
hence (x, y) is a Nash equilibrium to the game (A, B).
Remark 3.1. We later show in Proposition 5.1 that using the trace of M as the objective function
to SDP2 will guarantee that SDP2 returns a rank-1 solution.

4

Bounds on  for General Games

In this section, we provide upper bounds on the  returned by SDP2 for an arbitrary bimatrix
game. Since the problem of computing a Nash equilibrium in such a game is PPAD-complete, it is
unlikely that one can find rank-1 solutions to this SDP in polynomial time. In Section 5, we design
objective functions (such as variations of the nuclear norm) that empirically do very well in finding

11

low-rank solutions to SDP2. Nevertheless, it is of interest to know if the solution returned by SDP2
is not rank-1, whether one can recover an -Nash equilibrium from it and have a guarantee on .
Recall our notation for the matrices


X P
M :=
,
Z Y
and


X
M0 :=  Z
xT

P
Y
yT


x
y .
1

Throughout this section, any matrices X, Z, P = Z T and Y or vectors x and y are assumed to be
taken from a feasible solution to SDP2. The ultimate results of this section are Theorems 4.5, 4.12,
and 4.16. To work towards them, we need a number of preliminary lemmas which we present in
Section 4.1.

4.1

Lemmas Towards Bounds on 

We first observe the following connection between the approximate payoffs Tr(AZ) and Tr(BZ),
and (x, y), as defined in Section 2.1.
Lemma 4.1. Consider a feasible solution M0 to SDP2 and the vectors x and y and the matrix Z
from that solution. Then
(x, y) ≤ max{Tr(AZ) − xT Ay, Tr(BZ) − xT By}.
Proof. Note that since Tr(AZ) ≥ eTi Ay and Tr(BZ) ≥ xT Bei from constraints (21) and (22)
of SDP2, we have A ≤ Tr(AZ) − xT Ay and B ≤ Tr(BZ) − xT By.
We thus are interested in the difference of the two matrices P = Z T and xy T . These two
matrices can be interpreted as two different probability distributions over the strategy outcomes.
The matrix P is the probability distribution from the SDP which generates the approximate payoffs
Tr(AZ) and Tr(BZ), while xy T is the product distribution that would have resulted if the matrix
had been rank-1. We will see that the difference of these distributions is key in studying the 
which results from the SDP. Hence, we first take steps to represent this difference.
Lemma 4.2. Consider any feasible matrix M0 to SDP2, and its submatrix M. Let the matrix M
be given by an eigendecomposition
M=

k
X

λi vi viT

=:

i=1

k
X
i=1

   T
a
ai
,
λi i
bi bi

(28)

soPthat the eigenvectors
vi ∈ Rm+n are partitioned into ai ∈ Rm and bi ∈ Rn . Then for all
Pn
m
i, j=1 (ai )j = j=1 (bi )j .

12

Proof. We know from the distribution constraints from Section 2.3.1 that
k
X

(15)

λi 1Tm ai aTi 1m = 1,

i=1
k
X

(29)

(15)

λi 1Tm ai bTi 1n = 1,

(30)

i=1
k
X

(15)

λi 1Tn bi aTi 1m = 1,

i=1
k
X

(31)

(15)

λi 1Tn bi bTi 1n = 1.

(32)

i=1

Then by subtracting terms we have
(29) − (30) =

(31) − (32) =

k
X

λi 1Tm ai (aTi 1m − bTi 1n ) = 0,

i=1
k
X

λi 1Tn bi (aTi 1m − bTi 1n ) = 0.

(33)

(34)

i=1

By subtracting again these imply
(33) − (34) =

k
X

λi (1Tm ai − 1Tn bi )2 = 0.

(35)

i=1

As all λi are nonnegative due to positive semidefiniteness of M, the only way for this equality to
hold is to have 1Tm ai = 1Tn bi , ∀i. This is equivalent to the statement of the claim.
Pn
P
From Lemma 4.2, we can let si := m
j=1 (bi )j , and furthermore we assume without
j=1 (ai )j =
loss of generality that each si is nonnegative. Note that from the row constraint (11) we have
xi =

m
X
j=1

Xij =

k X
m
X

λl (al )i (al )j =

k
X

λj sj (al )i .

(36)

j=1

l=1 j=1

Hence,
x=

k
X

λi si ai .

(37)

λi si bi .

(38)

i=1

Similarly,
y=

k
X
i=1

Finally note from the distribution constraint (15) that this implies
k
X

λi s2i = 1.

i=1

13

(39)

Lemma 4.3. Let
M=

k
X
i=1

   T
a
ai
λi i
,
bi bi

be
a feasible solution
to SDP2, such that the eigenvectors of M are partitioned into ai and bi with
Pn
Pm
(b
)j = si , ∀i. Then
(a
)
=
i
i
j
j=1
j=1
T

P − xy =

k X
k
X

λi λj (sj ai − si aj )(sj bi − si bj )T .

i=1 j>i

Proof. Using equations (37) and (38) we can write
P − xy T =

k
X

λi ai bTi − (

i=1

=

k
X

k
X

k
X
λi si ai )(
λj sj bj )T

i=1

j=1

λi ai (bi − si

i=1
(39)

=

λj sj bj )T

j=1

k
X

k
X

λi ai (

i=1

=

k
X

λj s2j bi

− si

j=1

k X
k
X

k
X

λj sj bj )T

j=1

λi λj ai sj (sj bi − si bj )T

i=1 j=1

=

k X
k
X

λi λj (sj ai − si aj )(sj bi − si bj )T ,

i=1 j>i

where the last line follows from observing that terms where i and j are switched can be combined.
We can relate  and P − xy T with the following lemma.
Lemma 4.4. Consider any feasible solution M0 to SDP2 and the matrix P − xy T . Then
≤

kP − xy T k1
,
2

where k · k1 here denotes the entrywise L-1 norm, i.e., the sum of the absolute values of the entries
of the matrix.
Proof. Let D := P − xy T . From Lemma 4.1,
A ≤ Tr(AZ) − xT Ay = Tr(A(Z − yxT )).
If we then hold D fixed and restrict that A has entries bounded in [0,1], the quantity Tr(ADT ) is
maximized when
(
1 Di,j ≥ 0
Ai,j =
.
0 Di,j < 0
The resulting quantity Tr(ADT ) will then be the sum of all nonnegative elements of D. Since the
sum of all elements in D is zero, this quantity will be equal to 12 kDk1 .
The proof for B is identical, and the result follows from that  is the maximum of A and B .
14

4.2

Bounds on 

We provide a number of bounds on (x, y), where x and y are taken from the last column of a
feasible solution to SDP2. The first is a theorem stating that solutions which are “close” to rank-1
provide small .
Theorem 4.5. Let M0 be a feasible solution to SDP2. Suppose M is rank-k and its eigenvalues
are λ1 ≥ λ2 ≥ ... ≥ λk ≥ 0. Then, the x and y from the last column of M0 constitute an -NE to
Pk
the game (A, B) with  ≤ m+n
i=2 λi .
2
Proof. By the Perron Frobenius theorem (see e.g. [28, Chapter 8.3]), the eigenvector corresponding
to λ1 can be assumed to be nonnegative, and hence
s1 = ka1 k1 = kb1 k1 .
(40)
 
a
We further note that for all i, since i is a vector of length m + n with 2-norm equal to 1, we
bi
must have
 
√
ai
≤ m + n.
(41)
bi 1
Since si is the sum of the elements of ai and bi , we know that
√
m+n
si ≤ min{kai k1 , kbi k1 } ≤
.
2

(42)

This then gives us

m+n
,
(43)
4
with the first inequality following from (42) and the second from (41). Finally note that a consequence of the nonnegativity of k · k1 and (41) is that for all i, j,
s2i ≤ kai k1 kbi k1 ≤

kai k1 kbj k1 + kbi k1 kaj k1 ≤ (kai k1 + kbi k1 )(kaj k1 + kbj k1 ) =

 
ai
bi

1

Now we let D := P − xy T and upper bound 21 kDk1 using Lemma 4.3.
k

k

1
1 XX
kDk1 = k
λi λj (sj ai − si aj )(sj bi − si bj )T k1
2
2
i=1 j>i

≤

1
2

k X
k
X
i=1 j>i
k

≤

kλi λj (sj ai − si aj )(sj bi − si bj )T k1

k

1 XX
λi λj ksj ai − si aj k1 ksj bi − si bj k1
2
i=1 j>i
k

≤

k

1 XX
λi λj (sj kai k1 + si kaj k1 )(sj kbi k1 + si kbj k1 )
2
i=1 j>i

(40),(43)

≤

k

1X
λ1 s21 λj (sj + kaj k1 )(sj + kbj k1 )
2
j=2

15

 
aj
bj

(41)

≤ m + n.
1

(44)

k

k

1 XX
m+n
m+n
+
+ s2i
+ si sj kai k1 kbj k1 + si sj kaj k1 kbi k1 )
λi λj (s2j
2
4
4
i=2 j>i

k

(41),(44),(42)

X
m+n
λ1 s21
λi
2

≤

i=2

+

1
2

k X
k
X

λi λj

i=2 j>i

AMGM3

≤

m+n 2
(si + s2j ) + λi λj si sj (m + n)
4

k
k
k
X
s2i + s2j
s2i + s2j
m + n XX
m+n
λ1 s21
+
)
λi +
λi λj (
2
2
4
2
i=2

i=2 j>i

k

=

k

i=2

=

=

≤

i=2 j>i

k

k

k

k

k

i=2

i=2

j>i

i=2

j>i

X
X
X X
3(m + n) X
m+n
λ1 s21
λi +
(
λi s2i
λj +
λi
λj s2j )
2
8
k
k
k
k
k
X
X
X
X
3(m + n) X
m+n
λ1 s21
λi +
(
λj
λi s2i +
λi
λj s2j )
2
8
i=2

j=2

=

k

k

k

i=2

j=2

i=2

i=2

j>i

k

k

X
X
m+n
3(m + n)
λ1 s21
(1 − λ1 s21 )
λi +
λi
2
8
i=2

m+n
(3 + λ1 s21 )
8

(39)

≤

1<i<j

X
X
m+n
3(m + n) X
λ1 s21
λi +
(
λj s2j )
λi
2
8

(39)

=

k

X
m+n
3(m + n) X X
λ1 s21
λi +
λi λj (s2i + s2j )
2
8

i=2

k
X

λi

i=2

k

m+nX
λi .
2
i=2

4.3

Bounds on  in the Rank-2 Case

We now give a series of bounds on  which hold for feasible solutions to SDP2 that are rank-2 (note
that due to the row inequalities, M will have the same rank as M0 ). This is motivated by our
ability to show stronger (constant) bounds in this case, and the fact that we often recover rank-2
(or rank-1) solutions with our algorithms in Section 5. As it will be important in our study of this
particular case, we first recall the definition of a completely positive factorization/rank of a matrix.
Definition 4.6. A matrix M is completely positive (CP) if it admits a decomposition M = U U T
for some nonnegative matrix U .
Definition 4.7. The CP-rank of an n × n CP matrix M is the smallest k for which there exists a
nonnegative n × k matrix U such that M = U U T .
3

AMGM is used to denote the arithmetic-mean-geometric-mean inequality.

16

Theorem 4.8 (see e.g. [19] or Theorem 2.1 in [6]). A rank-2, nonnegative, and positive semidefinite
matrix is CP and has CP-rank 2.
It is also known (see e.g., Section 4 in [19]) that the CP factorization of a rank-2 CP matrix can
be found to arbitrary accuracy in polynomial time. With these preliminaries in mind, we present
lemmas which are similar to Lemmas 4.2 and 4.3, but provide a decomposition which is specific to
the rank-2 case.
Lemma 4.9. Suppose that a feasible solution M0 to SDP2 is rank-2. Then there exists a decompo   T
   T
c c
a a
, where σ1 and σ2 are nonnegative, σ1 + σ2 = 1, a, c ∈ 4m ,
+ σ2
sition M = σ1
d d
b b
and b, d ∈ 4n .
Proof. Since the matrix M is rank-2, nonnegative, and positive semidefinite, from Theorem 4.8 we
T
T
can decompose the matrix M into
 0  v1 v1 + 0v2 v2 where v1 and v2 are nonnegative. We can then
a
c
partition v1 and v2 into vectors 0 and 0 as we did in Lemma 4.2. Furthermore, we note that
b
d
because
hold, by repeating the proof of Lemma 4.2, we find
Pstill
Pm 0 (15)
Pn 0 constraints
Pmthe 0 distribution
n
that i=1 ai = i=1 bi , and i=1 ci = i=1 d0i . By letting
m
m
X
X
a0
b0
c0
d0
0 2
σ1 = (
ai ) , σ2 = (
c0i )2 , a = √ , b = √ , c = √ , d = √ ,
σ1
σ1
σ2
σ2
i=1

i=1

we have found constants σ1 and σ2 , and vectors a, b, c and d which satisfy
   T
   T
a a
c c
M = σ1
+ σ2
,
b b
d d
and a, b, c, and d are simplex vectors. Note that we can assume σ1 and σ2 are both positive, as
otherwise we are in the rank-1 case. Finally, to show that σ1 + σ2 = 1, recall that the sum of all
   T
   T
c c
a a
elements in M is 4, as are the sum of the elements of
and
.
b b
d d
Lemma 4.10. Suppose a feasible solution M0 to SDP2 is rank-2, and that
   T
   T
a a
c c
M = σ1
+ σ2
,
b b
d d
where σ1 and σ2 are nonnegative, σ1 + σ2 = 1, a, c ∈ 4m , and b, d ∈ 4n . Then,
P − xy T = σ1 σ2 (a − c)(b − d)T .
Proof. Recall that in our notation,
P = σ1 abT + σ2 cdT ,
x = σ1 a + σ2 c,
y = σ1 b + σ2 d.
Then,
P − xy T = σ1 abT + σ2 cdT − (σ1 a + σ2 c)(σ1 b + σ2 d)T
= σ1 abT + σ2 cdT − σ12 abT − σ1 σ2 adT − σ1 σ2 cbT − σ22 cdT
= σ1 (1 − σ1 )abT − σ1 σ2 adT − σ1 σ2 cbT + σ2 (1 − σ2 )cdT
= σ1 σ2 abT − σ1 σ2 adT − σ1 σ2 cbT + σ2 σ1 cdT
= σ1 σ2 (a − c)(b − d)T .

17

With this decomposition we can present a series of constant additive factor approximations for
the rank-2 case. To do so we apply Lemma 4.4 to the decomposition in Lemma 4.10. All the
following proofs will use the notation with σ, a, b, c, and d as in Lemma 4.10.
Theorem 4.11. If a feasible solution M0 to SDP2 is rank-2, then the x and y from the last column
of M0 constitute a 12 −Nash equilibrium.
Proof. We can use Lemma 4.10 to represent
D := P − xy T = σ1 σ2 (a − c)(b − d)T ,
where σ1 , σ2 ≥ 0, σ1 + σ2 = 1, a, c ∈ 4m , and b, d ∈ 4n . Then we can use Lemma 4.4 to get that
≤

kDk1
1
1
= kσ1 σ2 (a − c)(b − d)T k1 ≤ σ1 σ2 ka − ck1 kb − dk1 .
2
2
2

Since we have kak1 = kbk1 = kck1 = kdk1 = 1, we get the following bound for :
1
1
σ1 σ2 ka − ck1 kb − dk1 ≤ σ1 σ2 · 2 · 2 = 2σ1 σ2 .
2
2
Since σ1 and σ2 sum to one and are nonnegative, we know that σ1 σ2 ≤
 ≤ 12 .

1
4,

and hence we have

Theorem 4.12. If a feasible solution M0 to SDP2 is rank-2, then either the x and y from its last
5
5
column constitute a 11
-NE, or a 11
-NE can be recovered from M0 in polynomial time.
Proof. We consider 3 cases, depending on whether A (x, y) and B (x, y) are greater than or less
than .4. If A ≤ .4, B ≤ .4, then (x, y) is already a .4-Nash equilibrium. Now consider the case
when A ≥ .4, B ≥ .4. Since A ≤ Tr(A(P − xy T )T ) and B ≤ Tr(B(P − xy T )T ), we have
σ1 σ2 (a − c)T A(b − d) ≥ .4, σ1 σ2 (a − c)T B(b − d) ≥ .4.
Since A, a, b, c, and d are all nonnegative and σ1 σ2 ≤ 41 ,
aT Ab + cT Ad ≥ (a − c)T A(b − d) ≥ 1.6,
and the same inequalities hold for for player B. In particular, since A and B have entries bounded
in [0,1] and a, b, c, and d are simplex vectors, all the quantities aT Ab, cT Ad, aT Bb, and cT Bd are
at most 1, and consequently at least .6. Hence (a, b) and (c, d) are both .4-Nash equilibria.
Now suppose that (x, y) is a .4-NE for one player (without loss of generality player A) but not for
the other (without loss of generality player B). Then A ≤ .4, and B ≥ .4. Let y ∗ be a best response
for player B to x, and let p = 1+B1−A . Consider the strategy profile (x̃, ỹ) := (x, py + (1 − p)y ∗ ).
This can be interpreted as the outcome (x, y) occurring with probability p, and the outcome (x, y ∗ )
happening with probability 1 − p. In the first case, player A will have A (x, y) = A and player
B will have B (x, y) = B . In the second outcome, player A will have A (x, y ∗ ) at most 1, while
player B will have B (x, y ∗ ) = 0. Then under this strategy profile, both players have the same
upper bound for , which equals B p = 1+BB−A . To find the worst case for this value, let B = .5
5
(note from Theorem 4.11 that B ≤ 12 ) and A = .4, and this will return  = 11
.
We now show a stronger result in the case of symmetric games.
Definition 4.13. A symmetric game is a game in which the payoff matrices A and B satisfy
B = AT .
18

Definition 4.14. A Nash equilibrium strategy (x, y) is said to be symmetric if x = y.
Theorem 4.15 (see Theorem 2 in [29]). Every symmetric bimatrix game has a symmetric Nash
equilibrium.
For the proof of Theorem 4.16 below we modify SDP2 so that we are seeking a symmetric
solution.
Theorem 4.16. Suppose the constraints x = y and X = P = Y are added to SDP2. Then if a
feasible solution M0 to this new SDP is rank-2, either the x and y from its last column constitute
a symmetric 31 -NE, or a symmetric 13 -NE can be recovered from M0 in polynomial time.
Proof. If (x, y) is already a symmetric 13 -NE, then the claim is established. Now suppose that (x, y)
does not constitute a 13 -Nash equilibrium. Observe that since x = y, we must have a = b and c = d.
Then following the same reasoning as in the proof of Theorem 4.12, we have
1
σ1 σ2 (a − c)T A(a − c) ≥ .
3
1
Since A, a, and c are all nonnegative, and σ1 σ2 ≤ 4 , we get
4
aT Aa + cT Ac ≥ (a − c)T A(a − c) ≥ .
3
In particular, at least one of aT Aa and cT Ac is at least 32 . Since the maximum possible payoff is 1,
at least one of (a, a) and (c, c) is a (symmetric) 13 -Nash equilibrium.

5

Algorithms for Lowering the Rank

In this section, we present heuristics which aim to find low-rank solutions to SDP2 and present some
empirical results. Recall that our SDP2 in Section 2.4 did not have an objective function. Hence, we
can encourage low-rank solutions by choosing certain objective functions, for example the nuclear
norm (i.e. trace) of the matrix M, which is a general heuristic for rank minimization [33, 15]. This
simple objective function is already guaranteed to produce a rank-1 solution in the case of strictly
competitive games (see Proposition 5.1 below). For general games, however, one can design better
objective functions in an iterative fashion (see Section 5.1).
Proposition 5.1. For a strictly competitive game, any optimal solution to SDP2 with Tr(M) as
the objective function must be rank-1.
Proof. Let



X
X P
M :=
, M0 :=  Z
Z Y
xT

P
Y
yT


x
y ,
1

with P = Z T , be a feasible solution to SDP2. In the case of strictly competitive games, from
Theorem 3.5 we know that that (x, y) is a Nash equilibrium. Then because the matrix M0 must be
   T
x x
psd, by applying the Schur complement (see, e.g. [7, Sect. A.5.5]), we have that M 
,
y y
 T

xx
xy T
+ P for some psd matrix P and some Nash equilibrium (x, y).
and therefore M =
T
yx
yy T
Given this expression, the objective value is then xT x+y T y+Tr(P). As (x, y) is a Nash equilibrium,
the choice of P = 0 results in a feasible solution. Since the zero matrix has the minimum possible
   T
x x
trace among all psd matrices, the solution will be the rank-1 matrix
.
y y
19

5.1

Linearization Algorithms

The algorithms we present in this section are based on iterative linearization of certain nonconvex
objective functions. Motivated by the next proposition, we design two continuous (nonconvex)
objective functions that, if minimized exactly, would guarantee rank-1 solutions. We will then
linearize these functions iteratively.
Proposition 5.2. Let the matrices X and Y and vectors x and y be taken from a feasible solution
M0 to SDP2. Then the matrix M0 is rank-1 if and only if Xi,i = x2i and Yi,i = yi2 for all i.
 
x
Proof. Necessity of the condition is trivial; we argue sufficiency. Denote the vector z =
. First
y
recall from the row constraints of Section 2.3 that M will have the same rank as M0 , as the
last column
p is a linear combination of the columns of X and Y . Since M is psd, we have that
Mi,j ≤ Mi,i Mj,j , which implies Mi,j ≤ zi zj by the assumption of the proposition. Further
P
Pm+n
recall that a consequence of the unity constraint (20) is that m+n
zi zj = 4, and that we
i=1
Pm+nj=1
Pm+n
require from the distribution constraints from Section 2.3.1 that i=1
j=1 Mi,j = 4. Now we
can see that in order to have the equality
4=

m+n
X m+n
X

Mi,j ≤

i=1 j=1

m+n
X m+n
X

zi zj = 4,

i=1 j=1

we must have Mi,j = zi zj for each i and j. Consequently M is rank-1.
We focus now on two nonconvex objectives that as a consequence of the above proposition
would return rank-1 solutions:
Pm+n p
Proposition 5.3. All optimal solutions to SDP2 with the objective function
Mi,i or
i=1
T
T
Tr(M) − x x − y y are rank-1.
Proof. We show that each of these objectives has a specific lower bound which is achieved if and
only if the matrix is rank-1.
   T
p
p
x x
Observe that since M 
, we have Xi,i ≥ xi and Yi,i ≥ yi , and hence
y y
m+n
X

m
n
X
X
p
Mi,i ≥
xi +
yi = 2.

i=1

Further note that

i=1

i=1

 T    T    T  
x
x
x
x
x
x
Tr(M) −
≥
−
= 0.
y
y
y
y
y
y

We can see that the lower bounds are achieved if and only if Xi,i = x2i and Yi,i = yi2 for all i,
which by Proposition 5.2 happens if and only if M is rank-1.
We refer to our two objective functions in Proposition 5.3 as the “square root objective” and
the “diagonal gap objective” respectively. While these are both nonconvex, we will attempt to
iteratively minimize them by linearizing them through a first order Taylor expansion. For example,
at iteration k of the algorithm,
m+n
Xq

(k)

Mi,i '

i=1

m+n
Xq

(k−1)

Mi,i

i=1

1
(k)
(k−1)
+ q
(Mi,i − Mi,i ).
(k−1)
2 Mi,i
20

Note that for the purposes of minimization, this reduces to minimizing

Pm+n
i=1

(k)
q 1
Mi,i .
(k−1)
Mi,i

In similar fashion, for the second objective function, at iteration k we can make the approximation
 (k)T  (k)
 (k−1)T  (k−1)T
 (k−1)T  (k)  (k−1)
x
x
x
x
x
x
x
Tr(M) −
' Tr(M) −
−2
(
−
).
y
y
y
y
y
y
y
 (k−1)T  (k)
x
x
Once again, for the purposes of minimization this reduces to minimizing Tr(M)−2
.
y
y
This approach then leads to the following two algorithms.4
Algorithm 1 Square Root Minimization Algorithm
1:
2:
3:

Let x(0) = 1m , y (0) = 1n , k = 1.
while !convergence do
P
Pn
q 1
Solve SDP2 with m
X
+
i,i
i=1
i=1
(k−1)
xi

timal solution by M0∗ .
4:
Let x(k) = diag(X ∗ ), y (k) = diag(Y ∗ ).
5:
Let k = k + 1.
6: end while

q 1
Yi,i
(k−1)
yi

as the objective, and denote the op-

Algorithm 2 Diagonal Gap Minimization Algorithm
1:
2:
3:

4:
5:
6:

Let x(0) = 0m , y (0) = 0n , k = 1.
while !convergence do
 (k−1)T  (k)
x
x
Solve SDP2 with Tr(X)+Tr(Y )−2
as the objective, and denote the optimal
y
y
solution by M0∗ .
Let x(k) = x∗ , y (k) = y ∗ .
Let k = k + 1.
end while

Remark 5.1. Note that the first iteration of both algorithms uses the nuclear norm (i.e. trace) of
M as the objective.
The square root algorithm has the following property.
Theorem 5.4. Let M0(1) , M0(2) , . . . be the sequence of optimal matrices obtained from the square
root algorithm. Then the sequence
m+n
X q (k)
{
Mi,i }
(45)
i=1

is nonincreasing and is lower bounded by two. If it reaches two at some iteration t, then the matrix
M0(t) is rank-1.
Proof. Observe that for any k > 1,
m+n
Xq

(k)
Mi,i

i=1
4

(k)
(k−1)
q
q
m+n
m+n
m+n
X q (k−1)
Mi,i
1 X
1 X Mi,i
(k−1)
(k−1)
q
q
≤
(
+ Mi,i ) ≤
(
+ Mi,i ) =
Mi,i ,
(k−1)
(k−1)
2
2
Mi,i
Mi,i
i=1
i=1
i=1

An algorithm similar to Algorithm 2 is used in [18].

21

where the first inequality follows from the arithmetic-mean-geometric-mean inequality, and the
Pm+n M(k)
(k)
q i,i
and hence achieves a no
second follows from that Mi,i is chosen to minimize
i=1
(k−1)
Mi,i

M(k−1) .

larger value than the feasible solution
This shows that the sequence is nonincreasing.
The proof of Proposition 5.3 already shows that the sequence is lower bounded by two, and
Proposition 5.3 itself shows that reaching two is sufficient to have the matrix be rank-1.
The diagonal gap algorithm has the following property.
0

0

Theorem 5.5. Let M (1) , M (2) , . . . be the sequence of optimal matrices obtained from the diagonal
gap algorithm. Then the sequence
(k)

{Tr(M

 (k)T  (k)
x
x
)−
}
y
y

(46)

is nonincreasing and is lower bounded by zero. If it reaches zero at some iteration t, then the matrix
M0(t) is rank-1.
Proof. Observe that
Tr(M(k) ) −

 (k)T  (k)
 (k)T  (k)
 (k)  (k−1)  (k)  (k−1)
x
x
x
x
x
x
x
x
≤ Tr(M(k) ) −
+(
−
)T (
−
)
y
y
y
y
y
y
y
y
 (k)T  (k−1)  (k−1)T  (k−1)
x
x
x
x
(k)
= Tr(M ) − 2
+
y
y
y
y
 (k−1)T  (k−1)  (k−1)T  (k−1)
x
x
x
x
≤ Tr(M(k−1) ) − 2
+
y
y
y
y
 (k−1)T  (k−1)
x
x
= Tr(M(k−1) ) −
,
y
y

 (k−1)T  (k−1)
x
x
y
y
0(k−1)
and hence achieves a no larger value than the feasible solution M
. This shows that the sequence is nonincreasing.
The proof of Proposition 5.3 already shows that the sequence is lower bounded by zero, and
Proposition 5.3 itself shows that reaching zero is sufficient to have the matrix be rank-1.
0

where the second inequality follows from that M (k) is chosen to minimize Tr(M(k−1) )−2

Our last theorem further quantifies how making the objective of the diagonal gap algorithm
small makes  small. The proof is similar to the proof of Theorem 4.5.
Theorem 5.6. Let M0 be a feasible solution to SDP2. Then, the x and y from the last column of
M0 constitute an -NE to the game (A, B) with  ≤ 3(m+n)
(Tr(M0 ) − xT x − y T y).
8
Proof. Let k be the rank of M0 with the eigenvalues of M0given by λ1 , . . . , λk and the eigenvectors
P
Pn
a
v1 , . . . , vk partitioned as in Lemma 4.2 so that vi = i with m
j=1 (ai )j =
j=1 (bi )j = si , ∀i.
bi
P
Then we have Tr(M0 ) = ki=1 λi , and
xT x + y T y

(37),(38)

=

k
k
k
X
X
X
λi si vi )T (
λi si vi ) =
λ2i s2i .
(
i=1

i=1

22

i=1

We now get the following chain of inequalities (the first one follows from Lemma 4.4 and the proof
of Theorem 4.5):
k

k

1 XX
λi λj (sj kai k1 + si kaj k1 )(sj kbi k1 + si kbj k1 )
2

≤

i=1 j>i

(40),(43)

≤

k

k

m+n
1 XX
m+n
+ s2i
+ si sj kai k1 kbj k1 + si sj kaj k1 kbi k1 )
λi λj (s2j
2
4
4
i=1 j>i

(44)

≤

k

k

1 XX
m+n 2
(si + s2j ) + λi λj si sj (m + n)
λi λj
2
4
i=1 j>i

AM GM

≤

k
k
s2i + s2j
s2i + s2j
m + n XX
+
)
λi λj (
2
4
2
i=1 j>i

k

=

k

3(m + n) X X
λi λj (s2i + s2j )
8
i=1 j>i

=

=

k

k

k

k

i=1

j>i

i=1

j>i

X
X X
3(m + n) X
(
λi s2i
λj +
λi
λj s2j )
8
k
k
k
k
X
X
X
3(m + n) X
(
λj
λi s2i +
λi
λj s2j )
8
j=1

1<i<j

i=1

j>i

k

=

3(m + n) X X
(
λi
λj s2j )
8
i=1

(39)

=

k

3(m + n) X
(
λi (1 − λi s2i ))
8

3(m + n)
=
(
8

5.2

j6=i

i=1
k
X

k
X

i=1

i=1

λi −

λ2i s2i ) =

3(m + n)
(Tr(M0 ) − xT x − y T y).
8

Numerical Experiments

We tested Algorithms 1 and 2 on games coming from 100 randomly generated payoff matrices with
entries bounded in [0, 1] of varying sizes. Below is a table of statistics for 20 × 20 matrices; the
data for the rest of the sizes can be found in Appendix A.5 We can see that our algorithms return
approximate Nash equilibria with fairly low  (recall the definition from Section 2.1). We ran 20
iterations of each algorithm on each game. Using the SDP solver of MOSEK [1], each iteration
takes on average under 4 seconds to solve on a standard personal machine with a 3.4 GHz processor
and 16 GB of memory.
5

The code that produced these results is publicly available at aaa.princeton.edu/software. The function nash.m
computes an approximate Nash equilibrium using one of our two algorithms as specified by the user.

23

Table 1: Statistics on  for 20 × 20 games after 20 iterations.
Algorithm
Max
Mean Median StDev
Square Root 0.0198 0.0046 0.0039 0.0034
Diagonal Gap 0.0159 0.0032 0.0024 0.0032
The histograms below show the effect of increasing the number of iterations on lowering  on
20 × 20 games. For both algorithms, there was a clear improvement of the  by increasing the
number of iterations.

Figure 2: Distribution of  over numbers of iterations for the square root algorithm (left) and the
diagonal gap algorithm (right).

6

Bounding Payoffs and Strategy Exclusion

In addition to finding -additive Nash equilibria, our SDP approach can be used to answer certain
questions of economic interest about Nash equilibria without actually computing them. For instance, economists often would like to know the maximum welfare (sum of the two players’ payoffs)
achievable under any Nash equilibrium, or whether there exists a Nash equilibrium in which a given
subset of strategies (corresponding, e.g., to undesirable behavior) is not played. Both these questions are NP-hard for bimatrix games [16]. In this section, we show how our SDP can be applied
to these problems and given some numerical experiments.

6.1

Bounding Payoffs

When designing policies that are subject to game theoretic behavior by agents, economists would
often like to find one with a good socially optimal outcome, which usually corresponds to an
equilibrium giving the maximum welfare. Hence, given a game, it is of interest to know the highest
achievable welfare under any Nash equilibrium.
To address this problem, we begin as we did in Section 2.1 by posing the question of maximizing
the welfare under any Nash equilibrium as a quadratic program. Since the feasible set of this
program is the set of Nash equilibria, the constraints are the same as those in the formulation
in (2), though the objective function is now the welfare:

24

max
x,y

xT Ay + xT By

subject to xT Ay ≥ eTi Ay, ∀i ∈ {1, . . . , m},
xT By ≥ xT Bej , ∀j ∈ {1, . . . , n},
xi ≥ 0, ∀i ∈ {1, . . . , m},
yj ≥ 0, ∀j ∈ {1, . . . , n},
m
X
xi = 1,

(47)

i=1
n
X

yi = 1.

i=1

The SDP relaxation of this quadratic program will then be given by
max

M0 ∈Sm+n+1,m+n+1

subject to

Tr(AZ) + Tr(BZ)
(17) − (26).

(SDP3)
(48)

One can easily see that the optimal value of this SDP is an upper bound on the welfare achievable
under any Nash equilibrium. To test the quality of this upper bound, we tested this SDP on a
random sample of one hundred 5 × 5 and 10 × 10 games6 . The results are in Figures 3, which show
that the bound returned by SDP3 was exact in a large number of the experiments.

Figure 3: The quality of the upper bound on the maximum welfare obtained by SDP3 on 100 5 × 5
games (left) and 100 10 × 10 games (right).
6

The matrices were randomly generated with uniform and independent entries in [0,1]. The computation of the
upper bounds on the maximum payoffs was done with the function nashbound.m, which computes an SDP lower
bound on the problem of minimizing a quadratic function over the set of Nash equilibria of a bimatrix game. This
code is publicly available at aaa.princeton.edu/software. The exact computation of the maximum payoffs was done
with the lrsnash software [5], which computes extreme Nash equilibria. For a definition of extreme Nash equilibria
and for understanding why it is sufficient for us to compare against extreme Nash equilibria (both in Section 6.1 and
in Section 6.2), see Appendix B.

25

6.2

Strategy Exclusion

The strategy exclusion problem asks, given a subset of strategies S = (Sx , Sy ), with Sx ⊆ {1, . . . , m}
and Sy ⊆ {1, . . . , n}, is there a Nash equilibrium in which no strategy in S is played with positive
probability. We will call a set S “persistent” if the answer to this question is negative, i.e. at least
one strategy in S is played with positive probability in every Nash equilibrium. One application
of the strategy exclusion problem is to understand whether certain strategies can be discouraged
in the design of a game, such as reckless behavior in a game of chicken or defecting in a game of
prisoner’s dilemma. In these particular examples these strategy sets are persistent and cannot be
discouraged.
A quadratic program which can address the strategy exclusion problem is as follows:
X
X
min
xi +
yi
x∈4m ,y∈4n

subject to

i∈Sx

i∈Sy

T

x Ay ≥ eTi Ay, ∀i ∈ {1, . . . , m},

(49)

xT By ≥ xT Bej , ∀j ∈ {1, . . . , n}.
Observe that by design, S is persistent if and only if this quadratic program has a positive
optimal value. The SDP relaxation of this problem is given by
X

min

M0 ∈Sm+n+1,m+n+1

subject to

i∈S

xi +

X

yi

(SDP4)

i∈S

(17) − (26).

(50)

Our approach for the strategy exclusion problem would be to declare that a strategy set is
persistent if and only if SDP4 has positive optimal value.
Note that since the optimal value of SDP4 is a lower bound for that of (49), SDP4 carries over
the property that if a set S is not persistent, then the SDP for sure returns zero. Thus, when
using SDP4 on a set which is not persistent, our algorithm will always be correct. However, this is
not necessarily the case for a persistent set. While we can be certain that a set is persistent if SDP4
returns a positive optimal value (again, because the optimal value of SDP4 is a lower bound for
that of (49)), there is still the possibility that for a persistent set SDP4 will have optimal value
zero.
To test the performance of SDP4, we generated 100 random games of size 5 × 5 and 10 × 10 and
computed all their extreme Nash equilibria7 . We then, for every strategy set S of cardinality one
and two, checked whether that set of strategies was persistent, first by checking among the extreme
Nash equilibria, then through SDP4. The results are presented in Tables 2 and 3. As motivated by
the discussion above, we separately show the performance on all instances and the performances
on persistent input instances. As can be seen, SDP4 was quite effective for the strategy exclusion
problem. In particular, for 10 × 10 games, we have a perfect identification rate.

7

Connection to the Sum of Squares/Lasserre Hierarchy

In this section, we clarify the connection of the SDPs we have proposed in this paper to those
arising in the sum of squares/Lasserre hierarchy. We start by briefly reviewing this hierarchy.
7

The exact computation of the Nash equilibria was done again with the lrsnash software [5], which computes
extreme Nash equilibria. To understand why this suffices for our purposes see Appendix B.

26

|S|
Number of Total Sets
Number Correct
Percent Correct

Table 2: Performance of SDP4 on 5 × 5 games
1
2
|S|
1000
4500
Number of Persistent Sets
996
4465
Number Correct
99.6 % 99.2 %
Percent Correct

Table 3: Performance of SDP4 on 10 × 10 games
|S|
1
2
|S|
Number of Total Sets 2000
19000
Number of Persistent Sets
Number Correct
2000
19000
Number Correct
Percent Correct
100 % 100 %
Percent Correct

7.1

1
22
18
81.8%

1
11
11
100%

2
1478
1443
97.6%

2
841
841
100%

Sum of Squares/Lasserre Hierarchy

The sum of squares/Lasserre hierarchy8 gives a recipe for constructing a sequence of SDPs whose
optimal values converge to the optimal value of a given polynomial optimization problem. Recall
that a polynomial optimization problem (pop) is a problem of minimizing a polynomial over a basic
semialgebraic set, i.e., a problem of the form
min

f (x)

x∈Rn

(51)

subject to gi (x) ≥ 0, ∀i ∈ {1, . . . , m},
where f, gi are polynomial functions. In this section, when we refer to the k-th level of the Lasserre
hierarchy, we mean the optimization problem
k
γsos
:=max
γ,σi

γ

subject to f (x) − γ = σ0 (x) +

m
X

σi (x)gi (x),

(52)

i=1

σi is sos, ∀i ∈ {0, . . . , m},
σ0 , gi σi have degree at most 2k, ∀i ∈ {1, . . . , m}.
Here, the notation “sos” stands for sum of squares. We
P say that a polynomial p is a sum of squares
if there exist polynomials q1 , . . . , qr such that p = ri=1 qi2 . There are two primary properties of
the Lasserre hierarchy which are of interest. The first is that any fixed level of this hierarchy gives
an SDP of size polynomial in n. The second is that, if the set {x ∈ Rn |gi (x) ≥ 0} is Archimedean
k = p∗ , where p∗ is the optimal value of the pop in (51).
(see, e.g. [24] for definition), then lim γsos
k→∞

The latter statement is a consequence of Putinar’s positivstellensatz [32], [22].

7.2

The Lasserre Hierarchy and SDP1

One can show, e.g. via the arguments in [23], that the feasible sets of the SDPs dual to the SDPs
underlying the hierarchy we summarized above produce an arbitrarily tight outer approximation to
the convex hull of the set of Nash equilibria of any game. The downside of this approach, however,
is that the higher levels of the hierarchy can get expensive very quickly. This is why the approach
we took in this paper was instead to improve the first level of the hierarchy. The next proposition
formalizes this connection.
8

The unfamiliar reader is referred to [22, 30, 24] for an introduction to this hierarchy and the related theory of
moment relaxations.

27

Proposition 7.1. Consider the problem of minimizing any quadratic objective function over the
set of Nash equilibria of a bimatrix game. Then, SDP1 (and hence SDP2) gives a lower bound on
this problem which is no worse than that produced by the first level of the Lasserre hierarchy.
Proof. To prove this proposition we show that the first level of the Lasserre hierarchy is dual to a
weakened version of SDP1.
Explicit parametrization of first level of the Lasserre hierarchy. Consider the formulation of the Lasserre hierarchy in (52) with k = 1. Suppose we are minimizing a quadratic
function
 T  
x
x
f (x, y) = y  C y 
1
1
over the set of Nash equilibria as described by the linear and quadratic constraints in (2). If we
apply the first level of the Lasserre hierarchy to this particular pop, we get
max

Q,α,χ,β,ψ,η

γ

 T  
 T  
m
x
x
x
x
X
subject to y  C y  − γ = y  Q y  +
αi (xT Ay − eTi Ay)
1
1
1
1
i=1
n
X
+
βi (xT By − xT Bei )
i=1

+

m
X

χi x i +

i=1

n
X

(53)
ψi yi

i=1

m
n
X
X
+ η1 (
xi − 1) + η2 (
yi − 1),
i=1

i=1

Q  0,
α, χ, β, ψ ≥ 0,
where Q ∈ Sm+n+1×m+n+1 , α, χ ∈ Rm , β, ψ ∈ Rn , η ∈ R2 .
By matching coefficients of the two quadratic functions on the left and right hand sides of (53),
this SDP can be written as
max
γ
γ,α,β,χ,ψ,η

subject to H  0,
α, β, χ, ψ ≥ 0,

(54)

where
P
Pm
Pn


0
(− m
i=1 αi )A + (−
i=1 βi )B Pi=1 βi B,i − χ − η1 1m
Pn
1  Pm
m
T

(− i=1 αi )A + (− i=1 βi )B
0
H :=
i=1 αi Ai, − ψ − η2 1n +C.
Pn
Pm
2
T
T
T
T
T
β
B
−
χ
−
η
1
α
A
−
ψ
−
η
1
2η
+
2η
−
2γ
1
2
1 m
2 n
i=1 i ,i
i=1 i i,
(55)
Dual of a weakened version of SDP1. With this formulation in mind, let us consider a
weakened version of SDP1 with only the relaxed Nash constraints, unity constraints, and nonnegativity constraints on x and y in the last column (i.e., the nonegativity constraint is not applied to
the entire matrix). Let the objective be Tr(CM0 ). To write this new SDP in standard form, let

28




0
B −B,i
A
0
1
0
0 ,
0
−ATi,  , Bi :=  B T
2 −B T 0
0
−Ai,
0
,i




0 0 1m
0 0
0
1
1

0 0 0 , S2 :=
0 0 1n  .
S1 :=
2 1T 0 −2
2 0 1T −2
n
m


0
1 T
A
Ai :=
2
0

1
2

Let Ni be the matrix with all zeros except a
i = m + n + 1).
Then this SDP can be written as

at entry (i, m + n + 1) and (m + n + 1, i) (or a 1 if

min0

Tr(CM0 )

(SDP0)

subject to

M0  0,

(56)

M

0

(57)

0

(58)

0

(59)

0

(60)

0

(61)
(62)

Tr(Ni M ) ≥ 0, ∀i ∈ {1, . . . , m + n},
Tr(Ai M ) ≥ 0, ∀i ∈ {1, . . . , m},
Tr(Bi M ) ≥ 0, ∀i ∈ {1, . . . , n},
Tr(S1 M ) = 0,
Tr(S2 M ) = 0,
Tr(Nm+n+1 ) = 1.

We now create dual variables for each constraint; we choose αi and βi for the relaxed Nash
constraints (58) and (59), η1 and η2 for the unity constraints (60) and (61), χ for the nonnegativity
of x (57), ψ for the nonnegativity of y (57), and γ for the final constraint on the corner (62). These
variables are chosen to coincide with those used in the parametrization of the first level of the
Lasserre hierarchy, as can be seen more clearly below.
We then write the dual of the above SDP as
max

α,β,λ,γ

subject to

γ
m
X

αi Ai +

i=1

n
X
i=1

βi Bi +

2
X

ηi Si +

i=1

m
X

Ni+n χi +

i=1

n
X

Ni ψi + γNm+n+1  C,

i=1

α, β, χ, ψ ≥ 0.
which can be rewritten as
max

α,β,χ,ψ,γ

γ

subject to G  0,
α, β, χ, ψ ≥ 0,

(63)

where
P
Pm
Pn


0
(− m
i=1 αi )A + (−
i=1 βi )B Pi=1 βi B,i − χ − η1 1m
Pn
1  Pm
m
T

(− i=1 αi )A + (− i=1 βi )B
0
G :=
i=1 αi Ai, − ψ − η2 1n +C.
Pn
Pm
2
T
T
T
T
T
β
B
−
χ
−
η
1
α
A
−
ψ
−
η
1
2η
+
2η
−
2γ
1 m
2 n
1
2
i=1 i ,i
i=1 i i,
We can now see that the matrix G coincides with the matrix H in the SDP (54). Then we have
(53)opt = (54)opt = (63)opt ≤ SDP 0opt ≤ SDP 1opt ,
29

where the first inequality follows from weak duality, and the second follows from that the constraints
of SDP0 are a subset of the constraints of SDP1.
Remark 7.1. The Lasserre hierarchy can be viewed in each step as a pair of primal-dual SDPs:
the sum of squares formulation which we have just presented, and a moment formulation which is
dual to the sos formulation [22]. All our SDPs in this paper can be viewed more directly as an
improvement upon the moment formulation.
Remark 7.2. One can see, either by inspection or as an implication of the proof of Theorem 2.2,
that in the case where the objective function corresponds to maximizing player A’s and/or B’s
payoffs9 , SDPs (54) and (63) are infeasible. This means that for such problems the first level of
the Lasserre hierarchy gives an upper bound of +∞ on the maximum payoff. On the other hand,
the additional valid inequalities in SDP2 guarantee that the resulting bound is always finite.

8

Future Work

Our work leaves many avenues of further research. Are there other interesting subclasses of games
(besides strictly competitive games) for which our SDP is guaranteed to recover an exact Nash
equilibrium? Can the guarantees on  in Section 4 be improved in the rank-2 case (or the general
case), by improving our analysis or for example by using the correlated equilibrium constraints
(which we did not use)? Is there a polynomial time algorithm that is guaranteed to find a rank-2
solution to SDP2? Such an algorithm, together with our analysis, would improve the best known
approximation bound for symmetric games (see Theorem 4.16). Can SDPs in a higher level of the
Lasserre hierarchy be used to achieve better  guarantees? What are systematic ways of adding
valid inequalities to these higher-order SDPs by exploiting the structure of the Nash equilibrium
problem? For example, since any strategy played with positive probability must give the same
payoff, one can add a relaxed version of the cubic constraints
xi xj (eTi Ay − eTj Ay) = 0, ∀i, j ∈ {1, . . . , m}
to the SDP underlying the second level of the Lasserre hierarchy. What are other valid inequalities
for the second level? Finally, our algorithms were specifically designed for two-player one-shot
games. This leaves open the design and analysis of semidefinite relaxations for repeated games or
games with more than two players.

References
[1] MOSEK reference manual, 2013. Version 7. Latest version available at http://www.mosek.
com/.
[2] I. Adler. The equivalence of linear programs and zero-sum games. International Journal of
Game Theory, 42(1):165–177, 2013.
[3] I. Adler, C. Daskalakis, and C. H. Papadimitriou. A note on strictly competitive games. In
International Workshop on Internet and Network Economics, pages 471–474. Springer, 2009.
9

This would be the case, for example, in the maximum social welfare problem of Section 6.1, where the matrix of
the quadratic form in the objective function is given by


0
−A − B 0
0
0 .
C = −A − B
0
0
0

30

[4] R. J. Aumann. Subjectivity and correlation in randomized strategies. Journal of Mathematical
Economics, 1(1):67–96, 1974.
[5] D. Avis, G. D. Rosenberg, R. Savani, and B. Von Stengel. Enumeration of Nash equilibria for
two-player games. Economic Theory, 42(1):9–37, 2010.
[6] A. Berman and N. Shaked-Monderer. Completely positive matrices. World Scientific, 2003.
[7] S. Boyd and L. Vandenberghe. Convex optimization. Cambridge university press, 2004.
[8] S. P. Boyd, L. El Ghaoui, E. Feron, and V. Balakrishnan. Linear matrix inequalities in system
and control theory, volume 15. SIAM, 1994.
[9] X. Chen and X. Deng. Settling the complexity of two-player Nash equilibrium. In FOCS,
volume 6, page 47th, 2006.
[10] X. Chen, X. Deng, and S.-H. Teng. Computing Nash equilibria: Approximation and smoothed
complexity. In 2006 47th Annual IEEE Symposium on Foundations of Computer Science
(FOCS’06), pages 603–612. IEEE, 2006.
[11] G. B. Dantzig. A proof of the equivalence of the programming problem and the game problem.
Activity analysis of production and allocation, 13:330–338, 1951.
[12] C. Daskalakis, P. W. Goldberg, and C. H. Papadimitriou. The complexity of computing a
Nash equilibrium. SIAM Journal on Computing, 39(1):195–259, 2009.
[13] C. Daskalakis, A. Mehta, and C. Papadimitriou. A note on approximate Nash equilibria. In
International Workshop on Internet and Network Economics, pages 297–306. Springer, 2006.
[14] C. Daskalakis, A. Mehta, and C. Papadimitriou. Progress in approximate Nash equilibria. In
Proceedings of the 8th ACM conference on Electronic commerce, pages 355–358. ACM, 2007.
[15] M. Fazel. Matrix rank minimization with applications. PhD thesis, PhD thesis, Stanford
University, 2002.
[16] I. Gilboa and E. Zemel. Nash and correlated equilibria: Some complexity considerations.
Games and Economic Behavior, 1(1):80–93, 1989.
[17] M. X. Goemans and D. P. Williamson. Improved approximation algorithms for maximum cut
and satisfiability problems using semidefinite programming. Journal of the ACM (JACM),
42(6):1115–1145, 1995.
[18] S. Ibaraki and M. Tomizuka. Rank minimization approach for solving BMI problems with
random search. In American Control Conference, 2001. Proceedings of the 2001, volume 3,
pages 1870–1875. IEEE, 2001.
[19] V. Kalofolias and E. Gallopoulos. Computing symmetric nonnegative rank factorizations.
Linear Algebra and its Applications, 436(2):421–435, 2012.
[20] S. C. Kontogiannis, P. N. Panagopoulou, and P. G. Spirakis. Polynomial algorithms for approximating Nash equilibria of bimatrix games. In International Workshop on Internet and
Network Economics, pages 286–296. Springer, 2006.
[21] R. Laraki and J. B. Lasserre. Semidefinite programming for min–max problems and games.
Mathematical Programming, 131(1-2):305–332, 2012.

31

[22] J. B. Lasserre. Global optimization with polynomials and the problem of moments. SIAM
Journal on Optimization, 11(3):796–817, 2001.
[23] J. B. Lasserre. Convex sets with semidefinite representation. Mathematical programming,
120(2):457–477, 2009.
[24] M. Laurent. Sums of squares, moment matrices and optimization over polynomials. In Emerging Applications of Algebraic Geometry, pages 157–270. Springer, 2009.
[25] C. E. Lemke and J. T. Howson, Jr. Equilibrium points of bimatrix games. Journal of the
Society for Industrial and Applied Mathematics, 12(2):413–423, 1964.
[26] L. Lovász. On the shannon capacity of a graph. IEEE Transactions on Information theory,
25(1):1–7, 1979.
[27] G. P. McCormick. Computability of global solutions to factorable nonconvex programs: Part
I : Convex underestimating problems. Mathematical Programming, 10(1):147–175, 1976.
[28] C. D. Meyer. Matrix analysis and applied linear algebra, volume 2. SIAM, 2000.
[29] J. Nash. Non-cooperative games. Annals of mathematics, pages 286–295, 1951.
[30] P. A. Parrilo. Semidefinite programming relaxations for semialgebraic problems. Mathematical
Programming, 96(2):293–320, 2003.
[31] P. A. Parrilo. Polynomial games and sum of squares optimization. In Proceedings of the 45th
IEEE Conference on Decision and Control, pages 2855–2860. IEEE, 2006.
[32] M. Putinar. Positive polynomials on compact semi-algebraic sets. Indiana University Mathematics Journal, 42(3):969–984, 1993.
[33] B. Recht, M. Fazel, and P. A. Parrilo. Guaranteed minimum-rank solutions of linear matrix
equations via nuclear norm minimization. SIAM Review, 52(3):471–501, 2010.
[34] R. Savani and B. Stengel. Hard-to-solve bimatrix games. Econometrica, 74(2):397–429, 2006.
[35] P. Shah and P. A. Parrilo. Polynomial stochastic games via sum of squares optimization. In
Decision and Control, 2007 46th IEEE Conference on, pages 745–750. IEEE, 2007.
[36] N. D. Stein. Exchangeable equilibria. PhD thesis, Massachusetts Institute of Technology, 2011.
[37] H. Tsaknakis and P. G. Spirakis. An optimization approach for approximate Nash equilibria.
In International Workshop on Web and Internet Economics, pages 42–56. Springer, 2007.
[38] L. Vandenberghe and S. Boyd. Semidefinite programming. SIAM Review, 38(1):49–95, 1996.

A

Statistics on  from Algorithms in Section 5

Below are statistics for the  recovered in 100 random games of varying sizes using the algorithms
of Section 5.
Table 4: Statistics on  for 5 × 5 games after 20 iterations.
Algorithm
Max
Mean Median StDev
Square Root 0.0702 0.0040 0.0004 0.0099
Diagonal Gap 0.0448 0.0027
0
0.0061
32

Table 5: Statistics on  for 10 × 5 games after 20 iterations.
Algorithm
Max
Mean Median StDev
Square Root 0.0327 0.0044 0.0021 0.0064
Diagonal Gap 0.0267 0.0033 0.0006 0.0053

B

Table 6: Statistics on  for 10 × 10 games after
Algorithm
Max
Mean Median
Square Root 0.0373 0.0058 0.0039
Diagonal Gap 0.0266 0.0043 0.0026

20 iterations.
StDev
0.0065
0.0051

Table 7: Statistics on  for 15 × 10 games after
Algorithm
Max
Mean Median
Square Root 0.0206 0.0050 0.0034
Diagonal Gap 0.0212 0.0038 0.0025

20 iterations.
StDev
0.0045
0.0039

Table 8: Statistics on  for 15 × 15 games after
Algorithm
Max
Mean Median
Square Root 0.0169 0.0051 0.0042
Diagonal Gap 0.0159 0.0038 0.0029

20 iterations.
StDev
0.0039
0.0034

Table 9: Statistics on  for 20 × 15 games after
Algorithm
Max
Mean Median
Square Root 0.0152 0.0046 0.0035
Diagonal Gap 0.0119 0.0032 0.0022

20 iterations.
StDev
0.0036
0.0027

Table 10: Statistics on  for 20 × 20 games after
Algorithm
Max
Mean Median
Square Root 0.0198 0.0046 0.0039
Diagonal Gap 0.0159 0.0032 0.0024

20 iterations.
StDev
0.0034
0.0032

Lemmas for Extreme Nash Equilibria

The results reported in Section 6 were found using the lrsnash [5] software which computes extreme
Nash equilibria (see definition below). In particular the true maximum welfare and the persistent
strategy sets were found in relation to extreme Nash equilibria only. We show in this appendix why
this is sufficient for the claims we made about all Nash equilibria.
Definition B.1. An extreme Nash equilibrium is a Nash equilibrium which cannot be expressed
as a convex combination of other Nash equilibria.
Lemma B.2. All Nash equilibria are convex combinations of extreme Nash equilibria.

33

Proof. It suffices to show that any extreme point of the convex hull of the set of Nash equilibria
must be an extreme Nash equilibrium, as any point in a convex set can be written as a convex
combination of its extreme points. Suppose for the purpose of contradiction that this was not the
case, i.e. there is a point x which is an extreme point of the convex hull of Nash equilibria but is not
an extreme Nash equilibrium. Then either it is not a Nash equilibrium, or it is a Nash equilibrium
which is not extreme. In both cases, x can be written as a convex combination of other Nash
equilibria, and so cannot be an extreme point for the convex hull. For the former case it is because
its membership in the convex hull must be due to an expression of it as a convex combination of
Nash equilibria, and in the latter it is due to the definition of extreme Nash equilibria.
The next lemma shows that checking extreme Nash equilibria are sufficient for the maximum
welfare problem.
Lemma B.3. For any bimatrix game, there exists an extreme Nash equilibrium giving the maximum
welfare among all Nash equilibria.
 
 i
Pr
x̃
x
Proof. Consider any Nash equilibrium (x̃, ỹ), and let it be written as
= i=1 λi i for some
ỹ
y
 1
 r
x
x
set of extreme Nash equilibria 1 , . . . , r and λ ∈ 4r . Observe that for any i, j,
y
y
xiT Ay j ≤ xjT Ay j , xiT By j ≤ xiT By i ,

(64)

from the definition of a Nash equilibrium. Now note that
r
r
X
X
x̃T (A + B)ỹ = (
λi xi )T (A + B)(
λi y i )

=

i=1
r X
r
X

i=1

λi λj xiT (A + B)y j

i=1 j=1

=

r X
r
X

=
=

j

λi λj x Ay +

i=1 j=1
r X
r
(64) X

≤

iT

r X
r
X

λi λj xiT By j

i=1 j=1
r X
r
X

λi λj xjT Ay j +

λi λj xiT By i

i=1 j=1
i=1 j=1
r
r
X
X
λi xiT Ay i +
λi xiT By i
i=1
i=1
r
X
λi xiT (A + B)y i .
i=1

In particular, since each (xi , y i ) is an extreme Nash equilibrium, this tells us for any Nash
equilibrium (x̃, ỹ) there must be an extreme Nash equilibrium which has at least as much welfare.
Similarly for the results for persistent sets in Section 6.2, there is no loss in restricting attention
to extreme Nash equilibria.
Lemma B.4. For a given strategy set S, if every extreme Nash equilibrium plays at least one
strategy in S with positive probability, then every Nash equilibrium plays at least one strategy in S
with positive probability.
34

Proof. Let S be a persistent set of strategies. Since all Nash equilibria are composed of nonnegative
entries, and every extreme Nash equilibrium has positive probability on some entry in S, any convex
combination of extreme Nash equilibria must have positive probability on some entry in S.

Acknowledgments.
We would like to thank Ilan Adler, Costis Daskalakis, Georgina Hall, Ramon van Handel, and
Robert Vanderbei for insightful exchanges.

35

