of F away from the centers of the cubelets shall be gotten by
interpolation with the closest grid points.
Each grid point x shall receive one of four “colors” {0,
1, 2, 3}, that represent the value of the three-dimensional
displacement vector F(x) – x. The four possible vectors can
be chosen to point away from each other such that F(x) – x
can only be approximately zero in the vicinity of all the four
colors.
We are now ready to fit G itself into the above framework. Each of the 2n vertices of G shall correspond with two
special sites in the cube, one of which lies along the bottom left-hand edge in Figure 9 and the other one along the
top left edge. (We use locations that are easy to compute
from the identity of a vertex of G.) While most other grid
points in the cube get color 0 from F, at all the special sites
a particular configuration of the other colors appears. If G
has an edge from node u to node v, then F shall also color
a long sequence of points between the corresponding sites
in the cube (as shown in Figure 9), so as to connect them
zy
with sequences of grid points that get colors 1, 2, and 3.
The precise arrangement of these colors can be chosen to
x
be easy to compute (using the circuits P and S that define
G) and such that all four colors are adjacent to each other (an
approximate fixed point) only at sites that correspond to an
“end of the line” of G.
Having shown earlier that Brouwer is in PPaD, we establish the following:
Theorem 4. 1. Brouwer is PPaD-complete.
figure 9: embedding the END OF THE LINE graph in a cube. the embedding is used to define a continuous function F, whose approximate
fixed points correspond to the unbalanced nodes of the END OF THE LINE
graph.
u
2
u�
2
u
5
u
4
u
6
n
1
n�
1
u
3
u
1
u�
1
4. 2. from BROUWER to nASH
The PPaD-complete class of Brouwer functions that we identified above have the property that their function F can be
efficiently computed using arithmetic circuits that are built
up using a small repertoire of standard operators such as
addition, multiplication, and comparison. These circuits
can be written down as a “data flow graph,” with one of
these operators at each node. In order to transform this into
a game whose Nash equilibria correspond to (approximate)
fixed points of the Brouwer function, we introduce players
for every node on this data flow graph.
games that Do arithmetic: The idea is to simulate each
arithmetic gate in the circuit by a game, and then compose
the games to get the effect of composing the gates. The
whole circuit is represented by a game with many players,
each of whom “holds” a value that is computed by the circuit. We give each player two actions, “stop” and “go.” To
simulate, say, multiplication of two values, we can choose
payoffs for three players x, y, and z such that, in any Nash
equilibrium, the probability that z (representing the output of the multiplication) will “go” is equal to the product
of the probabilities that x and y will “go.” The resulting
“multiplication gadget” (see Figure 10) has a fourth player
w who mediates between x, y, and z. The directed edges
show the direct dependencies among the players’ payoffs.
Elsewhere in the game, z may input his value into other
related gadgets.
Here is how we define payoffs to induce the players to
implement multiplication. Let X, Y, Z, and W denote the
mixed strategies (“go” probabilities) of x, y, z, and w. We pay
figure 10: the players of the multiplication game. the graph shows
which players affect other players’ payoffs.
x
w
z
y
w the amount X · Y for choosing strategy stop and Z for
choosing go. We also pay z to play the opposite from player
w. It is not hard to check that in any Nash equilibrium of the
game thus defined, it must be the case that Z = X · Y. (For
example, if Z > X · Y, then w would prefer strategy go, and
therefore z would prefer stop, which would make Z = 0, and
would violate the assumption Z > X · Y.) Hence, the rules of
the game induce the players to implement multiplication in
the choice of their mixed strategies.
By choosing different sets of payoffs, we could ensure that
Z = X + Y or It is a little more challenging to simulate
the comparison of two real values, which also is needed to
simulate the Brouwer function. Below we discuss that issue
in more detail.
computing a brouwer function with games: Suppose we
have a Brouwer function F defined on the unit cube. Include
three players x , x , and x whose “go” probabilities repre-
12
3
sent a point x in the cube. Use additional players to compute
febrUary 2009 | vol. 52 | no. 2 | CommunICatIons of the aCm
95