Proving Nash’s Theorem

I decided to split the post on finding mixed equilibra and proving the Nash Equilibrium into two posts because both are quite mathematically dense and very involved. This section in particular contains mainly intricate definitions and is not for the faint of heart. Once again, to find more details on the topics discussed in this post, please refer to this book.

    Let’s first start with a few definitions.

  1. In mathematics, a convex set C \subset \mathbb{R}^m has the property that for every pair of numbers x, y \epsilon C and \lambda \epsilon [0,1] (where \lambda is a fraction between zero and one), \lambda x + (1-\lambda)y \epsilon C. Given vectors x^0, ..., x^n and scalars \lambda_0, ..., \lambda_n, where \lambda_i \geq 0 and \displaystyle\sum\limits_{i=0}^n \lambda_i = 1, the vector sum of the product of the scalars and vectors, \displaystyle\sum\limits_{i=0}^n \lambda_i x^i, is a convex combination of the vectors x^0, ..., x^n.
  2. A set of points {x^0, ..., x^n} in Euclidean space are affinely independent if \displaystyle\sum\limits_{i=0}^n \lambda_i x^i = 0 and \displaystyle\sum\limits_{i=0}^n \lambda_i = 0 only when \lambda_0= ...= \lambda_n = 0. In other words, the points are affinely independent when the vectors \left\{x^1 - x^0, x^2 - x^0, ..., x^n-x^0\right\} are linearly independent.
  3. An n-simplex, denoted as x^0 \cdot \cdot \cdot x^n is the set of all the convex combinations of the affinely independent points {x^0, ..., x^n}:

    x^0 \cdot \cdot \cdot x^n = \left\{\displaystyle\sum\limits_{i=0}^n \lambda_i x^i: \forall i \epsilon \left\{0, ..., n\right\}, \lambda_i \geq 0; and \displaystyle\sum\limits_{i=0}^n \lambda_i = 1 \right\}.

  4. The standard n-simplex \bigtriangleup_n is:

    \left\{x^0 \cdot \cdot \cdot x^n \epsilon \mathbb{R}^{n+1}: \displaystyle\sum\limits_{i=0}^n x^i = 1, \forall i = 0, ..., n, x \geq 0 \right\}

  5. A simplical subdivision of an n-simplex, T, is a finite set of simplexes, \left\{T_i\right\} where T_i \epsilon T and \cup T_i = T. Furthermore, for any T_i, T_j \epsilon T, T_j \cap T_j is either an empty set or contains only one common face. In other words, a simplical subdivision divides an n-simplex into a set of simplexes that span the entire space and each simplex overlaps with another simplex in exactly a face.
  6. If we define a arbitrary point within a simplex, y \epsilon x^0 \cdot \cdot \cdot x^n. This point within the simplex can be written as a convex combination of the vertices of the simplex, y = \displaystyle\sum\limits_{i} \lambda_i x^i. Then, we define the set of vertices that make up the point to be \chi (y) = \left\{i:\lambda_i>0\right\}. Given a simplicial subdivided simplex T=x^0 \cdot \cdot \cdot x^n and let V be the set of all the distinct vertices of all the subsimplexes; if we assume a function \lambda: V \rightarrow \left\{0, ..., n\right\}, \lambda(v) is a proper labeling of a subdivision if \lambda(v) \epsilon \chi(v). This means that all the vertices of the original simplex must be labeled with different labels. See Figure 1 for an example of a properly labeled simplex.
    Figure 1: Properly labeled simplex. (From  Shoham and Kevin Leyton-Brown)

    Figure 1: Properly labeled simplex. (From Shoham and Kevin Leyton-Brown)

  7. A completely labeled subsimplex is one that incorporates all the values of the original simplex’s vertices, \left\{0, ..., n \right\} in \lambda. See Figure 2 for an example; the completely labeled subsimplexes are shaded in.
    Figure 2: Completely labeled subsimplexes are shaded.

    Figure 2: Completely labeled subsimplexes are shaded.

  8. Given these definitions, Sperner’s lemma states that any simplicially subdivided simplex, T_n=x^0 \cdot \cdot \cdot x^n, and a proper labeling \lambda of the subdivision yields an odd number of completely labeled subsimplexes in the subdivision.
    1. I will now prove Sperner’s lemma. (As a side note, to see a more detailed explanation of Sperner’s Lemma (with a slightly different proof) and its applications, please read this paper.) Most proofs of the theorem uses induction on n. I will introduce a simplified version of the inductive proof in proving this theorem. First consider the base case where n = 1. In this case, the simplex is a line segment with endpoints labeled \left\{1, 2 \right\}. In whichever way we divide this simplex into subsimplexes, when we go from endpoint 1 to endpoint 2, we must switch the labeling an odd number of times. An odd number of switches corresponds to an odd number of completely labeled subsimplexes. Thus, we prove that the base case holds.

      Now we assume that the lemma holds for the case (n-1) to prove the general case n. Let’s consider the example of a 3-simplex in Figure 3 while we run through the proof. Let’s first define some vocabulary (inspired by this article). Any n-simplex S is a house. A completely labeled n-1 subsimplex of the house, in other words, a subsimplex of the house with labels 1, ..., n-1 is called a door. These doors can be in the interior or on the boundary of the simplex where we remove the vertex label n (let’s call this boundary d). In Figure 3, the (1,2) edges are the doors and the big triangle labeled \left\{1,2,3\right\} is the house. The bottom edge of the big triangle is d. The rooms of the house are the individual subsimplexes or, in Figure 3, the small triangles. By our inductive assumption, d has an odd number of completely labeled subsimplexes (labeled with \left\{1,...,n-1\right\} since we have eliminated n at the boundary). Therefore, we can conclude that the number of doors on d is odd.

      We can locate the completely labeled rooms by walking through each room using a “trap-door” method. To use the “trap-door” method, we must first agree that each room can have at most two doors. (In fact, each room may only have either exactly one door or exactly two doors.) We can make sense of this in this way. If the doors are labeled with \left\{1,...,n-1\right\}, then the remaining vertex of the room can be labeled with either n or one of the labels in \left\{1,...,n-1\right\}. If the vertex is labeled n, then the room is a completely labeled subsimplex and has only one door. If the vertex is labeled with a repeating label from \left\{1,...,n-1\right\}, then the room has exactly two doors, since one door is made of the original set of vertices and the other door is made of the original set of points with the repeated label substituted in.

      We can walk through the rooms in this way. We start at any door on the boundary. If the door is part of a completely labeled room, we stop. If not, we walk through the other door in the room (the “trap-door”) and into another room. Each time we reach a completely labeled room or another door on a boundary, we stop. The paths do not cross or double-back because at most two doors exist in a room (one for entrance and one for exit) and a door can only connect two rooms. The number of doors is finite so the walk would always end at a boundary door or in a completely labeled room. Paths from doors on boundaries that do not lead to completely labeled rooms lead to another door on the boundary.
      Important note:: Walks can also be done in reverse since all walks follow the same path.

      Thus, given that the number of doors is odd on the boundary, the number of doors that lead to completely labeled rooms is also odd (since doors that do not lead to completely labeled rooms pair up). However, not every completely labeled room can be walked to from a door on the boundary. For the rooms that cannot be reached from a door on the boundary, if we start a walk from inside one of these rooms, we end up at another completely labeled room. (We cannot end up on a door on the boundary since these doors are paired up with another door on the boundary). Thus, the total number of completely labeled rooms is odd for an n-simplex. You can see an example of such walks in Figure 4.

      Figure 3: Doors are indicated by dashed lines and completely labeled rooms are shaded  (From Su 1999).

      Figure 3: Doors are indicated by dashed lines and completely labeled rooms are shaded (From Su 1999).


      Figure 4: Walked are indicated by the directed paths (from Su 1999)

      Figure 4: Walks are indicated by the directed paths (from Su 1999)

      At this point, for the sake of compactness and clarity, I will explain the rest of the proof later tomorrow in another blog post.

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

One Response to Proving Nash’s Theorem

  1. Pingback: Proving Nash’s Theorem (Part 2) | Sublime Illusions

Leave a Reply

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

WordPress.com Logo

You are commenting using your WordPress.com 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 )

Google+ photo

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

Connecting to %s