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 2ⁿ 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