DoI: 10.1145/1461928.1461951
The Complexity of Computing
a Nash Equilibrium
By Constantinos Daskalakis, Paul W. Goldberg, and Christos H. Papadimitriou
abstract
How long does it take until economic agents converge to an
equilibrium? By studying the complexity of the problem of
computing a mixed Nash equilibrium in a game, we provide
evidence that there are games in which convergence to such an
equilibrium takes prohibitively long. Traditionally, computational problems fall into two classes: those that have a polynomial-time algorithm and those that are nP-hard. However, the
concept of NP-hardness cannot be applied to the rare problems
where “every instance has a solution”—for example, in the case
of games Nash’s theorem asserts that every game has a mixed
equilibrium (now known as the Nash equilibrium, in honor of
that result). We show that finding a Nash equilibrium is complete for a class of problems called PPaD, containing several
other known hard problems; all problems in PPaD share the
same style of proof that every instance has a solution.
1. IntRoDuCtIon
In a recent CACM article, Shoham22 reminds us of the long
relationship between Game Theory and Computer Science,
going back to John von Neumann at Princeton in the 1940s,
and how this connection became stronger and more crucial
in the past decade due to the advent of the Internet: Strategic
behavior became relevant to the design of computer systems,
while much economic activity now takes place on computational platforms.
Game Theory is about the strategic behavior of rational
agents. It studies games, thought experiments modeling various situations of conflict. One commonly studied model aims
to capture two players interacting in a single round. For example, the well-known school yard game of rock–paper–scissors
can be described by the mathematical game shown in Figure
1. There are two players, one choosing a row and one choosing
a column; the choices of a player are his/her actions. Once the
two players choose, simultaneously, an action, they receive
the corresponding payoffs shown in the table: The first number denotes the payoff of Row, the second that of Column.
Notice that each of these pairs of numbers sum to zero in the
case of Figure 1; such games are called zero-sum games. Three
other well-known games, called chicken, prisoner’s dilemma,
and penalty shot game, respectively, are shown in Figure 2; the
penalty shot game is zero-sum, but the other two are not. All
these games have two players; Game Theory studies games
with many players, but these are harder to display.a
a
How about games such as chess? We can capture this and other similar
games in the present framework by considering two players, Black and
White, each with a huge action set containing all possible maps from positions to moves; but of course, such formalism is not very helpful for analyzing chess and similar games.
The purpose of games is to help us understand economic
behavior by predicting how players will act in each particular game. The predictions game theorists make about player
behavior are called equilibria. One such prediction is the
pure Nash equilibrium: Each player chooses an action that is
a “best response” to the other player’s choice—i.e., it is the
highest payoff, for the player, in the line, row or column, chosen by the other player. In the game of chicken in Figure 2,
a pure Nash equilibrium is when one player chooses “dare”
and the other chooses “chicken.” In the prisoner’s dilemma,
the only pure Nash equilibrium is when both players choose
“defect.”
Unfortunately, not all games have a pure Nash equilibrium. For example, it is easy to see that the rock–
paper–scissors game in Figure 1 has none. This lack of
universality is an important defect of the concept of pure
Nash equilibrium as a predictor of behavior. But the rock–
paper–scissors game does have a more sophisticated kind
of equilibrium, called a mixed Nash equilibrium—and in
fact one that is familiar to all who have played this game:
both players pick an action uniformly at random. That is, a
mixed Nash equilibrium is a probabilistic distribution on
the set of actions of each player. Each of the distributions
should have the property that it is a best response to the
other distributions; this means that each action assigned
positive probability is among the actions that are best
responses, in expectation, to the distribution(s) chosen by
the opponent(s).
In 1950, John Nash proved that all games have a mixed
Nash equilibrium. That is, in any game, distributions over
19
the players’ actions exist such that each is a best response
to what everybody else is doing. This important—and far
from obvious—universality theorem established the mixed
Nash equilibrium as Game Theory’s central equilibrium
concept, the baseline and gold standard against which all
figure 1: Rock–paper–scissors.
rock
paper
scissors
rock
(0, 0)
( 1, - 1)
(- 1, 1)
paper
(- 1, 1)
(0, 0)
( 1, - 1)
scissors
( 1, - 1)
(- 1, 1)
(0, 0)
A previous version of this paper appeared in the ACM 2006
Proceedings of the Symposium on Theory of Computing.
febrUary 2009 | vol. 52 | no. 2 | CommunICatIons of the aCm
89