Communications - February 2009

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, Shoham²² 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