6.896: Topics in Algorithmic Game Theory Audiovisual Supplement to Lecture 5 Constantinos DaskalakisOn the blackboard we defined multi-player games and Nash equilibria, and showed Nash’s theorem that a Nash equilibrium exists in every game. In our proof, we used Brouwer’s fixed point theorem. In this presentation, we explain Brouwer’s theorem, and give an illustration of Nash’s proof. We proceed to prove Brouwer’s Theorem using a combinatorial lemma whose proof we also provide, called Sperner’s Lemma.Brouwer’ s Fixed Point TheoremBrouwer’s fixed point theorem f Theorem: Let f : D D be a continuous function from a convex and compact subset D of the Euclidean space to itself. −→Then there exists an x s.t. x = f (x) . ∈ DN.B. All conditions in the statement of the theorem are necessary. closed and bounded D D Below we show a few examples, when D is the 2-dimensional disk.Brouwer’s fixed point theorem fixed pointBrouwer’s fixed point theorem fixed pointBrouwer’s fixed point theorem fixed pointNash’s Proofƒ: [0,1]2 →[0,1]2, continuous such that fixed points ≡ Nash eq. Kick Dive Left Right Left 1 , -1 -1 , 1 Right -1 , 1 1, -1 Visualizing Nash’s ConstructionKick Dive Left Right Left 1 , -1 -1 , 1 Right -1 , 1 1, -1 Visualizing Nash’s Construction 0 1 0 1 Pr[Right] Pr[Right]Kick Dive Left Right Left 1 , -1 -1 , 1 Right -1 , 1 1, -1 Visualizing Nash’s Construction 0 1 0 1 Pr[Right] Pr[Right]Kick Dive Left Right Left 1 , -1 -1 , 1 Right -1 , 1 1, -1 Visualizing Nash’s Construction 0 1 0 1 Pr[Right] Pr[Right]ƒ: [0,1]2 →[0,1]2, cont. such that fixed point ≡ Nash eq. Kick Dive Left Right Left 1 , -1 -1 , 1 Right -1 , 1 1, -1 Visualizing Nash’s Construction 0 1 0 1 Pr[Right] Pr[Right] fixed point ½ ½ ½ ½Sperner’s LemmaSperner’s LemmaSperner’s Lemma no red no blue no yellow Lemma: Color the boundary using three colors in a legal way.Sperner’s Lemma Lemma: Color the boundary using three colors in a legal way. No matter how the internal nodes are colored, there exists a tri-chromatic triangle. In fact an odd number of those. no red no blue no yellowSperner’s Lemma Lemma: Color the boundary using three colors in a legal way. No matter how the internal nodes are colored, there exists a tri-chromatic triangle. In fact an odd number of those.Sperner’s Lemma Lemma: Color the boundary using three colors in a legal way. No matter how the internal nodes are colored, there exists a tri-chromatic triangle. In fact an odd number of those.Proof of Sperner’s Lemma Lemma: Color the boundary using three colors in a legal way. No matter how the internal nodes are colored, there exists a tri-chromatic triangle. In fact an odd number of those. For convenience we introduce an outer boundary, that does not create new tri-chromatic triangles. Next we define a directed walk starting from the bottom-left triangle.Transition Rule: If ∃ red - yellow door cross it with red on your left hand. ? Space of Triangles 1 2 Proof of Sperner’s Lemma Lemma: Color the boundary using three colors in a legal way. No matter how the internal nodes are colored, there exists a tri-chromatic triangle. In fact an odd number of those.Proof of Sperner’s Lemma ! Lemma: Color the boundary using three colors in a legal way. No matter how the internal nodes are colored, there exists a tri-chromatic triangle. In fact an odd number of those. For convenience we introduce an outer boundary, that does not create new tri-chromatic triangles. Next we define a directed walk starting from the bottom-left triangle. Starting from other triangles we do the same going forward or backward. Claim: The walk cannot exit the square, nor can it loop around itself in a rho-shape. Hence, it must stop somewhere inside. This can only happen at tri-chromatic triangle…Proof of Brouwer’s Fixed Point Theorem We show that Sperner’s Lemma implies Brouwer’s Fixed Point Theorem. We start with the 2-dimensional Brouwer problem on the square.2D-Brouwer on the Square Suppose ƒ: [0,1]2 →[0,1]2, continuous must be uniformly continuous (by the Heine-Cantor theorem) say d is the �∞norm1 0 1 0 −→−→xy∀� > 0, ∃δ = δ(�) > 0, s.t.d(z, w) < δ =⇒ d(f(z),f(w)) < �2D-Brouwer on the Square Suppose ƒ: [0,1]2 →[0,1]2, continuous must be uniformly continuous (by the Heine-Cantor theorem) < δ(�)choose some and triangulate so that the diameter of cells is at most �δ(�)say d is the �∞norm1 0 1 0 −→−→xy∀� > 0, ∃δ = δ(�) > 0, s.t.d(z, w) < δ =⇒ d(f(z),f(w)) < �2D-Brouwer on the Square Suppose ƒ: [0,1]2 →[0,1]2, continuous must be uniformly continuous (by the Heine-Cantor theorem) < δ(�)choose some and triangulate so that the diameter of cells is at most �δ(�)say d is the �∞norm1 0 1 0 −→−→xy∀� > 0, ∃δ = δ(�) > 0, s.t.d(z, w) < δ =⇒ d(f(z),f(w)) < �color the nodes of the triangulation according to the direction of f(x) − x1 0 1 0 −→−→xy2D-Brouwer on the Square Suppose ƒ: [0,1]2 →[0,1]2, continuous must be uniformly continuous (by the Heine-Cantor theorem) < δ(�)choose some and triangulate so that the diameter of cells is at most �δ(�)color the nodes of the triangulation according to the direction of f(x) − xsay d is the �∞norm∀� > 0, ∃δ = δ(�) > 0, s.t.d(z, w) < δ =⇒ d(f(z),f(w)) < �tie-break at the boundary angles, so that the resulting coloring respects the boundary conditions required by Sperner’s lemma find a trichromatic triangle, guaranteed by Sperner2D-Brouwer on the Square Suppose ƒ: [0,1]2 →[0,1]2, continuous must be uniformly continuous (by the Heine-Cantor theorem) Claim: If zY is the yellow corner of a trichromatic triangle, then say d is the �∞norm∀� > 0, ∃δ = δ(�) > 0, s.t.d(z, w) < δ =⇒ d(f(z),f(w)) < �|f(zY) − zY|∞< � + δ.1 0 1 0 −→−→xy1 0 1 0 −→−→xyProof of Claim Claim: If zY is the yellow corner of a trichromatic triangle, then |f(zY) − zY|∞< � + δ.Proof: Let zY, zR , zB be the yellow/red/blue corners of a trichromatic triangle. By the definition of the coloring, observe that the product of (f(zY) − zY)xand (f (zB) − zB)xis ≤ 0.Hence: |(f(zY) − zY)x|≤ |(f(zY) − zY)x− (f(zB) − zB)x|≤ |(f(zY) − f(zB))x| + |(zY− zB)x|≤ d(f(zY),f(zB)) + d(zY,zB)≤ � + δ.|(f(zY) − zR)y| ≤ � +