Slide 12 point ExerciseSlide 3The PPAD Class [Papadimitriou ’94]The Directed GraphSlide 6Slide 7four arguments of existenceThe Class PPA [Papadimitriou ’94]The Undirected GraphThe Class PLS [JPY ’89]The DAGThe Class PPP [Papadimitriou ’94]Slide 14Slide 15Slide 16The PLANThis LectureFirst StepNon-Isolated Nodes map to pairs of segmentsNon-Isolated Nodes map to pairs of segmentsEdges map to orthonormal pathsExceptionally 0n is closer to the boundary…Finishing the EmbeddingReducing to 3-d SpernerBoundary ColoringColoring of the RestColoring around LThe Beginning of L at 0nColor TwistingColor TwistingProof of Claim of Previous SlideFinishing the Reduction6.896: Topics in Algorithmic Game TheoryLecture 8Constantinos Daskalakis2 point Exercise5. NASH  BROUWER (cont.):- Final Point:We defined BROUWER for functions in the hypercube. But Nash’s function is defined on the product of simplices. Hence, to properly reduce NASH to BROUWER we first embed the product of simplices in a hypercube, then extend Nash’s function to points outside the product of simplices in a way that does not introduce approximate fixed points that do not correspond to approximate fixed points of Nash’s function.Last Time…The PPAD Class [Papadimitriou ’94]Suppose that an exponentially large graph with vertex set {0,1}n is defined by two circuits:PNnode idnode idnode idnode idEND OF THE LINE:Given P and N: If 0n is an unbalanced node, find another unbalanced node. Otherwise say “yes”.PPAD = { Search problems in FNP reducible to END OF THE LINE} possible previouspossible next“A directed graph with an unbalanced node (indegree  outdegree) must have another unbalanced node”{0,1}n...0nThe Directed Graph= solutionOther Combinatorial Arguments of Existencefour arguments of existence“If a graph has a node of odd degree, then it must have another.”PPA “Every directed acyclic graph must have a sink.”PLS“If a function maps n elements to n-1 elements, then there is a collision.”PPP“If a directed graph has an unbalanced node it must have another.”PPADThe Class PPA [Papadimitriou ’94]Suppose that an exponentially large graph with vertex set {0,1}n is defined by one circuit:Cnode id{ node id1 , node id2}ODD DEGREE NODE:Given C: If 0n has odd degree, find another node with odd degree. Otherwise say “yes”.PPA = { Search problems in FNP reducible to ODD DEGREE NODE} possible neighbors“If a graph has a node of odd degree, then it must have another.”{0,1}n...0nThe Undirected Graph= solutionThe Class PLS [JPY ’89]Suppose that a DAG with vertex set {0,1}n is defined by two circuits:Cnode id{node id1, …, node idk}FIND SINK:Given C, F: Find x s.t. F(x) ≥ F(y), for all y  C(x). PLS = { Search problems in FNP reducible to FIND SINK} Fnode id“Every DAG has a sink.”The DAG{0,1}n= solutionThe Class PPP [Papadimitriou ’94]Suppose that an exponentially large graph with vertex set {0,1}n is defined by one circuit:Cnode idnode idCOLLISION:Given C: Find x s.t. C( x )= 0n; or find x ≠ y s.t. C(x)=C(y). PPP = { Search problems in FNP reducible to COLLISION } “If a function maps n elements to n-1 elements, then there is a collision.”1 pointHardness ResultsInclusions we have already established:Our next goal: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, 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, DengFirst Step...0nGeneric PPADEmbed PPAD graph in [0,1]3our goal is to identify a piecewise linear, single dimensional subset of the cube, corresponding to the PPAD graph; we call this subset LNon-Isolated Nodes map to pairs of segments...0nGeneric PPADNon-Isolated Nodepair of segmentsmainauxiliary...0nGeneric PPADpair of segmentsalso, add an orthonormal path connecting the end of main segment and beginning of auxiliary segmentbreakpoints used:Non-Isolated Nodes map to pairs of segmentsNon-Isolated NodeEdges map to orthonormal paths...0nGeneric PPADorthonormal path connecting the end of the auxiliary segment of u with beginning of main segment of vEdge between and breakpoints used:Exceptionally 0n is closer to the boundary…...0nGeneric PPADThis is not necessary for the embedding of the PPAD graph, but will be useful later in the definition of the Sperner instance…Finishing the Embedding...0nGeneric PPADClaim 1:Two points p, p’ of L are closer than 32-m in Euclidean distance only if they are connected by a part of L that has length 82-m or less.Call L the orthonormal line defined by the above construction.Claim 2: Given the circuits P, N of the END OF THE LINE instance, and a point x in the cube, we can decide in polynomial time if x belongs to L.Claim 3: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 L332 1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