Slide 1Slide 2The PLANLast LectureThis LectureSlide 6Embedding of PPAD graph into [0,1]3Reducing to 3-d SpernerBoundary ColoringColoring of the RestColoring around LThe Beginning of L at 0nColor TwistingColor TwistingProof of Claim of Previous SlideFinishing the ReductionSlide 17Slide 18(Special) SPERNER BROUWER(Special) SPERNER BROUWER(Special) SPERNER BROUWERSlide 22Slide 23(Special) BROUWER NASH(Special) BROUWER NASH(Special) BROUWER NASHCan games perform conventional binary computation?Can these games perform binary computation?A possible PPAD-hardness reductionCan games that do real arithmetic?6.896: Topics in Algorithmic Game TheoryLecture 9Constantinos DaskalakisLast Time…The PLAN...0nGeneric PPADEmbed PPAD graph in [0,1]33D-SPERNER p.w. linear BROUWERmulti-playerNASH4-playerNASH3-playerNASH2-playerNASH[Pap ’94][DGP ’05][DGP ’05][DGP ’05][DGP ’05][DGP ’05][DP ’05][CD’05][CD’06]DGP = Daskalakis, Goldberg, PapadimitriouCD = Chen, DengLast Lecture...0nGeneric PPADEmbed PPAD graph in [0,1]33D-SPERNER p.w. linear BROUWERmulti-playerNASH4-playerNASH3-playerNASH2-playerNASH[Pap ’94][DGP ’05][DGP ’05][DGP ’05][DGP ’05][DGP ’05][DP ’05][CD’05][CD’06]DGP = Daskalakis, Goldberg, PapadimitriouCD = Chen, DengThis Lecture...0nGeneric PPADEmbed PPAD graph in [0,1]33D-SPERNER p.w. linear BROUWERmulti-playerNASH4-playerNASH3-playerNASH2-playerNASH[Pap ’94][DGP ’05][DGP ’05][DGP ’05][DGP ’05][DGP ’05][DP ’05][CD’05][CD’06]DGP = Daskalakis, Goldberg, PapadimitriouCD = Chen, DengReview of Last Lecture…PPAD-completeness of SPERNER...0nGeneric PPADpair of segments (the main and the auxiliary segment); Embedding of PPAD graph into [0,1]3Non-Isolated Nodeorthonormal path connecting the end of the auxiliary segment of u with the beginning of main segment of vEdge between and connected by an orthonormal line.Reducing to 3-d SpernerInstead of coloring vertices of the triangulation (the points of the cube whose coordinates are integer multiples of 2-m), color the centers of the cubelets; i.e. work with the dual graph.3-d SPERNERBoundary Coloringlegal coloring for the dual graph (on the centers of cubelets)N.B.: this coloring is not the envelope coloring we used earlier; also color names are permutedColoring of the RestRest of the coloring:All cubelets get color 0, unless they touch line L.The cubelets surrounding line L at any given point are colored with colors 1, 2, 3 in a way that “protects” the line from touching color 0.Coloring around L3321colors 1, 2, 3 are placed in a clockwise arrangement for an observer who is walking on Ltwo out of four cubelets are colored 3, one is colored 1 and the other is colored 2The Beginning of L at 0nnotice that given the coloring of the cubelets around the beginning of L (on the left), there is no point of the subdivision in the proximity of these cubelets surrounded by all four colors…Color Twisting- in the figure on the left, the arrow points to the direction in which the two cubelets colored 3 lieout of the four cubelets around L which two are colored with color 3 ?IMPORTANT directionality issue:the picture on the left shows the evolution of the location of the pair of colored 3 cubelets along the subset of L corresponding to an edge (u, v) of the PPAD graph…- observe also the way the twists of L affect the location of these cubelets with respect to Lat the main segment corresponding to u the pair of cubelets lies above L, while at the main segment corresponding to v they lie below LColor Twistingthe flip in the location of the cubelets makes it impossible to locally decide where the colored 3 cubelets should lie!to resolve this we assume that all edges (u,v) of the PPAD graph join an odd u (as a binary number) with an even v (as a binary number) or vice versafor even u’s we place the pair of 3-colored cubelets below the main segment of u, while for odd u’s we place it above the main segmentClaim1: This is W.L.O.G. convention agrees with coloring around main segment of 0nProof of Claim of Previous Slide- Duplicate the vertices of the PPAD graph- If node u is non-isolated include an edge from the 0 to the 1 copynon-isolated- Edges connect the 1-copy of a node to the 0-copy of its out-neighborFinishing the ReductionClaim 1: A point in the cube is panchromatic in the described coloring iff it is:- an endpoint u2’ of a sink vertex u of the PPAD graph, or- an endpoint u1 of a source vertex u ≠0n of the PPAD graph.A point in the cube is panchromatic iff it is the corner of some cubelet (i.e. it belongs to the subdivision of mutliples of 2-m), and all colors are present in the cubelets containing this point.Claim 2: Given the description P, N of the PPAD graph, there is a polynomial-size circuit computing the coloring of every cubelet .PPAD-completeness of BROUWER(Special) SPERNER BROUWERcolor fudgingBoundary coloring is not a legal Sperner coloring anymore, but no new panchromatic points were introduced by the modification.Claim:Proof: The points that (were not but) could potentially become panchromatic after the modification are those with: x1, x2, or x3=1-2-m. But since the ambient space is colored green and the line L is far from the boundary, this won’t happen.(Special) SPERNER BROUWERcolor 0 (ambient space)color 1color 2color 3- Convert color of to direction of the displacement vector :- Define BROUWER instance on the (slightly smaller) cube defined by the convex hull of the centers of the cubelets. This is thinner by 2-m in each dimension.(Special) SPERNER BROUWERClaim: Let x be a -approximate Brouwer Fixed Point of f. Then the corners of the simplex S containing x must have all colors. f is extended on the remaining cube by interpolation: The cube is triangulated in the canonical way. To compute the displacement of f at some point x, we find the simplex S to which x belongs. Then if , where xi are the corners of S, we define :PPAD-completeness of NASH(Special) BROUWER NASHInitial thoughts:BROUWER, SPERNER as well as END OF THE LINE are defined in terms of explicit circuits (for computing the function value, coloring, or next/previous nodes) specified in the description of the instance.In usual NP reductions, the computations performed by the gates in the circuits of the source problem need to somehow be simulated in the target problem.The trouble with NASH is that no circuit is