Proving Nash’s Theorem (Part 2)

As promised, I will attempt to finish up the rest of the proof for Nash’s Theorem tonight (albeit a few weeks late). Let’s start again with a few definitions from where we left off.

  1. A subset of \mathbb{R}^m is compact if the set is closed and bounded. Every sequence in a compact set has a convergent subsequence.
  2. The centroid of a simplex x^0 \cdot \cdot \cdot x^m is the average of the its vertices or, in mathematical terms, the centroid is \frac{1}{m+1} \displaystyle\sum\limits_{i=0}^m x^i.
  3. Now we are set to prove Brouwer’s Fixed Point Theorem which states that a continuous function f:\bigtriangleup_m \to \bigtriangleup_m mapping a transformation of a simplex contains a fixed point z for z\epsilon \bigtriangleup_m such that f(z) = z. There are various different proofs of this theorem spread out through mathematical literature (for examples, see here, here, and here). However, I will be following the proof explained by Shosham and Leyton-Brown since the proof uses Sperner’s lemma (and is one of the easier proofs to understand).
    1. To begin, let \epsilon > 0. We then simplicially subdivide \bigtriangleup_m such that the Euclidean distance between any two vertices in a subsimplex is at most \epsilon. We label the vertices in the subsimplex with a labeling function \lambda(v) where \lambda(v) \epsilon \chi(v) \cap \left\{i: f_i(v) \leq v_i\right\}(1). For each vertex in the division, v, v_i is the ith component of the vertex and f_i(v) is the ith component of f(v). To ensure that \lambda(v) is well defined, we must show that f_i(v) weakly decreases v_i for all possible i. We show this by assuming first the opposite that f_i(v) > v_i for all i \epsilon \chi(v). Given the definition of a standard simplex (all vertices within the simplex is some combination of the components), we know that \displaystyle\sum\limits_{i=0}^m v_i = 1. By the definition of \chi(v), a component is greater than zero, v_j > 0, if and only if j\epsilon\chi(v). Thus, we can deduce the following rule:

      \displaystyle\sum\limits_{j\epsilon\chi(v)} v_j = \displaystyle\sum\limits_{i=0}^m v_i = 1


      By our assumption, f_j(v) > v_j for all j \epsilon \chi(v) so we conclude that:

      \displaystyle\sum\limits_{j\epsilon\chi(v)} f_j(v) > \displaystyle\sum\limits_{j\epsilon\chi(v)} v_j = 1


      Given that f(v) is on the standard simplex, we know that

      \displaystyle\sum\limits_{j\epsilon\chi(v)} f_j(v) \leq \displaystyle\sum\limits_{i=0}^m f_i(v) = 1


      We have reached a contradiction by Eqs. 3 and 4. Therefore, \lambda(v) is well defined and satisfies Eq. 1 with a non-empty set on the right for every i\epsilon \chi(v).

    2. Since we have shown that \lambda(v) is a proper labeling, we know by Sperner’s lemma that a complete labeling exists in the subsimplexes. As we let \epsilon approach zero, we see a convergent sequence composed of the centroids of the completely labeled subsimplexes. We can call the point that the sequence of centroids converges to z. As \epsilon \rightarrow 0, every point of the completely labeled subsimplex, p^0...p^m, will converge to z, p^i \rightarrow z where i = {0, ..., m}. Thus, we have f(z) = z since f_i(z) = z_i for all i \epsilon \chi(z). This is because we have shown that f_i(v) \leq v_i. Since all points of the completely labeled subsimplex converges to z, p^0...p^m = z. If f_i(z) < z_i, then

      \displaystyle\sum\limits_{i=0}^m f_i(z) < \displaystyle\sum\limits_{i=0}^m z_i


      But we know by definition that

      \displaystyle\sum\limits_{i=0}^m f_i(z) = 1



      \displaystyle\sum\limits_{i=0}^m z_i = 1


      so Eqs. 5, 6 and 7 reach a contradiction and f_i(z) = z_i for all i\epsilon\chi(z) and f(z) = z. QED

      It appears that it has taken longer to write the proof for Brouwer’s theorem than expected. I will finish up the last and final part (where I actually prove Nash’s theorem–hard to believe) in my final blog post for Proving Nash’s Theorem.

This entry was posted in Game theory, Math and tagged , , . Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )


Connecting to %s