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 n2n numbers—
the utility of each player for each of the 2n strategy choices of
the n players. But our game has a special structure (called a
graphical game, see Kearns et al.
15): 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
7 was preceded by a number of important papers
that developed the ideas outlined here. Scarf’s algorithm21
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
algorithm17 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.
20
Three decades ago, Bubelis1 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 Deng2, 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.
3 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 Yannakakis9 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