DOC PREVIEW
MIT 6 896 - Topics in Algorithmic Game Theory

This preview shows page 1-2-15-16-17-32-33 out of 33 pages.

Save
View full document
View full document
Premium Document
Do you want full access? Go Premium and unlock all 33 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 33 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 33 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 33 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 33 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 33 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 33 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 33 pages.
Access to all documents
Download any document
Ad free experience

Unformatted text preview:

6.896: Topics in Algorithmic Game Theory Lecture 8 Constantinos Daskalakis2 point Exercise!5. 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: P N node id node id node id node id END 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 previous possible next “A directed graph with an unbalanced node (indegree ≠ outdegree) must have another unbalanced node”{0,1}n ... 0n The Directed Graph = solutionPPADFNPSPERNERBROUWERNASHOther 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: C node 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 v1∈ C(v2) ∧ v2∈ C(v1)“If a graph has a node of odd degree, then it must have another.”{0,1}n ... 0n The Undirected Graph = solutionThe Class PLS [JPY ’89]!Suppose that a DAG with vertex set {0,1}n is defined by two circuits: C node 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} F node id RRRR .v2∈ C(v1) ∧ F (v2) >F(v1)“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: C node id node id COLLISION: 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.”FNPPPAPLSPPPPPPAD1 pointHardness ResultsPPADSPERNERBROUWERNASHInclusions we have already established: Our next goal: PPADSPERNERBROUWERNASHPPADSPERNERBROUWERNASHThe PLAN ... 0n Generic PPAD Embed PPAD graph in [0,1]3 3D-SPERNER p.w. linear BROUWER multi-player NASH 4-player NASH 3-player NASH 2-player NASH [Pap ’94] [DGP ’05] [DGP ’05] [DGP ’05] [DGP ’05] [DGP ’05] [DP ’05] [CD’05] [CD’06] x1x2x31 1 DGP = Daskalakis, Goldberg, Papadimitriou CD = Chen, DengThis Lecture ... 0n Generic PPAD Embed PPAD graph in [0,1]3 3D-SPERNER p.w. linear BROUWER multi-player NASH 4-player NASH 3-player NASH 2-player NASH [Pap ’94] [DGP ’05] [DGP ’05] [DGP ’05] [DGP ’05] [DGP ’05] [DP ’05] [CD’05] [CD’06] x1x2x31 1 DGP = Daskalakis, Goldberg, Papadimitriou CD = Chen, DengFirst Step ... 0n Generic PPAD Embed PPAD graph in [0,1]3 nm = n +4our goal is to identify a piecewise linear, single dimensional subset of the cube, corresponding to the PPAD graph; we call this subset L x1x2x3Non-Isolated Nodes map to pairs of segments ... 0n Generic PPAD Non-Isolated Node pair of segments u ∈ {0, 1}nu1= (8�u� +2, 3, 3)u�1= (8�u� +6, 3, 3)u2= (3, 8�u� +6, 2m− 3)u�2= (3, 8�u� + 10, 2m− 3)main auxiliary x1x2x3u1u�1u2u�2... 0n Generic PPAD pair of segments x1x2x3u2u�2u1u�1also, add an orthonormal path connecting the end of main segment and beginning of auxiliary segment u3= (8�u� +6, 8�u� +6, 3)u4= (8�u� +6, 8�u� +6, 2m− 3)breakpoints used: u3u4Non-Isolated Nodes map to pairs of segments Non-Isolated NodeEdges map to orthonormal paths ... 0n Generic PPAD orthonormal path connecting the end of the auxiliary segment of u with beginning of main segment of v x1x2x3u�2u1u�1Edge between and uvv1v�1u5= (8�v� +2, 8�u� + 10, 2m− 3)u6= (8�v� +2, 8�u� + 10, 3)breakpoints used:Exceptionally 0n is closer to the boundary… ... 0n Generic PPAD x1x2x3u�2u1u�1v1v�101= (2, 2, 2)0�1= (6, 2, 2)03= (6, 6, 2)This 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 ... 0n Generic PPAD x1x2x3u�2u1u�1v1v�1Claim 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: u is a sink in PPAD graph ⇔ L is disconnected at u�2u is a source in PPAD graph ⇔ L is disconnected at u1Reducing to 3-d Sperner x1x2x3u�2u1u�1v1v�1Instead 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. x1x2x33-d Sperner Kijk: center of cubelet whose least significant cornerhas coordinates (i, j, k) · 2−mBoundary Coloring x1x2x3u�2u1u�1v1v�1Kijk← 0, if any of i, j, k is 2m− 1Kijk← 1, if i =0Kijk← 2, if j =0Kijk← 3, if k =0legal coloring for the dual graph (on the centers of cubelets) x1x2x3N.B.: this coloring is not the envelope coloring we used earlier; also color names are permutedColoring of the Rest x1x2x3u�2u1u�1v1v�1Rest of the coloring: All cubelets get color , unless they touch line L. The cubelets surrounding line L at any given point are colored with colors , 2, 3 in a way that “protects” the line from touching color 0. x1x2x3Coloring around L 3 3 2 ⋅ colors , 2, 3 are placed in a clockwise arrangement for an observer who is walking on L two out of four cubelets are colored 3, one is colored 1 and the other is


View Full Document

MIT 6 896 - Topics in Algorithmic Game Theory

Download Topics in Algorithmic Game Theory
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view Topics in Algorithmic Game Theory and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view Topics in Algorithmic Game Theory 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?