F(x) via gadgets as described above. Eventually, we can end
up with three players y , y , and y whose “go” probabilities
12 3
represent F(x). Finally, we can give payoffs to x , x , and x
12 3
that ensure that in any Nash equilibrium, their probabilities
agree with y , y , and y . Then, in any Nash equilibrium, these
12 3
probabilities must be a fixed point of F.
the brittle comparator Problem: There’s just one catch: our
comparator gadget, whose purpose is to compare its inputs
and output a binary signal according to the outcome of the
comparison, is “brittle” in that if the inputs are equal then
it outputs anything. This is inherent, because one can show
that, if a nonbrittle comparator gadget existed, then we
could construct a game that has no Nash equilibria, con-
tradicting Nash’s theorem. With brittle comparators, our
computation of F is faulty on inputs that cause the circuit to
make a comparison of equal values. We solve this problem
by computing the Brouwer function at a grid of many points
near the point of interest, and averaging the results, which
makes the computation “robust,” but introduces a small
error in the computation of F. Therefore, the construction
described above approximately works, and the three special
players of the game have to play an approximate fixed point
at equilibrium.
the final Step: three Players: The game thus constructed
has many players (the number depends mainly on how com-
plicated the program for computing the function F was), and
two strategies for each player. This presents a problem: To
represent such a game with n players we need n2ⁿ numbers—
the utility of each player for each of the 2ⁿ strategy choices of
the n players. But our game has a special structure (called a
graphical game, see Kearns et al. ¹⁵): The players are vertices of
a graph (essentially the data flow graph of F), and the utility
of each player depends only on the actions of its neighbors.

The final step in the reduction is to simulate this game by a three-player normal form game—this establishes that Nash is PPaD-complete even in the case of three players. This is accomplished as follows: We color the players (nodes of the graph) by three colors, say red, blue, and yellow, so that no two players who play together, or two players who are involved in a game with the same third player, have the same color (it takes some tweaking and argument to make sure the nodes can be so colored). The idea is now to have three “ lawyers,” the red lawyer, the blue lawyer, and the yellow lawyer, each represent all nodes with their color, in a game involving only the lawyers. A lawyer representing m nodes has 2m actions, and his mixed strategy (a probability distribution over the 2m actions) can be used to encode the simpler stop/ go strategies of the m nodes. Since no two adjacent nodes are colored the same color, the lawyers can represent their nodes without a “conflict of interest,” and so a mixed Nash equilibrium of the lawyers’ game will correspond to a mixed Nash equilibrium of the original graphical game.

But there is a problem: We need each of the “lawyers” to allocate equal amounts of probability to their customers; however, with the construction so far, it may be best for a lawyer to allocate more probability mass to his more “lucrative” customers. We take care of this last difficulty by having the lawyers play, on the side and for high stakes, a

96 CommunICatIons of the aCm | febrUary 2009 | vol. 52 | no. 2

generalization of the rock–paper–scissors game of Figure 1, one that forces them to balance the probability mass allocated to the nodes of the graph. This completes the reduction from graphical games to three-player games, and the proof.

5. ReLateD teChnICaL ContRIButIons

Our paper ⁷ was preceded by a number of important papers that developed the ideas outlined here. Scarf’s algorithm²¹ was proposed as a general method for finding approximate fixed points, more efficiently than brute force. It essentially works by following the line in the associated end of the line graph described in Section 3. 1. The Lemke–Howson algorithm¹⁷ computes a Nash equilibrium for two-player games by following a similar end of the line path. The similarity of these algorithms and the type of parity argument used in showing that they work inspired the definition of PPaD in Papadimitriou. ²⁰

Three decades ago, Bubelis¹ considered reductions among games and showed how to transform any k-player game to a three-player game (for k > 3) in such a way that given any solution of the three-player game, a solution of the k-player game can be reconstructed with simple algebraic operations. While his main interest was in the algebraic properties of solutions, his reduction is computationally efficient. Our work implies this result, but our reduction is done via the use of graphical games, which are critical in establishing our PPaD-completeness result.

Only a few months after we announced our result, Chen and Deng^{2, 3} made the following clever, and surprising, observation. The graphical games resulting from our construction are not using the multiplication operation (except for multiplication by a constant), and therefore can even be simulated by a two-player game, leading to an improvement of our hardness result from three- to two-player games. This result was unexpected, one reason being that the probabilities that arise in a two-player Nash equilibrium are always rational numbers, which is not the case for games with three or more players.

Our results imply that finding an e -Nash equilibrium is PPaD-complete, if e is inversely proportional to an exponential function of the game size. Chen et al. ³ extended this result to the case where e is inversely proportional to a polynomial in the game size. This rules out a fully polynomial-time approximation scheme for computing approximate equilibria.

Finally, in this paper, we have focused on the complexity of computing an approximate Nash equilibrium. Etessami and Yannakakis⁹ develop a very interesting complexity theory of the problem of computing the exact equilibrium (or other fixed points), a problem that is important in applications outside Game Theory, such as Program Verification.

6. ConCLusIon anD futuRe WoRK

Our hardness result for computing a Nash equilibrium raises concerns about the credibility of the mixed Nash equilibrium as a general-purpose framework for behavior