Authors Maria-Florina Balcan, Mark Braverman,
License CC-BY-3.0
T HEORY OF C OMPUTING, Volume 13 (13), 2017, pp. 1–31
www.theoryofcomputing.org
Nash Equilibria in
Perturbation-Stable Games
Maria-Florina Balcan∗ Mark Braverman†
Received November 23, 2012; Revised August 30, 2017; Published November 13, 2017
Abstract: Motivated by the fact that in many game-theoretic settings, the game analyzed is
only an approximation to the game being played, in this work we analyze equilibrium com-
putation for the broad and natural class of bimatrix games that are stable under perturbations.
We specifically focus on games with the property that small changes in the payoff matrices
do not cause the Nash equilibria of the game to fluctuate wildly. For such games we show
how one can compute approximate Nash equilibria more efficiently than the general result of
Lipton et al. (EC’03), by an amount that depends on the degree of stability of the game and
that reduces to their bound in the worst case. Additionally, we show that for stable games,
the approximate equilibria found will be close in variation distance to true equilibria, and
moreover this holds even if we are given as input only a perturbation of the actual underlying
stable game.
For uniformly stable games, where the equilibria fluctuate at most quasi-linearly in
the extent of the perturbation, we get a particularly dramatic improvement. Here, we
∗ Supported in part by NSF grants CCF-0953192 and CCF-1101283, ONR grant N00014-09-1-0751, AFOSR grant FA9550-
09-1-0538, a Google Research Award, and a Microsoft Faculty Fellowship. This work was done in part while the author was
visiting Microsoft Research NE.
† This work was done in part while the author was a member of Microsoft Research NE. Research supported in part by NSF
Awards, DMS-1128155, CCF-1525342, and CCF-1149888, a Packard Fellowship in Science and Engineering, and the Simons
Collaboration on Algorithms and Geometry.
ACM Classification: F.1.3, F.2.1, J.4
AMS Classification: 68Q17, 68W25, 91A05, 91A10
Key words and phrases: algorithmic game theory, approximation algorithms, Nash equilibrium, beyond
worst-case analysis, perturbation stability
© 2017 Maria-Florina Balcan and Mark Braverman
c b Licensed under a Creative Commons Attribution License (CC-BY) DOI: 10.4086/toc.2017.v013a013
M ARIA -F LORINA BALCAN AND M ARK B RAVERMAN
achieve a fully quasi-polynomial-time approximation scheme, that is, we can find 1/poly(n)-
approximate equilibria in quasi-polynomial time. This is in marked contrast to the general
class of bimatrix games for which finding such approximate equilibria is PPAD-hard. In
particular, under the (widely believed) assumption that PPAD is not contained in quasi-
polynomial time, our results imply that such uniformly stable games are inherently easier for
computation of approximate equilibria than general bimatrix games.
1 Introduction
The Nash equilibrium solution concept has a long history in economics and game theory as a description
for the natural result of self-interested behavior [31, 35]. Its importance has led to significant effort
in the computer science literature in recent years towards understanding their computational structure,
and in particular on the complexity of finding both Nash and approximate Nash equilibria. A series of
results culminating in the work by Daskalakis, Goldberg, and Papadimitriou [18] and Chen, Deng, and
Teng [15, 16] showed that finding a Nash equilibrium or even a 1/poly(n)-approximate equilibrium, is
PPAD-complete even for 2-player bimatrix games. For general values of ε, the best known algorithm
2
for finding ε-approximate equilibria runs in time nO((log n)/ε ) , based on a structural result of Lipton et
al. [28] showing that there always exist ε-approximate equilibria with support over at most O((log n)/ε 2 )
strategies. This structural result has been shown to be existentially tight [23]. Even for large values
of ε, despite considerable effort [20, 19, 33, 23, 14, 26], polynomial-time algorithms for computing
ε-approximate equilibria are known only for ε ≥ 0.3393 [33]. Recently, Rubinstein [32] showed √ that
unless surprisingly fast algorithms exist for PPAD-complete problems (running in time 2 Õ( n) ), no
general poly-time algorithm for computing ε-approximate equilibria, for a sufficiently small constant
ε, exists. These results suggest a difficult computational landscape for equilibrium and approximate
equilibrium computation on worst-case instances.
In this paper we go beyond worst-case analysis and investigate the equilibrium computation problem
in a natural class of bimatrix games that are stable under perturbations. As we argue, on one hand,
such games can be used to model many realistic situations. On the other hand, we show that they have
additional structure which can be exploited to provide better algorithmic guarantees than believed to
be possible on worst-case instances. The starting point of our work is the realization that games are
typically only abstractions of reality and except in the most controlled settings, payoffs listed in a game
that represents an interaction between self-interested agents are only approximations to the agents’ exact
utilities.1 As a result, for problems such as equilibrium computation, it is natural to focus attention on
games that are robust to the exact payoff values, in the sense that small changes to the entries in the
game matrices do not cause the Nash equilibria to fluctuate wildly; otherwise, even if equilibria can be
computed, they may not actually be meaningful for understanding behavior in the game that is played. In
this work, we focus on such games and analyze their structural properties as well as their implications
to the equilibrium computation problem. We show how their structure can be leveraged to obtain better
algorithms for computing approximate Nash equilibria, as well as strategies close to true Nash equilibria.
1 For example, if agents are two corporations with various possible actions in some proposed market, the precise payoffs
to the corporations may depend on specific quantities such as demand for electricity or the price of oil, which cannot be fully
known in advance but only estimated.
T HEORY OF C OMPUTING, Volume 13 (13), 2017, pp. 1–31 2
NASH E QUILIBRIA IN P ERTURBATION -S TABLE G AMES
Furthermore, we provide such algorithmic guarantees even if we are given only a perturbation of the
actual stable game being played.
To formalize such settings we consider bimatrix games G that satisfy what we call (ε, ∆) perturbation
stability, meaning that for any game G0 within L∞ distance ε of G (each entry changed by at most ε), each
Nash equilibrium (p0 , q0 ) in G0 is ∆-close to some Nash equilibrium (p, q) in G, where closeness is given
by variation distance. Clearly, any game is (ε, 1) perturbation stable for any ε, and the smaller the ∆, the
more structure the (ε, ∆) perturbation-stable games have. In this paper we study the meaningful range of
parameters, several structural properties, and the algorithmic behavior of these games.
Our first main result shows that for an interesting and general range of parameters, the structure
of perturbation stable games can be leveraged to obtain better algorithms for equilibrium computation.
Specifically, we show that for any 0 ≤ ε ≤ ∆ ≤ 1, all n-action (ε, ∆) perturbation-stable games with at
2
most nO((∆/ε) ) Nash equilibria must have a well-supported ε-equilibrium of support
∆2 log(1 + ∆−1 )
O log n .
ε2
2 2 −1
This yields an nO((∆ /ε ) log(1+∆ ) log n) -time algorithm for finding an ε-equilibrium, improving by a factor
O(1/(∆2 log(1 + ∆−1 ))) in the exponent over the bound of [28] for games satisfying this condition (and
reducing to the bound of [28] in the worst-case when ∆ = 1).2 Moreover, the stability condition can be
further used to show that the approximate equilibrium found will be ∆-close to a true equilibrium, and
this holds even if the algorithm is given as input only a perturbation to the true underlying stable game.
A particularly interesting class of games for which our results provide a dramatic improvement
are those that satisfy what we call t-uniform stability to perturbations. These are games that for some
ε0 = 1/poly(n) and some t ≥ 1 satisfy the (ε,tε) perturbation-stability condition for all ε < ε0 . For
games satisfying t-uniform perturbation-stability with t = poly(log(n)), our results imply that we can
find 1/poly(n)-approximate equilibria in npoly(log(n)) time, i. e., achieve a fully quasi-polynomial-time
approximation scheme (FQPTAS). This is especially interesting because the results of [16] prove that it is
PPAD-hard to find 1/poly(n)-approximate equilibria in general games. Our results show that under the
(widely believed) assumption that PPAD is not contained in quasi-polynomial time [17], such uniformly
stable games are inherently easier for computation of approximate equilibria than general bimatrix
games.3 Moreover, variants of many games appearing commonly in experimental economics including
the public goods game, matching pennies, and identical interest game [22] satisfy this condition. See
Section 3, Section 5, and Appendix B for detailed examples.
Our second main result shows that there exist constants c1 , c2 such that computing an ε-equilibrium
in a game satisfying the (ε, c1 ε 1/4 ) perturbation-stability condition is as hard as computing a c2 ε 1/4 -
equilibrium in a general game. For our reduction, we show that any general game can be embedded into
one having the (ε, c1 ε 1/4 ) perturbation-stability property such that an ε equilibrium in the new game
yields a c2 ε 1/4 -equilibrium in the original game. This result implies that the interesting range for the
2 One should think of ∆ as a function of ε, with both possibly depending on n. E. g., ε = 1/√n and ∆ = 6ε. Additionally,
note that any game that is stable for ∆ < ε is also stable for ∆ = ε; therefore, the condition “ε ≤ ∆” is not needed if we replace
∆ with max{ε, ∆} in the support size guaranteed and the number of equilibria allowed.
3 The generic result of [28] achieves quasi-polynomial time only for ε = Ω(1/poly(log n)).
T HEORY OF C OMPUTING, Volume 13 (13), 2017, pp. 1–31 3
M ARIA -F LORINA BALCAN AND M ARK B RAVERMAN
(ε, ∆)-perturbation-stability condition i. e., where one could hope to do significantly better than in the
general case, is ∆ = o(ε 1/4 ).
We also connect our perturbation-stability condition to a seemingly very different approximation-
stability condition introduced by Awasthi et al. [5, 6]. Formally, a game satisfies the strong (ε, ∆)-
approximation-stability condition if all ε-approximate equilibria are contained inside a small ball of
radius ∆ around a single equilibrium.4 We prove that our perturbation-stability condition is equivalent
to a much weaker version of this condition that we call well-supported approximation stability. This
condition requires only that for any well-supported ε-approximate equilibrium5 (p, q) there exists a
Nash equilibrium (p∗ , q∗ ) that is ∆-close to (p, q). Clearly, the well-supported approximation-stability
condition is more general than strong (ε, ∆)-approximation-stability since rather than assuming that there
exists a fixed Nash equilibrium (p∗ , q∗ ) such that all ε-approximate equilibria are contained in a ball of
radius ∆ around (p∗ , q∗ ), it requires only that for any well-supported ε-approximate equilibrium (p, q)
there exists a Nash equilibrium (p∗ , q∗ ) that is ∆-close to (p, q). Thus, perturbation-stable games are
significantly more expressive than strongly approximation-stable games and Section 3 presents several
examples of games satisfying the former but not the latter. However, our lower bound (showing that
∆ = ω(ε 1/4 ) is as hard as the general case) also holds for the strong approximation-stability condition.
We also provide an interesting structural result showing that for ∆ ≥ ε, each Nash equilibrium of
2
an (ε, ∆) perturbation-stable game with nO((∆/ε) ) Nash equilibria must be 8∆-close to a well-supported
ε-approximate equilibrium of support only O((∆2 /ε 2 ) log(1 + ∆−1 ) log n). Similarly, a t-uniformly stable
2
game with nO(t ) equilibria has the property that for any ∆, each equilibrium is 8∆-close to a well-
supported ∆/t-approximate equilibrium with support of size O(t 2 log(1 + ∆−1 ) log n). This property
implies that in quasi-polynomial time we can in fact find a set of approximate Nash equilibria that cover
(within distance 8∆) the set of all Nash equilibria in such games.
It is interesting to note that for our algorithmic results for finding approximate equilibria we do
not require knowing the stability parameters. If the game happens to be reasonably stable, then we get
improved running times over the Lipton et al. [28] guarantees; if this is not the case, then we fall back to
the Lipton et al. [28] bound.6 However, given a game, it might be interesting to know how stable it is. In
this direction, we provide a characterization of stable constant-sum games along with an algorithm for
computing the strong stability parameters of a given constant-sum game.
1.1 Related work
In addition to results on computing (approximate) equilibria in worst-case instances of general bimatrix
games, there has also been a series of results on polynomial-time algorithms for computing (approximate)
4 Awasthi et al. [5] argue that this condition is interesting since in situations where one would want to use an approximate
Nash equilibrium for predicting how players will play (which is a common motivation for computing a Nash or an approximate
Nash equilibrium), without such a condition the approximate equilibrium found might be far from the equilibrium played.
5 Recall that in an ε-Nash equilibrium, the expected payoff of each player is within ε from her best response payoff; however
the mixed strategies may include poorly-performing pure strategies in their support. By contrast, the support of a well-supported
ε-approximate equilibrium may only contain strategies whose payoffs fall within ε of the player’s best-response payoff.
6 This is because algorithmically, we can simply try different support sizes in increasing order and stop when we find
strategies forming a (well-supported) ε-equilibrium. In other words, given the desired approximation level ε, we can find an
2 2 −1
ε-approximate equilibrium in time nO((∆ /ε ) log(1+∆ ) log n) where ∆ is the smallest value greater than or equal to ε such that
the game is (ε, ∆) perturbation stable.
T HEORY OF C OMPUTING, Volume 13 (13), 2017, pp. 1–31 4
NASH E QUILIBRIA IN P ERTURBATION -S TABLE G AMES
equilibria in specific classes of bimatrix games. For example, Bárány et al. [12] considered two-player
games with randomly chosen payoff matrices, and showed that with high probability, such games have
Nash equilibria with small support. Their result implies that in random two-player games, Nash equilibria
can be computed in expected polynomial time. Kannan and Theobald [25] provide an FPTAS for the case
where the sum of the two payoff matrices has constant rank and Adsul et al. [1] provide a polynomial time
algorithm for computing an exact Nash equilibrium of a rank-1 bimatrix game. Note that it is possible for
a game to be stable and yet have high rank, and on the other hand to be unstable and have rank 0; see
Appendix B.
Awasthi et al. [5, 6] analyzed the question of finding an approximate Nash equilibrium in games
that satisfy stability with respect to approximation. However, their condition is quite restrictive in that
it focuses only on games that have the property that all the Nash equilibria are close together, thus
eliminating from consideration most common games. By contrast, our perturbation stability notion, which
(as mentioned above) can be shown to be a generalization of their notion, captures many more realistic
situations. Our upper bound on approximate equilibria can be viewed as generalizing the corresponding
result of [5, 6] and it is significantly more challenging technically. Moreover, our lower bounds also
apply to the stability notion of [5, 6] and provide the first (nontrivial) results about the interesting range
of parameters for that stability notion as well.
In a very different context, for clustering problems, Bilu and Linial [13] analyze maxcut clustering
instances with the property that if the distances are perturbed by a multiplicative factor of α, then the
optimum does not change. They show that under √ this condition, one can find the optimum solution
in polynomial time so long as α ≥ min{n/dmin , ndmax } where dmin and dmax are the minimum and
maximum degrees in the graph, respectively. Following that work, a series of results [7, 11, 10, 3]
have analyzed center-based clustering under this stability assumption, including k-median, k-means, and
k-center objective functions, with the current best bounds finding the optimum solution when α ≥ 2 [3].
A survey of center-based clustering, including under various stability conditions, appears in [4]. Our
notion of perturbation stability is inspired by this work, but is substantially less restrictive in two respects.
First, we require stability only to small perturbations in the input, and second, we do not require the
solutions (Nash equilibria) to stay fixed under perturbation, but rather just ask that they have a bounded
degree of movement.
A very different direction of work in studying robust equilibrium solutions is given by Aghassi
and Bertsimas [2]. Both [2] and the present paper aim to make the notion of equilibria in games more
realistic. However, in [2] the equilibrium notion itself is modified. In standard probabilistic game theory,
the players choose their strategies to maximize their expected payoff given the distribution of the other
players’ strategies. In the setting of [2], the players aim to maximize the worst case possible outcome over
possible actions by other players. While our robustness notion refers to the robustness of the (standard
probabilistic) equilibrium solution to perturbations of the game, the robustness notion of [2] refers to each
player’s payoff being robust against uncertainty in other players’ behavior—thus it models the players as
pessimistic rather than Bayesian agents.
The notion of perturbation stability we consider in our paper is also related to the stability notions
considered by Lipton et al. [29] for economic solution concepts. The main focus of their work was
understanding whether for a given solution concept or optimization problem all instances are stable.
In this paper, our main focus is on understanding how rich the class of stable instances is, and what
T HEORY OF C OMPUTING, Volume 13 (13), 2017, pp. 1–31 5
M ARIA -F LORINA BALCAN AND M ARK B RAVERMAN
properties one can determine about their structure that can be leveraged to get better algorithms for
computing approximate Nash equilibria.7 We provide the first results showing better algorithms for
computing approximate equilibria in such games.
2 Preliminaries
We consider 2-player general-sum n-action bimatrix games. Let R denote the payoff matrix of the row
player and C denote the payoff matrix of the column player. If the row player chooses strategy i and the
column player chooses strategy j, the payoffs are Ri, j and Ci, j , respectively. We assume all payoffs are
scaled to the range [0, 1].
A mixed strategy for a player is a probability distribution over the set of his pure strategies. The i-th
pure strategy will be represented by the unit vector ei , that has 1 in the ith coordinate and 0 elsewhere. For
a pair (p, q) of mixed strategies, the payoff to the row player is the expected value of a random variable
which is equal to Ri, j with probability pi q j . Therefore the payoff to the row player is pT Rq. Similarly the
payoff to the column player is pT Cq. Given strategies p and q for the row and column player, we denote
by supp(p) and supp(q) the support of p and q, respectively.
A Nash equilibrium [31] is a pair (p∗ , q∗ ) of strategies such that no player has an incentive to deviate
unilaterally. Since mixed strategies are convex combinations of pure strategies, it suffices to consider
only deviations to pure strategies. In particular, a pair (p∗ , q∗ ) of mixed strategies is a Nash-equilibrium
if for every pure strategy i of the row player we have eTi Rq∗ ≤ p∗ T Rq∗ , and for every pure strategy j
of the column player we have p∗ T Ce j ≤ p∗ T Cq∗ . Note that in a Nash equilibrium (p∗ , q∗ ), all rows i
in the support of p∗ satisfy eTi Rq∗ = p∗ T Rq∗ and similarly all columns j in the support of q∗ satisfy
p∗ T Ce j = p∗ T Cq∗ .
Definition 2.1. A pair of mixed strategies (p, q) is an ε-equilibrium if both players have no more than ε
incentive to deviate. Formally, for all rows i, eTi Rq ≤ pT Rq + ε, and for all columns j, pT Ce j ≤ pT Cq + ε.
Definition 2.2. A pair (p, q) of mixed strategies is a well-supported ε-equilibrium if for any i ∈ supp(p)
(i. e., i s.t. pi > 0) we have eTi Rq ≥ eTj Rq − ε, for all j; similarly, for any i ∈ supp(q) (i. e., i s.t. qi > 0)
we have pT Cei ≥ pT Ce j − ε, for all j.
Definition 2.3. We say that a bimatrix game G0 specified by R0 ,C0 is an L∞ α-perturbation of G specified
by R,C if we have |Ri, j − R0i, j | ≤ α and |Ci, j −Ci,0 j | ≤ α for all i, j ∈ {1, . . . , n}.
Definition 2.4. For two probability distributions q and q0 , we define the distance between q and q0 as the
variation distance
1
d(q, q0 ) = |qi − q0i | = ∑ max(qi − q0i , 0) = ∑ max(q0i − qi , 0) .
2∑i i i
We define the distance between two strategy pairs as the maximum of the row-player’s and column-
player’s distances. That is,
d((p, q), (p0 , q0 )) = max[d(p, p0 ), d(q, q0 )] .
7 Just as in [29], one can show that for the stability conditions we consider in our paper, there exist unstable instances.
T HEORY OF C OMPUTING, Volume 13 (13), 2017, pp. 1–31 6
NASH E QUILIBRIA IN P ERTURBATION -S TABLE G AMES
It is easy to see that d is a metric. If d((p, q), (p0 , q0 )) ≤ ∆, then we say that (p0 , q0 ) is ∆-close to
(p, q). Finally, throughout this paper we use “log” to mean the natural logarithm.
3 Stable games
The main notion of stability we introduce and study in this paper requires that any Nash equilibrium in
a perturbed game be close to a Nash equilibrium in the original game. This is an especially motivated
condition since in many real world situations the entries of the game we analyze are merely based
on measurements and thus only approximately reflect the players’ payoffs. In order to be useful for
prediction, we would like that equilibria in the game we operate with be close to equilibria in the real
game played by the players. Otherwise, in games where certain equilibria of slightly perturbed games are
far from all equilibria in the original game, the analysis of behavior (or prediction) will be meaningless.
We give the formal definition.
Definition 3.1. A game G satisfies the (ε, ∆)-perturbation-stability condition if for any G0 that is an L∞
ε-perturbation of G and for any Nash equilibrium (p, q) in G0 , there exists a Nash equilibrium (p∗ , q∗ ) in
G such that (p, q) is ∆-close to (p∗ , q∗ ).8
Observe that fixing ε, a smaller ∆ means a stronger condition and a larger ∆ means a weaker condition.
Every game is (ε, 1)-perturbation stable, and as ∆ gets smaller, we might expect for the game to exhibit
more useful structure.
Another stability condition we consider in this work is approximation stability.9
Definition 3.2. A game satisfies the (ε, ∆)-approximation-stability condition if for any ε-equilibrium
(p, q) there exists a Nash equilibrium (p∗ , q∗ ) such that (p, q) is ∆-close to (p∗ , q∗ ).
A game satisfies the well-supported (ε, ∆)-approximation-stability condition if for any well-supported
ε-equilibrium (p, q) there exists a Nash equilibrium (p∗ , q∗ ) such that (p, q) is ∆-close to (p∗ , q∗ ).
Clearly, if a game satisfies the (ε, ∆)-approximation-stability condition, then it also satisfies the well-
supported (ε, ∆)-approximation-stability condition. Interestingly, we show that the perturbation-stability
condition is equivalent to the well-supported approximation-stability condition. Specifically, we prove
the following.
Theorem 3.3. A game satisfies the well-supported (2ε, ∆)-approximation-stability condition if and only
if it satisfies the (ε, ∆)-perturbation-stability condition.
Proof. Consider an n × n bimatrix game specified by R and C and assume it satisfies the well-supported
(2ε, ∆)-approximation-stability condition; we show it also satisfies the (ε, ∆)-perturbation-stability con-
dition. Consider R0 = R + Γ and C0 = C + Λ, where |Γi, j | ≤ ε and |Λi, j | ≤ ε, for all i, j. Let (p, q) be
an arbitrary Nash equilibrium in the new game specified by R0 and C0 . We will show that (p, q) is a
8 Note that the entries of the perturbed game are not restricted to the [0, 1] interval, and are allowed to belong to [−ε, 1 + ε].
This is a proper way to formulate the notion because it implies, for instance, that if G is (ε, ∆) stable to perturbations, then for
any α > 0, αG is (αε, ∆) stable to perturbations. Theorem 3.3 provides further evidence that this definition is proper.
9 This definition is inspired by a related notion in clustering initiated by [8, 9] and further studied by, e. g., [34] and [24].
T HEORY OF C OMPUTING, Volume 13 (13), 2017, pp. 1–31 7
M ARIA -F LORINA BALCAN AND M ARK B RAVERMAN
well supported 2ε-approximate Nash equilibrium in the original game specified by R and C. To see this,
note that by definition, (since (p, q) is a Nash equilibrium in the game specified by R0 and C0 ) we have
eTj R0 q ≤ pT R0 q ≡ vR for all j; therefore eTj Rq + eTj Γq ≤ vR , so eTj Rq ≤ vR + ε, for all j. On the other
hand we also have eTi Rq = eTi R0 q − eTi Γq ≥ vR − ε for all i ∈ supp(p). Therefore, eTi Rq ≥ eTj Rq − 2ε, for
all i ∈ supp(p) and for all j. Similarly we can show pT Cei ≥ pT Ce j − 2ε, for all i ∈ supp(q) and for
all j. This implies that (p, q) is well supported 2ε-approximate Nash in the original game, and so by
assumption is ∆-close to a Nash equilibrium of the game specified by R and C. So, this game satisfies the
(ε, ∆)-perturbation-stability condition.
In the reverse direction, consider an n × n bimatrix game specified by R and C and assume it
satisfies the (ε, ∆)-stability to perturbations condition. Let (p, q) be an arbitrary well supported 2ε Nash
equilibrium in this game. Let us define matrices R0 and C0 such that eTi R0 q = maxi0 ei0 T Rq − ε for all
i ∈ supp(p) and eTi R0 q ≤ maxi0 eTi0 Rq−ε for all i ∈
/ supp(p), pT C0 e j = max j0 pT Ce j0 −ε for all j ∈ supp(q)
T 0 T
and p C e j0 ≤ max j p Ce j0 − ε for all j ∈ / supp(q). Since (p, q) is a well supported 2ε Nash equilibrium
we know this can be done such that |(R0 − R)i, j | ≤ ε and |(C0 −C)i, j | ≤ ε, for all i, j (in particular, we have
to add quantities in [−ε, ε] to all the elements in rows i of R in the support of p and subtract quantities in
[0, ε] from all the elements in rows i of R not in the support of p; similarly for q). By design, (p, q) is
a Nash equilibrium in the game defined by R0 , C0 , and from the (ε, ∆)-perturbation-stability condition,
we obtain that it is ∆-close to a true Nash equilibrium of the game specified by R and C. Thus, any well
supported 2ε Nash equilibrium in the game specified by R and C is ∆-close to a true Nash equilibrium of
this game, as desired.
One can show that well-supported approximation stability is a strict relaxation of the approximation-
stability condition. For example, consider the 2 × 2 bimatrix game
1 1 1 1 − ε0
R= , C= .
1 − ε0 1 − ε0 1 1 − ε0
For ε < ε0 this game satisfies the well-supported (ε, 0)-approximation-stability condition, but does not
satisfy (ε, ∆)-approximation-stability for any ∆ < ε/ε0 . To see this note that eT1 Rq = 1, eT2 Rq = 1 − ε0 ,
pT Ce1 = 1, and pT Ce2 = 1 − ε0 for any p and q. This implies that the only well supported ε-Nash
equilibrium is identical to the Nash equilibrium (1, 0)T , (1, 0)T , thus the game is well-supported (ε, 0)-
approximation stable. On the other hand, the pair of mixed strategies (p, q) with p = (1 − ε/ε0 , ε/ε0 )T
and q = (1 − ε/ε0 , ε/ε0 )T is an ε-Nash equilibrium. The distance between (p, q) and the unique Nash is
ε/ε0 , thus this game is not (ε, ∆)-approximation stable for any ∆ < ε/ε0 .
Interestingly, approximation stability (which is a restriction of well-supported approximation stability
and perturbation stability) is itself a relaxation of the stability condition considered by Awasthi et
al. [5] which requires that all approximate equilibria be contained in a ball of radius ∆ around a single
Nash equilibrium. In this direction, we define the strong version of the stability conditions given in
Definitions 3.1 and 3.2 to be a reversal of quantifiers that asks that there be a single (p∗ , q∗ ) such that
each relevant (p, q) (equilibrium in an ε-perturbed game, ε-approximate equilibrium, or well-supported
ε-approximate equilibrium) is ∆-close to (p∗ , q∗ ). Here we give the formal definition.
Definition 3.4. A game G satisfies the strong (ε, ∆)-perturbation-stability condition if there exists (p∗ , q∗ )
a Nash equilibrium of G such that for any G0 that is an L∞ ε-perturbation of G we have that any Nash
equilibrium in G0 is ∆-close to (p∗ , q∗ ).
T HEORY OF C OMPUTING, Volume 13 (13), 2017, pp. 1–31 8
NASH E QUILIBRIA IN P ERTURBATION -S TABLE G AMES
A game G satisfies the strong (well-supported) (ε, ∆)-approximation-stability condition if there exists
(p∗ , q∗ ) a Nash equilibrium of G such that any (well supported) ε-equilibrium (p, q) is ∆-close to (p∗ , q∗ ).
It is immediate from its proof that Theorem 3.3 applies to the strong versions of the definitions
as well. We also note that our generic upper bounds in Section 4 apply to the most relaxed version
(perturbation-stability) and our generic lower bound in Section 5 apply to the most stringent version
(strong approximation stability).
Range of parameters. As shown in [5], if a game G satisfies the strong (ε, ∆)-approximation-stability
condition and has a non-trivial Nash equilibrium (an equilibrium in which the players do not both have full
support), then we must have ∆ ≥ ε. We can show that if a game G satisfies (ε, ∆)-approximation-stability
and if the union of all ∆-balls around all Nash equilibria does not cover the whole space,10 then we
must have 3∆ ≥ ε; see Lemma C.1 and Lemma C.2 in Appendix C. In Section 5 we further discuss the
meaningful range of parameters from the point of view of the equilibrium computation problem.
Examples. Variants of many classic games including the public goods game, matching pennies, and
identical interest games are stable. As an example, consider the following modified identical interest game.
Both players have n available actions. The first action is to stay home, and the other actions correspond to
n − 1 different possible meeting locations. If a player chooses action 1 (stay home), his payoff is 1/2 no
matter what the other player is doing. If the player chooses to go out to a meeting location, his payoff is 1
if the other player is there as well and it is 0 otherwise. This game has n pure equilibria (all (ei , ei )) and
n
2 mixed equilibria (all (1/2ei + 1/2e j , 1/2ei + 1/2e j )) and it is well-supported (ε, 2ε)-approximation
stable for all ε < 1/6. Note that it does not satisfy strong (well-supported) stability because it has multiple
very distinct equilibria. For further examples see Lemma 5.1 in Section 5, as well as Appendix B.
4 Equilibria in stable games
In this section we show we can leverage the structure implied by perturbation stability to improve over
the best known generic bound of [28]. We start by considering ε and ∆ as given.
2
Theorem 4.1. Let 0 ≤ ε ≤ ∆ ≤ 1. Consider a game with at most nO((∆/ε) ) Nash equilibria which satis-
fies the well-supported (ε, ∆)-approximation-stability condition (or the (ε/2, ∆)-perturbation-stability
condition). Then there exists a well supported ε-equilibrium where each player’s strategy has support
O((∆/ε)2 log(1 + ∆−1 ) log n).
This improves by a factor O(1/(∆2 log(1 + ∆−1 ))) in the exponent over the bound of [28] for games
satisfying these conditions (and reduces to the bound of [28] in the worst-case when ∆ = 1).
10 If the union of all ∆-balls around all Nash equilibria does cover the whole space, this is an easy case from our perspective.
Any (p, q) would be a ε-equilibria.
T HEORY OF C OMPUTING, Volume 13 (13), 2017, pp. 1–31 9
M ARIA -F LORINA BALCAN AND M ARK B RAVERMAN
Remark. Note that any game satisfying well-supported (ε, ∆)-approximation-stability for ∆ < ε also
satisfies well-supported (ε, ε)-approximation-stability. Therefore, the condition “ε ≤ ∆” can be removed
2
from Theorem 2 by replacing the number of equilibria allowed with nO(max{1,(∆/ε) }) and the support-size
guarantee with O(max{1, (∆/ε)2 } log(1 + max{ε, ∆}−1 ) log n).
Proof idea. We start by showing that any Nash equilibrium (p∗ , q∗ ) of G must be highly concentrated.
In particular, we show that for each of p∗ , q∗ , any portion of the distribution with substantial L1 norm
(having total probability at least 8∆) must also have high L2 norm. Specifically, the ratio of L2 norm
to L1 norm must be Ω((ε/∆)(log n)−1/2 ). This in turn can be used to show that each of p∗ , q∗ has all
but at most 8∆ of its total probability mass concentrated in a set (which we call the high part) of size
O((∆/ε)2 log(1 + 1/∆) log n). Once the desired concentration is proven, we can then perform a version
of the [28] sampling procedure on the low parts of p∗ and q∗ (with an accuracy of only ε/∆) to produce
overall an ε-approximate equilibrium of support only a constant factor larger. The primary challenge
in this argument is to prove that p∗ and q∗ are concentrated.11 This is done through our key lemma,
Lemma 4.2 below. In particular, Lemma 4.2 can be used to show that if p∗ (or q∗ ) had a portion with
substantial L1 norm and low L2 norm, then there must exist a deviation from p∗ (or q∗ ) that is far from all
equilibria and yet is a well-supported approximate-Nash equilibrium, violating the stability condition.
Proving the existence of such a deviation is challenging because of the large number of equilibria that
may exist. Lemma 4.2 synthesizes the key points of this argument.
Lemma 4.2. Let 0 ≤ ε ≤ ∆ ≤ 1. Let p̃ be an arbitrary distribution over {1, 2, . . . , n}. Let S =
c(∆/ε)2 log n for c ≥ 562 , and fix β ≤ 1 such that 1 − β ≥ 8∆. Assume that the entries of p̃ can be
partitioned into two sets H and L such that
k p̃L k1 = 1 − β , k p̃H k1 = β , and k p̃L k22 ≤ (1 − β )2 /S .
Let us fix k1 n-dimensional vectors v(1) , . . . , v(k1 ) with entries in [−1, 1] and k2 distributions p(1) , . . . , p(k2 ) ,
0 2
where k1 = n2 and k2 ≤ nc (∆/ε) for c0 = (2/225)c − log(6)/ log(n). Then there exists p̃0 with supp( p̃0 ) ⊆
supp( p̃) such that
(1) d( p̃, p̃0 ) = 3∆,
(2) p̃0 · v(i) ≤ p̃ · v(i) + ε for all i ∈ {1, . . . , k1 }, and
(3) d( p̃0 , p(i) ) > d( p̃, p(i) ) − ∆ for all i ∈ {1, . . . , k2 }.
Proof. We show the desired result by using the probabilistic method. We randomly partition the entries
in p̃L into two sets A and B, moving 3∆ probability mass from A to B to create p̃0 (moving an amount of
probability to/from p̃i proportional to the value of p̃i ); for i ∈ H, we let p̃0i = p̃i . We next carefully use
concentration bounds together with both our L1 and L2 bounds on p̃L to show that with high probability,
conditions (2) and (3) are both satisfied.
11 We note that [5] prove an upper bound for the strong approximation-stability condition using the same concentration idea.
However, proving the desired concentration is significantly more challenging in our case since we deal with many equilibria.
T HEORY OF C OMPUTING, Volume 13 (13), 2017, pp. 1–31 10
NASH E QUILIBRIA IN P ERTURBATION -S TABLE G AMES
Formally, let us define the random variable Xi = 1 with probability 1/2 and Xi = 0 with probability
1/2. Define
(
p̃i for i ∈ H,
p̃0i =
p̃i + ∑3∆ p̃p̃i Xi Xi i − ∑3∆ p̃p̃i (1−X i)
i (1−Xi )
for i ∈ L.
i∈L i∈L
We have " #
1−β
E ∑ p̃i Xi = 2
.
i∈L
By applying McDiarmid’s inequality (see Theorem A.1 in Appendix A) and using the fact that k p̃L k22 ≤
(1 − β )2 /S, we obtain that with probability at least 3/4 we have:
1−β 1−β 1−β 1−β
∑ p̃i Xi − 2
≤
12
which also implies ∑ p̃i (1 − Xi ) − 2
≤
12
. (4.1)
i∈L i∈L
Assume that this happens. In this case, p̃0 is a legal mixed strategy for the row player and by
construction we have d( p̃, p̃0 ) = 3∆.
Let v be an arbitrary vector in {v(1) , . . . , v(k1 ) }. We have:
0 ∑i∈L p̃i Xi vi ∑i∈L p̃i (1 − Xi )vi
p̃ · v = p̃ · v + 3∆ − .
∑i∈L p̃i Xi ∑i∈L p̃i (1 − Xi )
Define
Z1 = ∑ p̃i Xi vi , Z2 = ∑ p̃i Xi , Z3 = ∑ p̃i (1 − Xi )vi , Z4 = ∑ p̃i (1 − Xi ) ,
i∈L i∈L i∈L i∈L
so we have:
0 Z1 Z3
p̃ · v = p̃ · v + 3∆ − .
Z2 Z4
Using McDiarmid’s inequality we get that with probability at least 1 − 1/n3 , each of the quantities
Z1 , Z2 , Z3 , Z4 is within ((1 − β )/28)(ε/∆) of its expectation; we are using here the fact that the value of
Xi can change any one of the quantities by at most p̃i , so the exponent in the McDiarmid bound is
2 1−β 2
− ∆ε 28
c
≤− log n .
∑i∈L 2i
p̃ 282
Also, we have
1−β
E[Z2 ] = E[Z4 ] = and E[Z1 ] = E[Z3 ] .
2
T HEORY OF C OMPUTING, Volume 13 (13), 2017, pp. 1–31 11
M ARIA -F LORINA BALCAN AND M ARK B RAVERMAN
So, we get that with probability at least 1 − 1/n3 we have
!
0 E[Z1 ] + (1−β
28∆
)ε
E[Z3 ] − (1−β
28∆
)ε
p̃ · v − p̃ · v ≤ 3∆ 1−β (1−β )ε
−1−β (1−β )ε
2 − 28∆ 2 + 28∆
2 2
ε ε
!
( 1−β )E[Z1 ] + 14∆ ( 1−β )E[Z3 ] − 14∆
= 3∆ ε − ε
1 − 14∆ 1 + 14∆
2 ε ε
= 3∆ E[Z1 ] + 1+
1−β 14∆ 14∆
2 ε ε 1
− E[Z3 ] − 1− ε 2
1−β 14∆ 14∆ 1 − ( 14∆ )
2 ε ε
≤ 3.1∆ E[Z1 ] + 1+
1−β 14∆ 14∆
2 ε ε
− E[Z3 ] − 1−
1−β 14∆ 14∆
ε ε
2
= 3.1∆ (E[Z1 ] + E[Z3 ]) + .
1−β 14∆ 7∆
Finally, using the fact that Z1 + Z3 ≤ ∑i∈L p̃i = 1 − β , we get
ε ε
p̃0 · v − p̃ · v ≤ 3.1∆ +
7∆ 7∆
yielding the desired bound p̃0 · v ≤ p̃ · v + ε. Applying the union bound over all i ∈ {1, . . . , k1 } we obtain
that the probability that there exists v in v(1) , . . . , v(k1 ) such that p̃0 · v ≥ p̃ · v + ε is at most 1/3.
Consider an arbitrary distribution p in {p(1) , . . . , p(k2 ) }. Assume that p = p̃ + g. By definition, we
have:
1 3∆ p̃i Xi 3∆ p̃i (1 − Xi ) 1
d(p, p̃0 ) = ∑ p̃i + gi − p̃i − ∑i∈L p̃i Xi + ∑ni∈L p̃i (1 − Xi ) + 2 ∑ |gi |
2 i∈L i∈H
1 3∆ p̃i Xi 3∆ p̃i (1 − Xi ) 1
= ∑ gi − ∑i∈L p̃i Xi + ∑i∈L p̃i (1 − Xi ) + 2 ∑ |gi |
2 i∈L i∈H
1 6∆ p̃i Xi 6∆ p̃i (1 − Xi ) 1 6∆ p̃i Xi 6∆ p̃i (1 − Xi ) 1
≥ ∑ gi − 1 − β + 1 − β − 2 ∑ 5(1 − β ) + 7(1 − β ) + 2 ∑ |gi |
2 i∈L i∈L i∈H
1 6∆ p̃i Xi 6∆ p̃i (1 − Xi ) 1 6∆ p̃i 1
≥ ∑ gi − + − ∑ + ∑ |gi |
2 i∈L 1−β 1−β 2 i∈L 5(1 − β ) 2 i∈H
1 6∆ p̃i Xi 6∆ p̃i (1 − Xi ) 3∆ 1
= ∑ gi − + − + ∑ |gi | ,
2 i∈L 1−β 1−β 5 2 i∈H
where the first inequality follows from applying relation (4.1) to the denominators and the fact that the
sum of the two denominators equals 1 − β . The last equality also follows from the fact that k p̃L k1 = 1 − β .
T HEORY OF C OMPUTING, Volume 13 (13), 2017, pp. 1–31 12
NASH E QUILIBRIA IN P ERTURBATION -S TABLE G AMES
Let us denote by
1 6∆ p̃i Xi 6∆ p̃i (1 − Xi )
Z= ∑ gi − 1 − β + 1 − β .
2 i∈L
We have:
1 1 6∆ p̃i 1 6∆ p̃i 1
E[Z] = ∑ 2 i 1 − β 2 i 1 − β ≥ 2 ∑ |gi | ,
2 i∈L
g − + g +
i∈L
therefore
1 3∆ 1 1 3∆ 3∆
E[d(p, p̃0 )] ≥ E[Z] + ∑ |gi | − 5 ≥ 2 ∑ |gi | + 2 ∑ |gi | − 5 = d(p, p̃) − 5 .
2 i∈H i∈L i∈H
We can now apply McDiarmid’s inequality (see Theorem A.1) to argue that with high probability Z is
within 2∆/5 of its expectation. Note that ci = 6∆ p̃i /(1 − β ). Therefore:
−2∆2 (1−β )2 /(225 ∑ p̃2i ∆2 ) 1
Pr {|Z − E[Z]| ≥ 2∆/5} ≤ 2e i∈L ≤ 2e−(2/225)S ≤ ,
3k2
where the last inequality follows from the definition of c0 . This then implies that
1
Pr d(p, p̃0 ) ≤ d(p, p̃0 ) − ∆ ≤
.
3k2
By the union bound we get that the probability that there exists a p in {p(1) , . . . , p(k2 ) } such that d(p, p̃0 ) ≤
d(p, p̃0 ) − ∆ is at most 1/3. Summing up overall all possible events we get that there is a non-zero
probability of (1), (2), (3) happening, as desired.
Proof of Theorem 4.1. Let (p∗ , q∗ ) be an arbitrary Nash equilibrium. We show that each of p∗ and q∗ are
highly concentrated, meaning that all but at most 8∆ of their total probability mass is concentrated in a
set of size O((∆/ε)2 log(1 + 1/∆) log n). Let’s consider p∗ (the argument for q∗ is similar). We begin by
partitioning it into its heavy and light parts. Specifically, we greedily remove the largest entries of p∗ and
place them into a set H (the heavy elements) until either
(a) the remaining entries L (the light elements) satisfy the condition that ∀i ∈ L, Pr[i] ≤ (1/S) Pr[L] for
S as in Lemma 4.2, or
(b) Pr[H] ≥ 1 − 8∆,
whichever comes first. Using the fact that the game satisfies the well-supported (ε, ∆)-approximation-
stability condition, we will show that case (a) cannot occur first, which will imply that p∗ is highly
concentrated.
In the following, we denote β as the total probability mass over H. Assume by contradiction that
case (a) occurs first. Note that we have kpL k1 = 1 − β , kpH k1 = β , and
1 1
∑(pi )2 ≤ S ∑ pi ∑ pi = S (1 − β )2 ,
i∈L i∈L i∈L
T HEORY OF C OMPUTING, Volume 13 (13), 2017, pp. 1–31 13
M ARIA -F LORINA BALCAN AND M ARK B RAVERMAN
so kpL k22 ≤ (1 − β )2 /S. Let vi, j = C(ei − e j ). Since (p∗ , q∗ ) is a Nash equilibrium we know that
p∗ · vi, j ≤ 0 for all i and for all j ∈ supp(q∗ ).
By Lemma 4.2 there exists p̃0 such that (1) d(p∗ , p̃0 ) = 3∆, (2) p̃0 · vi, j ≤ p∗ · vi, j + ε for all i and
for all j ∈ supp(q∗ ) and (3) d( p̃0 , p(i) ) > d(p∗ , p(i) ) − ∆ for all Nash equilibria p(i) . By (2) we have
that p̃0 · vi, j ≤ ε for all i and for all j ∈ supp(q∗ ), which implies that ( p̃0 , q∗ ) is a well supported ε-
approximate equilibrium (since by (2) the column player has at most an ε incentive to deviate and since
supp( p̃0 ) ⊆ supp(p∗ ) we know that the row player has no incentive to deviate). By (1) we also have
that ( p̃0 , q∗ ) is 3∆-far from (p∗ , q∗ ). We now use (3) to show that ( p̃0 , q∗ ) is ∆-far from all the other
equilibria as well. Let p be such an equilibrium. Note that if d(p, p∗ ) > 4∆, then clearly, by the triangle
inequality d(p, p̃0 ) > ∆. If d(p, p∗ ) < 2∆, clearly, by the triangle inequality, d(p, p̃0 ) > ∆. Finally if
d(p, p∗ ) ∈ [2∆, 4∆], then by (3), we that d(p, p̃0 ) > ∆, as desired.
Overall we get that ( p̃0 , q∗ ) is a well-supported ε-approximate equilibrium that is ∆-far from all the
other equilibria of the game. This contradicts the well supported (ε, ∆)-approximation-stability condition,
as desired.
Thus, case (b) occurs first, which implies that p∗ is highly concentrated. In particular, the fact that
case (a) has not yet occurred implies that the greedy construction of H has been able at each step to choose
an entry i such that Pr[i] > (1/S) Pr[L]; so, when β = Pr[H] ≥ 1 − 8∆, H has at most S log (1 + (8∆)−1 )
elements. The key idea now is that since 1 − β ≤ 8∆, we can apply the sampling argument of [28] to L
with accuracy parameter O(ε/∆) and then union the result with H.
Specifically, let us decompose p∗ as
p∗ = β pH + (1 − β )pL .
Applying the sampling argument of [28] to pL , we have that by sampling a multiset X of S elements from
L = supp(pL ), we are guaranteed that for any column e j , we have
(UX )T Ce j − pTL Ce j ≤ (ε/8∆) ,
where UX is the uniform distribution over X. This means that for p̃ = β pH + (1 − β )US , all columns e j
satisfy
|p∗ T Ce j − p̃T Ce j | ≤ ε/2 .
We have thus found the row portion of an ε-equilibrium with support of size S log (1 + 1/(8∆)) as
desired.
2
Corollary 4.3. Let 0 ≤ ε ≤ ∆ ≤ 1. Let G be a game with at most nO((∆/ε) ) Nash equilibria satisfying the
well-supported (ε, ∆)-approximation-stability condition (or the (ε/2, ∆)-perturbation-stability condition).
Then
2 −1 ) log n)
(1) given G we can find a well-supported ε-equilibrium (p, q) of G in time nO((∆/ε) log(1+∆ ;
(2) given G0 , an L∞ ε/6-perturbation of G, we can find a well supported ε-equilibrium (p, q) of G in
2 −1
time nO((∆/ε) log(1+∆ ) log n) .
In both cases, (p, q) is ∆-close to a Nash equilibrium (p∗ , q∗ ) of G.
T HEORY OF C OMPUTING, Volume 13 (13), 2017, pp. 1–31 14
NASH E QUILIBRIA IN P ERTURBATION -S TABLE G AMES
Proof. (1) By Theorem 4.1, we can simply try all supports of size O((∆/ε)2 log(1 + ∆−1 ) log n) and for
each of them write an LP to search for a well-supported ε-Nash equilibrium.
(2) By Theorem 4.1, G has a well-supported ε/3-Nash equilibrium with support of size O((∆/ε)2 ·
log(1 + ∆−1 ) log n). Since G0 is an L∞ ε/6-perturbation of G, then this is also a well-supported 2ε/3-Nash
equilibrium of G0 . Thus by trying all supports of size O((∆/ε)2 log(1 + ∆−1 ) log n) in G0 we can find a
well-supported 2ε/3-Nash equilibrium of G0 . Since G is an L∞ ε/6-perturbation of G0 , this will be a
well-supported ε-Nash equilibrium of G.
Corollary 4.3 improves by a factor O(1/(∆2 log(1 + ∆−1 ))) in the exponent over the bound of [28]
for games satisfying this condition. The most interesting range of improvements happens when ε is a
√
function on n and ∆ is a function of ε; e. g., ε = 1/ n, ∆ = 10ε—in this case we obtain an improvement
of O(n/ log(n)) in the exponent over the bound of [28].
The proof of Theorem 4.1 also implies an interesting structural result, namely, that each Nash
equilibrium of such a game is close to a pair of strategies of small support and by the triangle inequality,
the same will happen for any perturbation of G. We state the result.
2
Theorem 4.4. Let 0 ≤ ε ≤ ∆ ≤ 1. Consider a game G with at most nO((∆/ε) ) Nash equilibria which
satisfies well-supported (ε, ∆)-approximation-stability condition (or the (ε/2, ∆)-perturbation-stability
condition). Then it must be the case that
(1) any Nash equilibrium in G is 8∆-close to a pair of mixed strategies, each with support of size at
most O((∆/ε)2 log(1 + ∆−1 ) log n) ;
(2) for any game G0 with L∞ distance ε/2 from G, any Nash equilibrium in G0 is 9∆-close to a pair of
mixed strategies, each with support of size O((∆/ε)2 log(1 + ∆−1 ) log n).
Proof. Consider an arbitrary Nash equilibrium (p∗ , q∗ ) of G. The proof of Theorem 4.1 shows that the
supports of p∗ and q∗ can be partitioned into heavy and light sets so that p∗ = pH + pL and q∗ = qH + qL ,
where pH and qH each have probability mass at least 1 − 8∆ and each has support size O((∆/ε)2 log(1 +
∆−1 ) log n). Thus, (p∗ , q∗ ) is 8∆-close to (pH /|pH |, qH /|qH |). Part (2) then uses that fact that any Nash
equilibrium in G0 must be ∆-close to some Nash equilibrium in G due to perturbation-stability.
So far in Theorem 4.1 and Corollary 4.3 we have considered ε and ∆ fixed. It is also interesting to
consider games where the stability conditions hold uniformly for all sufficiently small ε. We call such
games uniformly stable.
Definition 4.5. Consider t ≥ 1. We say that a game is t-uniformly perturbation-stable (or t-uniformly
well-supported approximation-stable) if there exists ε0 = 1/poly(n) such that for all ε ≤ ε0 , G satisfies
(ε,tε) stability to perturbations (or the well-supported (ε,tε)-approximation-stability).
For games satisfying the t-uniform perturbation-stability condition with t = O(poly(log(n))) we can
find 1/poly(n)-approximate equilibria in npoly(log(n)) time, and more generally ε-approximate equilibria
in nlog (1/ε)poly(log(n)) time, thus achieving a FQPTAS. This provides a dramatic improvement over the
best worst-case bounds known.
Corollary 4.6. Let t = O(poly(log(n))). Then the following hold.
T HEORY OF C OMPUTING, Volume 13 (13), 2017, pp. 1–31 15
M ARIA -F LORINA BALCAN AND M ARK B RAVERMAN
(1) There is a FQPTAS to find approximate equilibria in games satisfying the t-uniform well-supported
approximation-stability condition (or the t-uniform perturbation-stability condition) with at most
2
nO(t ) Nash equilibria.
(2) Games satisfying the t-uniform well-supported approximation-stability condition (or the t-uniform
2
perturbation-stability condition) with at most nO(t ) Nash equilibria have the property that for any
∆ each equilibrium is 8∆-close to a pair of mixed strategies each with support of size O(t 2 log(1 +
∆−1 ) log n); moreover, for any L∞ -perturbation of magnitude ∆/t of such games, it must be the
case that any Nash equilibrium in G0 is 9∆-close to a pair of mixed strategies each with support of
size O(t 2 log(1 + ∆−1 ) log n).
Corollary 4.6 is especially interesting because the results of [16] prove that it is PPAD-hard to find
1/poly(n)-approximate equilibria in general bimatrix games. Our results shows that under the (widely
believed) assumption that PPAD is not contained in quasi-polynomial time [17], such uniformly stable
games are inherently easier for computation of approximate equilibria than general bimatrix games.
Moreover, variants of many games appearing commonly in experimental economics including the public
goods game and identical interest game [22] satisfy this condition (see Appendix B).
5 Converting the general case to the stable case
In this section we show that computing an ε-equilibrium in a game satisfying the strong (ε, Θ(ε 1/4 ))-
approximation-stability condition is as hard as computing a Θ(ε 1/4 )-equilibrium in a general game. For
our reduction, we show that any general game can be embedded into one having the strong (ε, Θ(ε 1/4 ))-
approximation-stability property such that an ε equilibrium in the new game yields a Θ(ε 1/4 ) equilibrium
in the original game. Since all the notions of stability considered in this paper generalize the strong
approximation-stability condition, the main lower bound in this section (Theorem 5.2) applies to these
notions as well.
We start by stating a key lemma that shows the existence of a family of modified matching pennies
games that satisfy strong approximation stability and have certain properties that will be helpful in proving
our main lower bound.
Lemma 5.1. Assume that ∆ ≤ 1/10. Consider the games defined by the following matrices.
1 + α1,1 1 + α1,2 . . . 1 + α1,n 0 γ1,1 γ1,2 . . . γ1,n 1
1 + α2,1 1 + α2,2 . . . 1 + α2,n 0 γ2,1 γ2,2 . . . γ2,n 1
R=
... ... ,
C=
... ... ,
1 + αn,1 1 + αn,2 . . . 1 + αn,n 0 γn,1 γn,2 . . . γn,n 1
0 0 ... 0 2∆ 2∆ 2∆ . . . 2∆ 0
where αi, j ∈ [−∆, 0] and γi, j ∈ [0, ∆] for all i, j. Each such game satisfies strong (∆2 , 4∆)-approximation-
stability. Moreover if (p, q) is a ∆2 -Nash equilibrium, then we must have
∆/2 ≤ p1 + · · · + pn ≤ 4∆ and ∆/2 ≤ q1 + · · · + qn ≤ 4∆ .
T HEORY OF C OMPUTING, Volume 13 (13), 2017, pp. 1–31 16
NASH E QUILIBRIA IN P ERTURBATION -S TABLE G AMES
Since the proof of Lemma 5.1 is somewhat tedious we defer its proof at the end of this section. We
now present the main result of this section.
Theorem 5.2. Computing an ε-equilibrium in a game satisfying the strong (ε, 8ε 1/4 )-approximation-
stability condition is as hard as computing an (8ε)1/4 -equilibrium in a general game.
Proof. The main idea is to construct a linear embedding of any given game into a larger, stable game in
such a way that incentives are not magnified too greatly when approximate equilibria of the new game
are translated back into strategies for the original game. In particular, consider ∆ = (8ε)1/4 and consider
a general game with n × n payoff matrices R and C. Let us construct a new game with (n + 1) × (n + 1)
payoff matrices R0 and C0 defined as follows.
0 1n,n − (∆/2)1n,n + (∆/2)R 0n,1
R =
01,n 2∆
and
(∆/2)1n,n + (∆/2)C 1n,1
C0 = .
2∆11,n 0
(For s, r > 0, the matrix 1s,r is the s × r matrix with all entries set to 1 and the matrix 0s,r is the s × r
matrix with all entries set to 0.) By Lemma 5.1, the new game defined by R0 and C0 satisfies the strong
(∆2 , 4∆)-approximation-stability condition, which in turn implies satisfying (ε, 8ε 1/4 )-approximation-
stability (since ε ≤ ∆2 and 4(8)1/4 ≤ 8). We show next that any ∆4 /8-equilibrium in this new game
(defined by R0 and C0 ) induces a ∆-equilibrium in the original game (defined by R and C). Since
∆ = (8ε)1/4 , this implies the desired result.
Let (p, q) be a ∆4 /8-equilibrium in the new game. By Lemma 5.1 (since ∆4 /8 ≤ ∆2 ), p must have
β ∆ probability mass in the first n rows and q must have α∆ probability mass in the first n columns, where
α, β ∈ [1/2, 4]. Let p f , q f denote p restricted to the first n rows and q restricted to the first n columns.
Let p̃ f = p f /|p f | and q̃ f = q f /|q f |, where |p f | = β ∆ and |q f | = α∆. We show that that ( p̃ f , q̃ f ) is a
∆-equilibrium in the original game defined by R and C. We prove this by contradiction. Assume this is
not the case. Assume first that the row player has an ∆ incentive to deviate. There must exist ei such that
eTi Rq̃ f > p̃ f Rq̃ f + ∆ .
Multiplying both sides by αβ ∆3 /2 and using the fact that αβ ≥ 1/4 we obtain the following inequality.
β ∆eTi (∆/2)Rq f > p f (∆/2)Rq f + ∆4 /8 . (5.1)
We clearly have β ∆eTi (1n,n − (∆/2)1n,n )q f = pTf (1n,n − (∆/2)1n,n )q f , and by adding this quantity as well
as pn+1 (2∆)qn+1 to both sides of inequality (5.1) we get
β ∆eTi (1n,n − (∆/2)1n,n + (∆/2)R)q f + pn+1 (2∆)qn+1
> p f (1n,n − (∆/2)1n,n + (∆/2)R)q f + pn+1 (2∆)qn+1 + ∆4 /8 ,
T HEORY OF C OMPUTING, Volume 13 (13), 2017, pp. 1–31 17
M ARIA -F LORINA BALCAN AND M ARK B RAVERMAN
which implies
(β ∆ei + pn+1 en+1 )T R0 q > pT R0 q + ∆4 /8 .
Therefore there exists a deviation for the row player (namely moving all β ∆ probability mass from rows
1, 2, . . . , n onto row i), yielding a benefit of ∆4 /8 to the row player. This contradicts the assumption that
(p, q) is an ∆4 /8-equilibrium in the new game, as desired.
Assume now that the column player has an ∆ incentive to deviate. There must exist e j such that
p̃Tf Ce j > p̃Tf Cq̃ f + ∆ .
Multiplying both sides by αβ ∆3 /2 and using the fact that αβ ≥ 1/4 we get:
pTf (∆/2)C(α∆e j ) > pTf (∆/2)Cq f + ∆4 /8 .
We have pTf (∆/2)1n,n α∆e j = pTf (∆/2)1n,n q f , so:
pTf ((∆/2)C + (∆/2)1n,n )α∆e j > pTf ((∆/2)C + (∆/2)1n,n )q f + ∆4 /8 . (5.2)
We also have pn+1 (2∆, . . . , 2∆)α∆e j = pn+1 (2∆, . . . , 2∆)q f . By adding this quantity as well as the term
pTf (1, . . . , 1)T qn+1 to both sides of inequality (5.2) we get:
pT C0 (α∆e j + qn+1 en+1 ) > pT C0 q + ∆4 /8 .
Therefore there exists a deviation for the column player (namely moving all α∆ probability mass from
columns 1, 2, . . . , n onto column i), yielding a benefit of ∆4 /8 to the column player. This contradicts the
assumption that (p, q) is an ∆4 /8-equilibrium in the new game, as desired.
Note. Theorem 5.2 implies that for any ε ≤ (1/8)(0.3393)4 , an algorithm for finding an ε-equilibrium
in a game satisfying the strong (ε, 8ε 1/4 )-approximation-stability condition would imply a better than
best currently known algorithm for finding approximate equilibria in general games (the best bound is
currently 0.3393).
We end this section by proving Lemma 5.1.
Proof of Lemma 5.1. First note that eTn+1 Rq = 2∆qn+1 and
eTi Rq = (1 + αi,1 )q1 + (1 + αi,2 )q2 + · · · + (1 + αi,n )qn for 1 ≤ i ≤ n.
Also pT Cen+1 = p1 + · · · + pn and
pT Ce j = p1 γ1, j + · · · + pn γn, j + 2∆pn+1 for 1 ≤ j ≤ n.
By a simple case analysis, one can show that any Nash equilibrium (p, q) must have 0 < pn+1 < 1
and 0 < qn+1 < 1. (This is also implicit in our analysis on ∆2 -Nash equilibria below.) This then implies
that in any Nash equilibrium (p, q) such that pi 6= 0 we must have:
2∆qn+1 = (1 + αi,1 )q1 + (1 + αi,2 )q2 + · · · + (1 + αi,n )qn . (5.3)
T HEORY OF C OMPUTING, Volume 13 (13), 2017, pp. 1–31 18
NASH E QUILIBRIA IN P ERTURBATION -S TABLE G AMES
Similarly, in any Nash equilibrium (p, q) such that q j 6= 0 we must have:
p1 + · · · + pn = p1 γ1, j + · · · + pn γn, j + 2∆pn+1 . (5.4)
Identities (5.3) and (5.4) together with the fact that αi, j ∈ [−∆, 0] and γi, j ∈ [0, ∆] for all i, j, imply
that there must exist a Nash equilibrium (p, q) satisfying:
2∆ 2∆ 2∆ 2∆
≤ p1 + · · · + pn ≤ and ≤ q1 + · · · + qn ≤ . (5.5)
1 + 2∆ 1+∆ 1 + 2∆ 1+∆
To get the desired stability guarantee we now show that any ∆2 -equilibrium must have ∆/2 ≤
p1 + · · · + pn ≤ 4∆ and ∆/2 ≤ q1 + · · · + qn ≤ 4∆. (This in turn implies that any ∆2 -equilibrium must be
at distance at most 4∆ from a Nash equilibrium satisfying relation (5.5).) We prove this by contradiction.
Consider an arbitrary ∆2 -equilibrium (p, q). We analyze a few cases.
Case 1. Suppose pn+1 > 1 − ∆/2. Then the column player’s payoff for column n + 1 is pT Cen+1 =
∑ni=1 pi ≤ ∆/2. But the column player’s payoff for a column j ∈ {1, . . . , n} is:
n
pT Ce j = ∑ γi, j pi + 2∆pn+1 ≥ 2∆(1 − ∆/2) .
i=1
If qn+1 > 1/2 then the column player has incentive to deviate at least:
pT Ce j − pT Cq ≥ (1/2)[2∆(1 − ∆/2) − ∆/2] > ∆/2 > ∆2 ,
which cannot happen since (p, q) is a ∆2 -equilibrium. On the other hand if qn+1 ≤ 1/2, then the row player
has huge incentive to deviate. Specifically, the row’s player payoff for row 1 is eT1 Rq ≥ (1/2)(1 − ∆),
but row’s player payoff for row n + 1 is eTn+1 Rq ≤ (1/2)2∆ = ∆. Thus in this case the row player has
incentive to deviate at least:
eT1 Rq − pT Rq ≥ (1 − ∆/2)[1/2(1 − ∆) − ∆] > ∆ ,
which cannot happen since (p, q) is a ∆2 -equilibrium.
Case 2. Suppose pn+1 < 1 − 4∆. Then the column player’s payoff for column n + 1 is pT Cen+1 =
n
∑i=1 pi ≥ 4∆, whereas the column player’s payoff for a column j ∈ {1, . . . , n} is
n
pT Ce j = p1 γ1, j + · · · + pn γn, j + 2∆pn+1 ≤ ∆ ∑ pi + 2∆pn+1 = ∆(1 − pn+1 ) + 2∆pn+1 ≤ 2∆ .
i=1
So, if qn+1 < 1 − ∆/2, then the column player has incentive to deviate at least
pT Cen+1 − pT Cq > (∆/2)[4∆ − 2∆] ≥ ∆2 ,
a contradiction. On the other hand, if qn+1 > 1 − ∆/2, then the row player’s payoff for row n + 1 is
eTn+1 Rq ≥ 2∆(1 − ∆/2), but the row player’s payoff for a row i ∈ {1, . . . , n} is:
n
eTi Rq = ∑ (1 + αi, j )q j ≤ 1 − qn+1 ≤ ∆/2 .
j=1
T HEORY OF C OMPUTING, Volume 13 (13), 2017, pp. 1–31 19
M ARIA -F LORINA BALCAN AND M ARK B RAVERMAN
So, in this case, the row player has incentive to deviate at least
eTn+1 Rq − pT Rq ≥ 4∆[2∆(1 − ∆/2) − ∆/2] > ∆2 ,
which cannot happen since (p, q) is a ∆2 -equilibrium.
Case 3. Suppose qn+1 > 1 − ∆/2. As in the bottom-half of the case 2 analysis we have that the row
player’s payoff for row n + 1 is eTn+1 Rq ≥ 2∆(1 − ∆/2), but the row player’s payoffs for rows 1, . . . , n are
≤ ∆/2. So, if pn+1 < 1 − ∆ then the row player has incentive to deviate at least
eTn+1 Rq − pT Rq ≥ ∆[2∆(1 − ∆/2) − ∆/2] > ∆2 ,
which cannot happen since (p, q) is a ∆2 -equilibrium. On the other hand, if pn+1 ≥ 1 − ∆, then the column
player’s payoff for column n + 1 is pT Cen+1 = ∑ni=1 pi ≤ ∆, but the column player’s payoff for a columns
j ∈ {1, . . . , n} is:
pT Ce j = p1 γ1, j + · · · + pn γn, j + 2∆pn+1 ≥ (1 − ∆)(2∆) .
So, the column player has incentive to deviate at least
pT Ce j − pT Cq ≥ qn+1 [2∆(1 − ∆) − ∆] ≥ ∆/2 > ∆2 ,
which cannot happen since (p, q) is a ∆2 -equilibrium.
Case 4. Finally assume that qn+1 < 1 − 4∆. Then the row player’s payoff for row n+1 is eTn+1 Rq ≤
2∆(1 − 4∆), but row player’s payoffs for rows 1, . . . , n are ≥ (4∆)(1 − ∆). So, if pn+1 > 1/2 then Row
has incentive to deviate at least
eTn+1 Rq − pT Rq ≥ (1/2)[4∆(1 − ∆) − 2∆(1 − 4∆)] ≥ ∆/2 > ∆2 ,
which cannot happen since (p, q) is a ∆2 -equilibrium. Finally if pn+1 < 1/2 < 1 − 4∆ we apply the
analysis in case 2.
Thus any ∆2 -equilibrium must have ∆/2 ≤ p1 + · · · + pn ≤ 4∆ and ∆/2 ≤ q1 + · · · + qn ≤ 4∆, as
desired. This concludes the proof.
6 Stability in constant-sum games
It is interesting to note that for our algorithmic results for finding approximate equilibria, we do not
require knowing the stability parameters. If the game happens to be reasonably stable, then we get
improved running times over the Lipton et al. [28] guarantees; if this is not the case, then we fall back to
the Lipton et al. [28] guarantees. This is because algorithmically, we can simply try different support
sizes in increasing order and stop when we find strategies forming a (well-supported) ε-equilibrium. In
other words, given the desired approximation level ε, we can find an ε-approximate equilibrium in time
2 2 −1
nO((∆ /ε ) log(1+∆ ) log n) where ∆ is the smallest value greater than or equal to ε such that the game is
(ε, ∆)-perturbation stable. However, given a game, it might be interesting to know how stable it is. In this
direction, in this section we provide a characterization of stable constant-sum games and an algorithm for
computing the strong stability parameters of a given constant-sum game.
T HEORY OF C OMPUTING, Volume 13 (13), 2017, pp. 1–31 20
NASH E QUILIBRIA IN P ERTURBATION -S TABLE G AMES
Consider a constant-sum game defined by R and C. Let
P∗ = {p, ∃ q such that (p, q) is a Nash equilibrium}
and
Q∗ = {q, ∃ p such that (p, q) is a Nash equilibrium} .
We say that p is ∆-far from P∗ if the minimum distance between p and p0 ∈ P∗ is > ∆. Let vR and vC
be the unique values of the row and column player, respectively, in a Nash equilibrium [35]. Lemma 6.1
and Lemma 6.2 below characterize constant sum games satisfying approximation stability in terms of
properties of the space of mixed strategies for the row player and column player separately. Theorem 6.3
gives a polynomial time algorithm for determining the approximately best parameters for the strong
approximation stability property for a given game.
Lemma 6.1. We have:
(a) If pT Re j < vR − α for some j then (p, q) is not an α/2-Nash equilibrium for any q. Similarly, if
eTj Cq < vC − α for some j then (p, q) is not an α/2-Nash equilibrium for any p.
(b) If for any p that is ∆-far from P∗ there exists e j such that pT Re j < vR − α and for any q that is ∆-far
from Q∗ there exists e j such that eTj Cq < vC − α, then the game satisfies (α/2, ∆)-approximation-
stability.
Proof. Part (a): Consider p such that pT Re j < vR − α for some j, and let q be arbitrary. If pT Rq <
vR − α/2, then this is not an α/2-equilibrium since the row player could play its minimax optimal
strategy and get vR . On the other hand if pT Rq ≥ vR − α/2, then pT Cq ≤ vC + α/2, so this is also not
an α/2-equilibrium because pT Ce j > vC + α, so the column player has more than an α/2 incentive to
deviate. The argument for q such that eTj Cq < vC − α for some j is completely symmetric.
Part (b): We show that under this condition, any (p, q) that is ∆-far from all Nash equilibria cannot be
an α/2-equilibrium. Consider (p, q) that is ∆-far from all Nash equilibria. Then either p is ∆-far from P∗
or q is ∆-far from Q∗ .12 This implies that by assumption either there exists e j such that pT Re j < vR − α,
or there exists e j such that eTj Cq < vC − α. Therefore, by part (a), (p, q) cannot be an α/2-Nash
equilibrium.
Lemma 6.2. Let (p∗ , q∗ ) be a Nash equilibrium.
(a) If p satisfies min j pT Re j ≥ vR − α then (p, q∗ ) is an α Nash equilibrium. Similarly, if q satisfies
min j eTj Cq ≥ vC − α then (p∗ , q) is an α Nash equilibrium.
12 This follows from the well known interchangeability property of constant-sum games, meaning that given two Nash
equilibria points (p1 , q1 ) and (p2 , q2 ), the strategy pairs (p1 , q2 ) and (p2 , q1 ) are also Nash equilibria. To see why this
follows, note that if both p and q are close to P∗ and Q∗ , respectively, then there exist Nash equilibria (p1 , q1 ), (p2 , q2 )
such that d(p, p1 ) ≤ ∆ and d(q, q2 ) ≤ ∆. By interchangeability, we get that (p1 , q2 ) is a Nash equilibrium and we also have
d((p1 , q2 ), (p, q)) ≤ ∆.
T HEORY OF C OMPUTING, Volume 13 (13), 2017, pp. 1–31 21
M ARIA -F LORINA BALCAN AND M ARK B RAVERMAN
(b) If there exists p that is ∆-far from P∗ such that min j pT Re j ≥ vR − α or if there exists q that is ∆-far
from Q∗ such that min j eTj Cq ≥ vC − α, then the game cannot be (α, ∆)-approximation-stable.
Proof. Part (a): Consider p such that min j pT Re j ≥ vR − α. This implies pT Rq∗ ≥ vR − α. Moreover,
p0 T Rq∗ ≤ vR for any p0 since q∗ is minimax optimal for the column player. Therefore, the row player has at
most α-incentive to deviate from (p, q∗ ). Similarly, pT Cq∗ ≥ vC (since q∗ is minimax optimal) and since
min j pT Re j ≥ vR − α, we have max j pT Ce j ≤ vC + α. So the column player has at most α-incentive to
deviate from (p, q∗ ) as well. The argument for q such that min j eTj Cq ≥ vC − α is completely symmetric.
Part (b): Assume that there exists p that is ∆-far from P∗ such that min j pT Re j ≥ vR − α. By part (a),
we know (p, q∗ ) is an α-Nash equilibrium. Since this is ∆-far from the set of Nash equilibria, the game is
not (α, ∆)-approximation-stable. The case for q that is ∆-far from Q∗ such that min j eTj Cq ≥ vC − α is
completely symmetric.
If the game satisfies the strong approximation-stability condition, then we can efficiently compute
good approximations for the stability parameters. Specifically, we have the following result.
Theorem 6.3. Given any 0 < α < 1, we can use Algorithm 1 so that we determine whp (at least
1 − 1/poly(n)) a value ∆ such that the game satisfies the strong (α/2, 2∆)-approximation-stability
2
condition but not strong (α, ∆/2)-approximation-stability. The running time is polynomial nO(1/α ) .
Proof. We first find a minimax optimal solution (p∗ , q∗ ) and then in Step 2, a small support α-Nash
equilibrium (p0 , q0 ). Note that we can do Step 2 efficiently since we have (p∗ , q∗ ) and it succeeds with
probability 1 − 1/poly(n).
In Step 3 we find the maximum ∆ p such that for some p of distance ∆ p from p0 we have pT Re j ≥
vR − α for all j, and in Step 4 we find the maximum ∆q such that for some q of distance ∆q from q0 we
have eTj Cq ≥ vC − α for all j. So, for all (p, q) of distance greater than ∆ = max(∆ p , ∆q ) from (p0 , q0 ),
either pT Re j < vR − α for some j or eTj Cq < vC − α for some j. By Lemma 6.1(a), this implies that all
α/2-Nash equilibria are within distance ∆ of (p0 , q0 ). By Lemma 6.2(a), this also implies that there exists
an α-Nash equilibrium that is at distance at least ∆ from (p0 , q0 ); in particular, either (p, q∗ ) or (p∗ , q)
depending on whether the maximum ∆ occurred in Step 3 or Step 4, respectively.
In sum, in Steps 3 and 4 we find ∆ such that all α/2-Nash equilibria are within distance ∆ of (p0 , q0 )
and there exists an α-Nash equilibrium at distance ∆ from (p0 , q0 ). By triangle inequality, we obtain that
the game is (α/2, 2∆) stable and it is not (α, ∆/2) stable. In particular, since all α/2-Nash equilibria are
within distance ∆ of (p0 , q0 ), and this includes (p∗ , q∗ ), we get that all α/2-Nash equilibria are within
distance 2∆ of (p∗ , q∗ ), so the game is (α/2, 2∆) stable. We also know that there exists ( p̃, q̃) an α-Nash
equilibrium at distance ∆ from (p0 , q0 ) (which is also an α-Nash equilibrium), so by triangle inequality, at
least one of the two α-Nash equilibria ( p̃, q̃) and (p0 , q0 ) is at distance at least ∆/2 from (p∗ , q∗ ), so the
game is not (α, ∆/2) stable.
2
Note that the running time is polynomial since we we perform steps 3 and 4 at most 2O(log n/α ) =
2 2
nO(1/α ) times, so overall the running time is nO(1/α ) .
T HEORY OF C OMPUTING, Volume 13 (13), 2017, pp. 1–31 22
NASH E QUILIBRIA IN P ERTURBATION -S TABLE G AMES
Algorithm 1 Determining the strong stability parameters of a constant sum game.
Input: R, C, parameter α.
1. Solve for minimax optimal (p∗ , q∗ ) and compute minimax values vR and vC .
2. Apply the sampling procedure in [28] from (p∗ , q∗ ) to get (p0 , q0 ) with support of size O((log n)/α 2 )
that is an α-Nash.
3. For each partition Π p of the support of p0 into supp+ and supp− , solve the following LP:
maximize v(Π p ) = ∑ (pi − p0i ) + ∑ (p0i − pi ) + ∑ pi
i∈supp+ i∈supp− i∈{1,2,...,n}\supp(p0 )
s.t. pi ≥ p0i for all i ∈ supp+ ,
pi ≤ p0i for all i ∈ supp− ,
pi ≥ 0 for all i and ∑i pi = 1,
T
p Re j ≥ vR − α for all j.
Let ∆ p = maxΠ p v(Π p ).
4. For each partition Πq of the support of q0 into supp+ and supp− , solve the following LP:
maximize v(Πq ) = ∑ (qi − q0i ) + ∑ (q0i − qi ) + ∑ qi
i∈supp+ i∈supp− i∈{1,2,...,n}\supp(q0 )
s.t. qi ≥ q0i for all i ∈ supp+ ,
qi ≤ q0i for all i ∈ supp− ,
qi ≥ 0 for all i and ∑i qi = 1,
eTj Cq ≥ vC − α for all j.
Let ∆q = maxΠq v(Πq ).
Output: Radius ∆ = max(∆ p , ∆q ).
7 Discussion and open questions
Our main results show that for 0 ≤ ε ≤ ∆ ≤ 1, all n-action (ε, ∆)-perturbation-stable games with at most
2
nO((∆/ε) ) Nash equilibria must have at least one well-supported ε-equilibrium of support
∆ log(1 + ∆−1 )
2
O log n .
ε2
Our current proof crucially uses the limited number of Nash-equilibria. In particular, the key technical
component (Lemma 4.2) shows that if p∗ (or q∗ ) had a portion with substantial L1 norm and low L2 norm,
then there must exist a deviation from p∗ (or q∗ ) that is far from all equilibria and yet is a well-supported
T HEORY OF C OMPUTING, Volume 13 (13), 2017, pp. 1–31 23
M ARIA -F LORINA BALCAN AND M ARK B RAVERMAN
approximate Nash equilibrium, violating the stability condition. Proving the existence of such a deviation
is based on probabilistic argument and requires doing a union bound over all such equilibria. It would be
very interesting if the upper bound on the number of equilibria could be relaxed by using a more refined
way to guard against all the equilibria or by using a different technique.
Another interesting question is whether the games that are the result of reductions proving PPAD-
hardness are just (ε, 1)-perturbation stable or whether ∆ can be < 1. Our results imply that the games
used in the reduction of PPAD-hardness cannot be particularly stable, in particular they cannot satisfy
the t-uniform perturbation-stability condition since for games satisfying t-uniform perturbation stability
with t = poly(log(n)), our results imply that we can find 1/poly(n)-approximate equilibria in npoly(log(n))
time, i. e., achieve a fully quasi-polynomial-time approximation scheme (FQPTAS). This is especially
interesting because the results of [16] prove that it is PPAD-hard to find 1/poly(n)-approximate equilibria
in general games. Our results show that under the (widely believed) assumption that PPAD is not contained
in quasi-polynomial time [17], such uniformly stable games are inherently easier for computation of
approximate equilibria than general bimatrix games. It is an interesting open question to understand the
level of stability of the games used in PPAD hardness.
Additionally, we show that determining whether a given game satisfies strong approximation stability
(and computing approximations to the stability parameters) can be done in polynomial time for constant-
sum games. It is an open question whether this can be done efficiently for broader classes of games. For
example, it would be interesting to consider the class of bimatrix games satisfying the condition of mutual
concavity [27], or equivalently the class of strategically zero-sum games [30].
Acknowledgments
We thank the reviewers for their helpful comments. We thank Avrim Blum, Dick Lipton, Yishay Mansour,
Shanghua Teng, and Santosh Vempala for useful discussions. We also thank Vangelis Markakis for
pointing [29] to us.
A Standard facts
The following is the McDiarmid inequality (see [21]) we use in our proofs.
Theorem A.1. Let Y1 , . . . ,Yn be independent random variables taking values in some set A, and assume
that t : An → R satisfies:
sup |t(y1 , . . . , yn ) − t(y1 , . . . , yi−1 , yi , yi+1 , yn )| ≤ ci ,
y1 ,...,yn ∈A,yi ∈A
for all i, 1 ≤ i ≤ n. Then for all γ > 0 we have:
n
−2γ 2 / ∑ c2i
Pr {|t(Y1 , . . . ,Yn ) − E[t(Y1 , . . . ,Yn )]| ≥ γ} ≤ 2e i=1 .
Also, it is a well known fact that any pair of strategies that is sufficiently close to a Nash equilibrium
is a sufficiently good approximate Nash equilibrium.
Claim A.2. If (p, q) is α-close to a Nash equilibrium (p∗ , q∗ ) (i. e., if d((p, q), (p∗ , q∗ )) ≤ α), then (p, q)
is a 3α-Nash equilibrium.
T HEORY OF C OMPUTING, Volume 13 (13), 2017, pp. 1–31 24
NASH E QUILIBRIA IN P ERTURBATION -S TABLE G AMES
B Examples
We present here several examples of games satisfying our stability condition.
Example 1. A classic game from experimental economics is the public goods game which is defined is
as follows. We have two players and each can choose to play a number between 0 and n − 1 corresponding
to an amount of money to contribute. If the Row player contributes i dollars and the Column player
contributes j dollars, then each gets back 0.75(i + j). So the payoff to the Row player is 0.75(i + j) − i
and the payoff to the Column player is 0.75(i + j) − j, where i ∈ {0, 1, . . . , n − 1} and j ∈ {0, 1, . . . , n − 1}.
This has payoffs ranging from 0 up to 0.75(n − 1), so to scale to the range [0, 1] (as we do in this paper),
we multiply all the payoffs by 1/n. That is, if the Row player plays i and the Column player plays j
then the payoff to the Row player is R[i, j] = [0.75 j − 0.25i]/n and the payoff to the Column player is
C[i, j] = [0.75i − 0.25 j]/n.
We first claim that this game is (ε, 0)-stable under perturbations for all ε < 1/(8n). To see this, note
that without any perturbation, for any j and any i ≥ 1 we have eT0 Re j − eTi Re j = 0.25i/n ≥ 0.25/n. That
means that the Row player prefers playing action 0 compared to action i by 0.25i/n ≥ 0.25/n. So, in a
game R0 ,C0 that is an L∞ ε-perturbation of the original game we get: eT0 R0 e j − eTi R0 e j ≥ 0.25/n − 2ε > 0.
That means that in the perturbed game, the Row player still prefers playing action 0. This implies that the
only equilibrium in the perturbed game has the Row player playing action 0, and similarly the Column
player playing 0, so the only equilibrium is (0, 0).
We now claim that this game is not (ε, 0.99) stable for any ε > 1/(4n). To see this consider adding
ε to R[1, 0]. That is, if the Row player plays action 1 and the Column player plays action 0, then the
payoff to Row player is −0.25/n + ε > 0. Now, (1, 0) is a Nash equilibrium since this payoff is strictly
greater than R[i, 0] for any i 6= 1. In particular, R[0, 0] = 0 and R[i, 0] < 0 for all i ≥ 2. So, there is now a
Nash equilibrium (actually the unique Nash equilibrium) at variation distance 1 from the original Nash
equilibrium.
Example 2. We present here a variant of the identical interest game. Both players have n available
actions. The first action is to stay home, and the other actions correspond to n − 1 different possible
meeting locations. If a player chooses action 1 (stay home), his payoff is 1/2 no matter what the other
player is doing. If the player chooses to go out to a meeting location, his payoff is 1 if the other player is
there as well and it is 0 otherwise. Formally, if the Row player plays i and the Column player plays j then
the payoff to the Row player is
R[1, j] = 1/2 for all j, R[i, i] = 1 for all i > 1, R[i, j] = 0 for i > 1, j 6= i.
and the payoff to the Column player is
C[i, 1] = 1/2, C[ j, j] = 1 for j > 1, C[i, j] = 0 for j > 1, i 6= j.
We claim that this game is well supported (ε, 2ε)-stable for all ε < 1/6, so it is 2-uniformly stable.
Note that eT1 Rq = 1/2 and eTi Rq = qi for i > 1. Similarly, pT Ce1 = 1/2 and pT Cei = pi for i > 1.
Note that if (p, q) is an well supported ε-Nash equilibrium and if qi < 1/2 − ε for i > 1 then both pi = 0
and qi = 0. This follows immediately since eT1 Rq = 1/2 and eTi Rq = qi for i > 1, so pi must equal 0 on
T HEORY OF C OMPUTING, Volume 13 (13), 2017, pp. 1–31 25
M ARIA -F LORINA BALCAN AND M ARK B RAVERMAN
any action whose expected payoff is < 1/2 − ε. Since pi = 0, qi must equal 0 as well in order to be
well-supported. Also note that if (p, q) is an well supported ε-Nash equilibrium and if qi > 1/2 + ε for
i > 0 then both pi = 1 and qi = 1. If qi > 1/2 + ε we have eTi Rq = 1/2 + ε and since eTj Rq ≤ 1/2 for
j 6= i we must have pi = 1. This in turn implies qi = 1. Similarly, we can show the same for the row
player as well.
These imply that the well supported ε-Nash equilibria that are not already Nash equilibria must
satisfy: for any action i > 1, i ∈ supp(q), we have 1/2 − ε ≤ qi ≤ 1/2 + ε and 1/2 − ε ≤ pi ≤ 1/2 + ε.
Similarly, for any action i > 1, i ∈ supp(p), we have 1/2 − ε ≤ qi ≤ 1/2 + ε and 1/2 − ε ≤ pi ≤ 1/2 + ε.
We have two cases. The first one is if there is exactly one action i > 1 in supp(q). In that case, (p, q)
has distance at most ε from the Nash equilibrium (1/2e0 + 1/2ei , 1/2e0 + 1/2ei ). The second one is if
there are two such actions i, j > 0 in supp(q). In that case, (p, q) has distance at most 2ε from the Nash
equilibrium (1/2ei + 1/2e j , 1/2ei + 1/2e j ), as desired.
Example 3. To relate to other conditions considered in the literature, we point out here that perturbation
stability is incomparable to the class of constant-rank games studied, e. g., in [25, 1]. One can generate
n-by-n matrices R and C that are highly stable and yet where R +C has large rank (rank n), and one can
also generate zero-sum games that are very unstable under perturbations.
In the first direction, consider any pair of n-by-n matrices R and C such that:
• The first row of R is all 1s.
• The first columns of C is all 1s.
• All other entries are in the range [0, 1/2).
Such matrices are (1/4, 0)-stable under perturbations, since under such perturbations, the only Nash
equilibrium is still p = q = e1 . Moreover, if the entries in [0, 1/2) are filled in randomly (or even filled in
arbitrarily but with infinitesimal perturbations added), we will have rank(R +C) = n with probability 1.
In the other direction, there are zero-sum games that are very unstable under perturbations. For
example, let δ > 0 be a small value and consider
1 1−δ 0 0 1 − 2δ 1 − δ
R = −C = ; R = −C = .
1 − δ 1 − 2δ 1−δ 1
Here, (R0 ,C0 ) is a 2δ -perturbation of (R,C), and yet the equilibria are far apart. In particular, the unique
Nash equilibrium of (R,C) is (e1 , e2 ), yet the unique Nash equilibrium of (R0 ,C0 ) is (e2 , e1 ).
C Range of parameters
Lemma C.1. Assume that the game G satisfies the (ε, ∆)-approximation-stability and that the union of
all ∆-balls around all Nash equilibria do not cover the whole space. Then we must have 3∆ ≥ ε.
Proof. Since the union of all ∆-balls around all Nash equilibria do not cover the whole space, we must
have a (p, q) that is at distance exactly ∆ from some fixed Nash equilibrium and that is ∆-far from all the
other Nash equilibria. By Claim A.2 we also have that this is a 3∆-Nash equilibrium. This then implies
the desired result.
T HEORY OF C OMPUTING, Volume 13 (13), 2017, pp. 1–31 26
NASH E QUILIBRIA IN P ERTURBATION -S TABLE G AMES
Lemma C.2. Assume that the bimatrix game G specified by R and C has a non-pure Nash equilibrium.
(a) If G satisfies the strong well-supported (ε, ∆)-approximation-stability condition, then we must have
∆ ≥ ε/4.
(b) If G satisfies the strong (ε, ∆)-perturbation-stability condition, then we must have ∆ ≥ ε/8.
Proof. Assume G satisfies the strong well-supported (ε, ∆)-approximation-stability condition. By defini-
tion, there exists a Nash equilibrium (p∗ , q∗ ) such that any well supported ε-equilibrium is ∆-close to
(p∗ , q∗ ). Let (p, q) be an arbitrary non-pure Nash equilibrium of G and assume without loss of generality
that p is a mixed strategy. Consider an α internal deviation of the row player, i. e., consider p0 with
supp(p0 ) ⊆ supp(p) such that d(p, p0 ) = α. Since supp(p0 ) ⊆ supp(p) we have p0T Rq = pT Rq. Since
(p, q) is a Nash equilibrium we have pT Ce j = pT Cq ≡ vC for all j ∈ supp(q) and pT Ce j ≤ vC for all
/ supp(q). Since d(p, p0 ) = α we have
j∈
|p0T Ce j − pT Ce j | ≤ |(p0 − p)T Ce j | ≤ α ,
for all j, so p0T Ce j ≥ vC − α, for all j ∈ supp(q) and p0T Ce j ≤ vC + α, for all j ∈ / supp(q). Thus (p0 , q)
0
is a well supported 2α-Nash equilibrium. By construction, we have d((p , q), (p, q)) = α. Since d is a
metric, by the triangle inequality, we get that at least one of the pairs (p0 , q) and (p, q) is at least α/2 far
from (p∗ , q∗ ); however they are both 2α well supported Nash equilibria. This implies that we must have
∆ ≥ ε/4, as desired. By Theorem 3.3, we immediately get (b) as well.
References
[1] B HARAT A DSUL , J UGAL G ARG , RUTA M EHTA , AND M ILIND S OHONI: Rank-1 bimatrix games:
A homeomorphism and a polynomial time algorithm. In Proc. 43rd STOC, pp. 195–204. ACM
Press, 2011. [doi:10.1145/1993636.1993664, arXiv:1010.3083] 5, 26
[2] M ICHELE AGHASSI AND D IMITRIS B ERTSIMAS: Robust game theory. Math. Program., 107(1-
2):231–273, 2006. [doi:10.1007/s10107-005-0686-0] 5
[3] H ARIS A NGELIDAKIS , KONSTANTIN M AKARYCHEV, AND Y URY M AKARYCHEV: Algorithms
for stable and perturbation-resilient problems. In Proc. 49th STOC, pp. 438–451. ACM Press, 2017.
[doi:10.1145/3055399.3055487] 5
[4] P RANJAL AWASTHI AND M ARIA -F LORINA BALCAN: Center based clustering: A foundational
perspective. In H ENNIG , M EILA , M URTAGH , AND ROCCI, editors, Handbook of Cluster Analysis.
CRC Press, 2015. Available from CMU. 5
[5] P RANJAL AWASTHI , M ARIA -F LORINA BALCAN , AVRIM B LUM , O R S HEFFET, AND S ANTOSH
V EMPALA: On Nash-equilibria of approximation-stable games. In Proc. 3rd Internat. Symp.
Algorithmic Game Theory (SAGT’10), pp. 78–89, 2010. [doi:10.1007/978-3-642-16170-4_8] 4, 5,
8, 9, 10
T HEORY OF C OMPUTING, Volume 13 (13), 2017, pp. 1–31 27
M ARIA -F LORINA BALCAN AND M ARK B RAVERMAN
[6] P RANJAL AWASTHI , M ARIA -F LORINA BALCAN , AVRIM B LUM , O R S HEFFET, AND S ANTOSH
V EMPALA: On Nash-equilibria of approximation-stable games. Current Science J., 103(9):1014–
1020, 2012. Available at JSTOR. Preliminary version in SAGT’10. 4, 5
[7] P RANJAL AWASTHI , AVRIM B LUM , AND O R S HEFFET: Center-based clustering under pertur-
bation stability. Inform. Process. Lett., 112(1-2):49–54, 2012. [doi:10.1016/j.ipl.2011.10.006,
arXiv:1009.3594] 5
[8] M ARIA -F LORINA BALCAN , AVRIM B LUM , AND A NUPAM G UPTA: Approximate clustering
without the approximation. In Proc. 20th Ann. ACM-SIAM Symp. on Discrete Algorithms (SODA’09),
pp. 1068–1077. ACM Press, 2009. [doi:10.1137/1.9781611973068.116] 7
[9] M ARIA -F LORINA BALCAN , AVRIM B LUM , AND A NUPAM G UPTA: Clustering under approxima-
tion stability. J. ACM, 60(2):8:1–8:34, 2013. [doi:10.1145/2450142.2450144] 7
[10] M ARIA -F LORINA BALCAN , N IKA H AGHTALAB , AND C OLIN W HITE: k-center clustering
under perturbation resilience. In Proc. 43rd Internat. Colloq. on Automata, Languages and
Programming (ICALP’16), volume 55 of LIPIcs, pp. 68:1–68:14. Schloss Dagstuhl, 2016.
[doi:10.4230/LIPIcs.ICALP.2016.68, arXiv:1505.03924] 5
[11] M ARIA -F LORINA BALCAN AND Y INGYU L IANG: Clustering under perturbation resilience. SIAM
J. Comput., 45(1):102–155, 2016. Preliminary version in ICALP’12. [doi:10.1137/140981575,
arXiv:1112.0826] 5
[12] I MRE B ÁRÁNY, S ANTOSH V EMPALA , AND A DRIAN V ETTA: Nash equilibria in random
games. Random Struct. Algorithms, 31(4):391–405, 2007. Preliminary version in FOCS’05.
[doi:10.1002/rsa.20199] 5
[13] YONATAN B ILU AND NATHAN L INIAL: Are stable instances easy? Combinatorics,
Probab. Comput., 21(5):643–660, 2012. Preliminary version appeared in ICS 2010.
[doi:10.1017/S0963548312000193, arXiv:0906.3162] 5
[14] H ARTWIG B OSSE , JAROSLAW B YRKA , AND E VANGELOS M ARKAKIS: New algorithms for
approximate Nash equilibria in bimatrix games. Theor. Comput. Sci., 411(1):164–173, 2010.
Preliminary version in WINE’07. [doi:10.1016/j.tcs.2009.09.023] 2
[15] X I C HEN AND X IAOTIE D ENG: Settling the complexity of two-player Nash equilibrium. In
Proc. 47th FOCS, pp. 261–272. IEEE Comp. Soc. Press, 2006. [doi:10.1109/FOCS.2006.69,
arXiv:0704.1678] 2
[16] X I C HEN , X IAOTIE D ENG , AND S HANG -H UA T ENG: Settling the complexity of computing
two-player Nash equilibria. J. ACM, 56(3):14:1–14:57, 2009. [doi:10.1145/1516512.1516516,
arXiv:0704.1678] 2, 3, 16, 24
[17] C ONSTANTINOS DASKALAKIS: On the complexity of approximating a Nash equilib-
rium. ACM Trans. Algorithms, 9(3):23:1–23:35, 2013. Preliminary version in SODA’11.
[doi:10.1145/2483699.2483703] 3, 16, 24
T HEORY OF C OMPUTING, Volume 13 (13), 2017, pp. 1–31 28
NASH E QUILIBRIA IN P ERTURBATION -S TABLE G AMES
[18] C ONSTANTINOS DASKALAKIS , PAUL W. G OLDBERG , AND C HRISTOS H. PAPADIMITRIOU: The
complexity of computing a Nash equilibrium. SIAM J. Comput., 39(1):195–259, 2009. Preliminary
version in STOC’06. [doi:10.1137/070699652] 2
[19] C ONSTANTINOS DASKALAKIS , A RANYAK M EHTA , AND C HRISTOS H. PAPADIMITRIOU:
Progress in approximate Nash equilibria. In Proc. 8th ACM Conf. on Electronic Commerce (EC’07),
pp. 355–358, 2007. [doi:10.1145/1250910.1250962] 2
[20] C ONSTANTINOS DASKALAKIS , A RANYAK M EHTA , AND C HRISTOS H. PAPADIMITRIOU: A note
on approximate Nash equilibria. Theoret. Comput. Sci., 410(17):1581–1588, 2009. Preliminary
version in WINE’06. [doi:10.1016/j.tcs.2008.12.031] 2
[21] L UC D EVROYE , L ÁSZLÓ G Y ŐRFI , AND G ÁBOR L UGOSI: A Probabilistic Theory of Pattern
Recognition. Springer, 1996. [doi:10.1007/978-1-4612-0711-5] 24
[22] S TEVEN N. D URLAUF AND L AWRENCE E. B LUME: Game Theory. Palgrave Macmillan, 2008.
[doi:10.1057/9780230280847] 3, 16
[23] T OMÁS F EDER , H AMID NAZERZADEH , AND A MIN S ABERI: Approximating Nash equilibria
using small-support strategies. In Proc. 8th ACM Conf. on Electronic Commerce (EC’07), pp.
352–354. ACM, 2007. [doi:10.1145/1250910.1250961] 2
[24] R ISHI G UPTA , T IM ROUGHGARDEN , AND C. S ESHADHRI: Decompositions of triangle-
dense graphs. SIAM J. Comput., 45(2):197–215, 2016. Preliminary version in ITCS’14.
[doi:10.1137/140955331, arXiv:1309.7440] 7
[25] R AVI K ANNAN AND T HORSTEN T HEOBALD: Games of fixed rank: A hierarchy of bimatrix games.
Economic Theory, 42(1):157–173, 2010. Preliminary version in SODA’07. [doi:10.1007/s00199-
009-0436-2, arXiv:cs/0511021] 5, 26
[26] S PYROS C. KONTOGIANNIS , PANAGIOTA N. PANAGOPOULOU , AND PAUL G. S PIRAKIS: Poly-
nomial algorithms for approximating Nash equilibria of bimatrix games. Theor. Comput. Sci.,
410(17):1599–1606, 2009. Preliminary version in WINE’06. [doi:10.1016/j.tcs.2008.12.033] 2
[27] S PYROS C. KONTOGIANNIS AND PAUL G. S PIRAKIS: On mutual concavity and strategically-zero-
sum bimatrix games. Theor. Comput. Sci., 432:64–76, 2012. Preliminary version in APPROX’10.
[doi:10.1016/j.tcs.2012.01.016] 24
[28] R ICHARD J. L IPTON , E VANGELOS M ARKAKIS , AND A RANYAK M EHTA: Playing large games
using simple strategies. In Proc. 4th ACM Conf. on Electronic Commerce (EC’03), pp. 36–41. ACM,
2003. [doi:10.1145/779928.779933] 2, 3, 4, 9, 10, 14, 15, 20, 23
[29] R ICHARD J. L IPTON , E VANGELOS M ARKAKIS , AND A RANYAK M EHTA: On stability properties
of economic solution concepts. Manuscript, 2006. 5, 6, 24
[30] H ERVÉ M OULIN AND J EAN -P HILIPPE V IAL: Strategically zero-sum games: The class of games
whose completely mixed equilibria cannot be improved upon. Internat. J. Game Theory, 7(3–4):201–
221, 1978. [doi:10.1007/BF01769190] 24
T HEORY OF C OMPUTING, Volume 13 (13), 2017, pp. 1–31 29
M ARIA -F LORINA BALCAN AND M ARK B RAVERMAN
[31] J OHN F. N ASH: Non-cooperative games. Ann. of Math., 54(2):286–295, 1951.
[doi:10.2307/1969529] 2, 6
[32] AVIAD RUBINSTEIN: Settling the complexity of computing approximate two-player Nash
equilibria. ACM SIGecom Exchanges, 15(2):45–49, 2017. Preliminary version in FOCS’16.
[doi:10.1145/3055589.3055596, arXiv:1606.04550] 2
[33] H ARALAMPOS T SAKNAKIS AND PAUL G. S PIRAKIS: An optimization approach for approximate
Nash equilibria. Internet Mathematics, 5(4):365–382, 2007. Preliminary version in WINE’07.
[doi:10.1080/15427951.2008.10129172] 2
[34] KONSTANTIN VOEVODSKI , M ARIA -F LORINA BALCAN , H EIKO R ÖGLIN , S HANG -H UA T ENG ,
AND Y U X IA : Efficient clustering with limited distance information. In Proc. 26th Ann. Conf. on
Uncertainty in Artificial Intelligence (UAI’10), pp. 632–640. AUAI Press, 2010. Available from
AUAI Press. [arXiv:1408.2045] 7
[35] J OHN VON N EUMANN AND O SKAR M ORGENSTERN: Theory of Games and
Economic Behavior (60th-Anniversary Edition). Princeton Univ. Press, 2007.
[http://press.princeton.edu/titles/7802.html] 2, 21
AUTHORS
Maria-Florina Balcan
Associate professor
School of Computer Science
Carnegie Mellon University, Pittsburgh, PA
ninamf cs cmu edu
http://www.cs.cmu.edu/~ninamf
Mark Braverman
Professor
Department of Computer Science
Princeton University, Princeton, NJ
mbraverm cs princeton edu
http://www.cs.princeton.edu/~mbraverm
T HEORY OF C OMPUTING, Volume 13 (13), 2017, pp. 1–31 30
NASH E QUILIBRIA IN P ERTURBATION -S TABLE G AMES
ABOUT THE AUTHORS
M ARIA -F LORINA BALCAN is an Associate Professor in the School of Computer Science
at Carnegie Mellon University. Her main research interests are machine learning, com-
putational aspects in economics and game theory, and algorithms. Her honors include
the CMU SCS Distinguished Dissertation Award, an NSF CAREER Award, a Microsoft
Faculty Research Fellowship, a Sloan Research Fellowship, and several paper awards.
She has held several leadership positions including being a Program Committee Co-chair
for COLT 2014, a Program Committee Co-chair for ICML 2016, and a board member of
the International Machine Learning Society.
M ARK B RAVERMAN received his Ph. D. from the University of Toronto in 2008 under
the supervision of Stephen Cook. He is currently a Professor of Computer Science at
Princeton University. He is interested in most aspects of theoretical computer science—
particularly in its connections to other disciplines such as information theory, game
theory, and mechanism design. His work has been recognized by an NSF CAREER
Award, a Packard Fellowship in Science and Engineering, and a Presburger Award in
Theoretical Computer Science.
T HEORY OF C OMPUTING, Volume 13 (13), 2017, pp. 1–31 31