Lecture 2

Existence Proofs: Nash, Brouwer, and Sperner

In this lecture, we will do a deep dive into the proof of Brouwer’s fixed point theorem, the main theorem that we invoked in the previous lecture to show the existence of Nash equilibrium. We will provide an elementary proof of Brouwer’s theorem, one of several in the literature, with the goal of distilling Brouwer’s existence-of-fixed-points result into a pure, combinatorial form. In particular, we seek to provide an answer to the following question:

Towards an answer, we will provide a proof of Brouwer’s theorem via another existence theorem, known as Sperner’s lemma. This pertains to a combinatorial structure, namely colorings of a triangulated grid, and it certifies the guaranteed existence of certain colorful triangles in this grid, if the coloring of the grid’s boundary meets certain conditions. Given that Sperner’s lemma pertains to combinatorial structures, by showing Brouwer’s theorem through Sperner’s lemma we come closer to a satisfying answer to the above question. Distilling even further, we will provide a proof of Sperner’s lemma as a corollary of an elementary existence result, namely a parity argument in directed graphs. All in all, at the end of this lecture, we will have a surprisingly crisp answer to our question:

And why are we interested in this pursuit? One reason is that we want to de-mystify what makes Nash equilibria exist in every game, and what makes fixed points exist in every continuous function from a convex compact set to itself.

Another reason is that designing algorithms for computing Nash equilibria can benefit from understanding the nature of the combinatorial argument underlying the existence of Nash equilibria. Indeed, we will soon see algorithms for computing Nash equilibria using the findings from this lecture.

And, in the reverse direction, understanding whether there are complexity barriers in the computation of Nash equilibria might benefit from known barriers for computing Brouwer fixed points, and colorful triangles in colored grids. Indeed, we will develop these ideas to study the computational complexity of Nash equilibria.

Relating the last two points, in this lecture we will lay the foundations for proving that: computing Nash equilibria can be polynomial-time reduced to computing fixed points of Lipschitz continuous functions; that the latter can be polynomial-time reduced to finding colorful triangles, guaranteed to exist in some large, colored grid by Sperner’s lemma; and that the latter can be polynomial-time reduced to finding odd degree vertices in some large, directed graph given another odd degree vertex in that graph. So, informally, Nash will reduce to Brouwer which will reduce to Sperner which will reduce to a computational problem capturing the parity argument in directed graphs. This direction of reductions will give us ideas for Nash equilibrium computation algorithms.

Surprisingly, in a future lecture we will also establish reductions in the reverse direction, namely that parity reduces to Sperner which reduces to Brouwer which reduces to Nash! And we will use this direction of reductions to study the computational complexity of Nash equilibrium computation.

L2.1 Sperner’s lemma

Sperner’s lemma applies to a \(3\)-colored \(N \times N\) grids of points. There are high-dimensional analogues of the lemma, but we will stick to \(2\) dimensions in this lectures. For the lemma to apply, the rules are simple. Each point is colored with one of three colors: red, blue, or yellow. The coloring must, however, satisfy the following boundary conditions:

1. The left column cannot contain any blue;
2. The bottom row cannot contain any red;
3. The right column and top row cannot contain any yellow.

Any coloring that satisfies these conditions is called a Sperner coloring. An example of a coloring satisfying these rules is shown in Figure 1.

Given any Sperner coloring, we are interested in finding a trichromatic triangle, that is, a triangular cell whose vertices are colored red, blue, and yellow. Sperner’s lemma guarantees that such a cell is guaranteed to exist, no matter the Sperner coloring.

We illustrate the previous theorem in the colored grid of Figure 1.

L2.1.1 The connection between Brouwer and Sperner

What does Sperner’s lemma have to do with Brouwer’s fixed point theorem? The connection is not immediate, but upon second thought, several glimpses of connections emerge. For one, both results are existence results. Furthermore, both results are trivially false if the “boundary conditions” in their statements are violated. In the case of Brouwer’s fixed point theorem, the boundary conditions are that the continuous function must map the compact set to itself, i.e. the boundary points must be mapped to somewhere inside the set. In the case of Sperner’s lemma, the boundary conditions are the coloring rules on the boundary.

If the direction of \(f ( z ) - z\) lies in the yellow-blue, blue-red, or yellow-red boundary, we can assign any one of the two compatible colors, but we will make sure that, for grid points lying on the boundary of \([0 , 1]^{2}\), we will break ties in favor of the color that does not violate the Sperner coloring conditions. Because \(f\) maps \([0 , 1]^{2}\) to itself, there should always be at least one such option! Thus, the coloring we will obtain will be a valid Sperner coloring, and it will have at least one trichromatic triangle.

In turn, it should be intuitively clear why trichromatic triangles have value vis-à-vis the fixed point behavior of \(f\): they are triangles where \(f ( z ) - z\) changes direction within a small distance and, due to continuity, \(f ( z ) - z\) can’t be too large.

We formalize these ideas in the next sections, arriving at two results. First, we will show a complete proof of Brouwer’s fixed point theorem, using Sperner’s lemma and a compactness argument. Second, we will establish the following computational reduction. Suppose we are given access to an algorithm that takes as input a Sperner coloring of a triangulated grid and computes a trichromatic triangle guaranteed by Sperner’s lemma. Then, we can use this algorithm to compute approximate Brouwer fixed points of a Lipschitz continuous function, \(f\), from \([0 , 1]^{2}\) to itself, by discretizing the domain into a grid whose cells have small enough diameter, as a function of the Lipschitz constant and the desired approximation, coloring the vertices of this grid according to the scheme presented above, and finding a trichromatic triangle. We illustrate how this reduction would work with an example.

It is worth noting that the trichromatic triangles obtained via the above reduction are not always in the proximity of exact fixed points of the function. Unless the discretization is fine enough and \(f\) has extra properties, we will only guarantee that the trichromatic triangles are in the proximity of approximate fixed points. While this is not the case in the examples above, it can be the case.

L2.1.2 Formalizing the connection

To make the argument formal, we need to establish a formal connection between a trichromatic triangle and an approximate Brouwer fixed point, and connect that to a choice of discretization parameter.

By the Heine-Cantor theorem, any continuous function \(f\) on a compact set is uniformly continuous, which implies that:

Now, given \(f\) and \(\epsilon\), consider a triangulation of \([ 0 , 1 ]^{2}\) in which the diameter of every triangle is \(\delta\) in \(ℓ_{∞}\). Assign colors to the vertices of the triangulation according to the direction of \(f ( z ) - z\), using the coloring scheme discussed above, and breaking ties in an arbitrary way but respecting the Sperner coloring conditions. Let us call the resulting coloring a Sperner discretization of \(f\) of diameter \(\delta\). Then, the following approximation bound can be established.

In turn, using a standard compactness argument, Corollary L2.5 implies Brouwer’s fixed point theorem for continuous functions from \([ 0 , 1 ]^{2}\) to itself.

L2.2 Proof of Sperner’s lemma

Now we turn to proving Sperner’s lemma. As it turns out, the lemma can be obtained as a corollary of a very basic parity argument on directed graphs.

Assuming a standard Sperner coloring is without loss of generality. Indeed, if a given Sperner coloring is not standard (as in Figure 1), we can always augment the grid with an additional layer of boundary that is colored in the standard way, and embed the given Sperner coloring in the inside. Due to the properties of Sperner colorings and the standard boundary coloring, this operation will not introduce any trichromatic triangles between the extra boundary and the old boundary.

Now that our boundary coloring is standard, we can easily show Sperner’s lemma using a graph-theoretic argument. Given a standard Sperner coloring we can define a directed graph, called Sperner graph, as follows:

For the standard Sperner coloring of Figure 1, the corresponding graph is shown just above on the left.

L2.2.1 Properties of the Sperner graph

As you might have guessed from the picture, the following key properties hold.

L2.2.2 Completing the proof of Sperner’s lemma

At this point, the proof of Sperner’s lemma is immediate. A graph in which each node has indegree at most one and outdegree at most one is composed of connected components that can only be singleton nodes, directed paths, or directed simple cycles. Only paths have nodes with outdegree \(1\) and indegree \(0\), or outdegree \(0\) and indegree \(1\); each has exactly one of each. Note also that the standard boundary coloring forces the bottom left cell not to be trichromatic, and node corresponding to this cell to have outdegree \(1\) and indegree \(0\). So this node must be the source of a path. The sink of that path is trichromatic as per Theorem L2.7. If there are other paths, both their source and their sink are trichromatic, as per Theorem L2.7. Hence, there are an odd number of trichromatic triangles in any standard Sperner coloring, and therefore any Sperner coloring.

L2.3 Beyond the unit square

We stated and proved Sperner’s lemma for the two-dimensional grid, and used that to prove Brouwer’s fixed point theorem for continuous functions mapping the unit square to itself. There is a \(d\)-dimensional generalization of Sperner’s lemma, which can be used to prove Brouwer’s fixed point theorem for continuous functions mapping \([ 0 , 1 ]^{d}\) to itself. In the high-dimensional case, a \(d\)-dimensional grid is partitioned into simplices, the \(d\)-dimensional analog of triangles, without introducing any more vertices other than those in the grid. The vertices of the grid are now colored with \(d + 1\) colors, \(0 , 1 , \dots , d\). Now, a coloring is valid if color \(i\) is not present in facet \(x_{i} = 0\), for all \(i = 1 , \dots , d\), and color \(0\) is not present in all facets \(x_{i} = 1\), for all \(i = 1 , \dots , d\). Sperner’s lemma guarantees the existence of a simplex that has all \(d + 1\) colors on its \(d + 1\) vertices. Using the \(d\)-dimensional version of Sperner’s lemma to prove Brouwer’s fixed point theorem for continuous functions mapping the \(d\)-dimensional hypercube to itself is analogous to the \(d = 2\) case. Finally, given Brouwer’s fixed point theorem for the hypercube it is not hard to prove it for other convex and compact sets. Given a function defined on an arbitrary convex and compact set, one can first affinely transform the coordinate system so the set lies inside the unit hypercube. Then the function can be extended outside of the set by first projecting points of the hypercube to the set and then applying the function. This will not introduce any spurious fixed points.