MIT 6.S890 — Topics in Multiagent Learning Tue, Nov 19th 2024
Lecture 17
PPAD-completeness of Nash equilibria (Part I)
Instructor: Prof. Gabriele Farina ( gfarina@mit.edu)★
As promised, we close this course with a discussion of problems that, from the point of view of its
computational complexity, are equivalent to that of computing Nash equilibrium. We have already
seen in Lecture 2 that the one can prove existence of Nash equilibrium in general games directly
from applying Brouwer’s fixed-point theorem on a continuous function from a compact and convex
set to itself. This immediately shows that
Computing Nash equilibrium is not harder than computing Brouwer fixed points.
Yet, no other proof of existence of Nash equilibrium is known that does not rely on Brouwer’s fixed
point theorem. Why is that the case? One of the main reasons is the following (very much non-
trivial) fact.
The opposite is also true: from a computational point of view, the computation of a Brouwer
fixed point is equivalent to computing a Nash equilibrium of some appropriate game of
polynomial size.
In other words, Nash equilibria are the prototypical example of a Brouwer fixed points!
1 Sperner’s lemma
One of the important merits of complexity
theory is that of connecting problems that,
despite their desparate looks, are united by
their ability to encode one same hard primi-
tive. For example, all NP-complete problem
are united by the fact that they are all equiv-
alent methods for checking whether satisfying
assignment to a Boolean formula exists.
What is the primitive that unites Brouwer’s
fixed points and Nash equilibria? To shed
light in this direction, let us consider
another problem that, at first glance,
has nothing to do with neither fixed
points nor equilibria: Sperner’s lemma.
No blue
No red
No yellow
Figure 1: Sample Sperner coloring.
Upon further inspection, it will turn out to be another problem in the same “family” as the previous
two.
Sperner’s lemma has to do with colored 𝑁 × 𝑁 grids of points. 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:
i. The left column cannot contain any blue;
ii. The bottom row cannot contain any red;
iii. 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 cell whose
vertices are colored red, blue, and yellow. Sperner’s lemma guarantees that such a request is always
possible to satisfy.
Theorem 1.1 (Sperner’s lemma). Any Sperner coloring must have at least one trichromatic
triangle.
In fact, it must have an odd number number of trichromatic triangles.
We illustrate the previous theorem on the grid of Figure 1.
Example 1.1. In the grid of Figure 1, there are a total of five
trichromatic triangles, as highlighted in green on the right.
Indeed, five is an odd number, validating the prediction of
Theorem 1.1.
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 nonconstructive existence results. Furthermore, both results are trivially false
if the boundary conditions are not satisfied. In the case of Brouwer’s fixed point theorem,
the boundary conditions are that the continuous function must map
the compact set to itself. In the case of Sperner’s lemma, they are the
coloring rules on the boundary. As it turns out, Sperner’s lemma is
fundamentally a discretized version of Brouwer’s fixed point theorem for
continuous functions on [0, 1]2. The colors correspond to a discretization
of the direction in which 𝑓(𝑧) − 𝑧 points, according to the coloring rule
shown on the left.
yellow
blue
red
(This was the same coloring we used in Lecture 2, with a bit of foreboding).
Following this connection, it should then be immediate why trichromatic triangles have value: they
correspond to cells in which the function points in three different directions, at the three corners of
the triangle, which gives hope that—due to continuity—the function must have a point somewhere
in the interior of the triangle in which all directions coexist and cancel out leading to a fixed point.
If we had access to an algorithm to find trichromatic triangles, we could use it to find approximate
Brouwer fixed points of continuous functions [0, 1]2 → [0, 1]2 by discretizing the space and coloring
the points according to the direction in which the function points. The discretization parameter
would then determine the precision of the fixed point. We illustrate this with an example.
Example 1.2. The following plots illustrate the Sperner discretization of the Nash improvement
function in three games we used in Lecture 2.
Nash improvement
function (Brouwer) Theater or football Prisoner's dilemma Penalty shot game
→
→
→
Sperner discretization
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 on a compact set is uniformly continuous, meaning
that
∀𝜖 > 0, ∃𝛿(𝜖) > 0 : ‖𝑧 − 𝑤‖∞ ≤ 𝛿(𝜖) ⟹ ‖𝑓(𝑧) − 𝑓(𝑤)‖∞ ≤ 𝜖.
Consider now a Sperner discretization in which the diameter of every cell is at most 𝛿 ≤ 𝛿(𝜖). Then,
the following approximation bound can be established.
Theorem 1.2. If 𝑧𝑌 is the yellow corner of a trichromatic triangle in a Sperner discretization
with cell diameter 𝛿 ≤ 𝛿(𝜖), then
‖𝑓(𝑧𝑌 ) − 𝑧𝑌 ‖∞ < 𝜀 + 𝛿.
Proof . Let 𝑧𝑅, 𝑧𝐵, and 𝑧𝑌 be the red, blue, and yellow vertices of the trichromatic triangle. The
key observation is that, by the coloring rule,
(𝑓(𝑧𝑌 ) − 𝑧𝑌 )𝑥 and (𝑓(𝑧𝐵) − 𝑧𝐵)𝑥 have opposite signs, and
(𝑓(𝑧𝑌 ) − 𝑧𝑌 )𝑦 and (𝑓(𝑧𝑅) − 𝑧𝑅)𝑦 have opposite signs.
Thus, we can write
|(𝑓(𝑧𝑌 ) − 𝑧𝑌 )𝑥| ≤ |(𝑓 (𝑧𝑌 ) − 𝑧𝑌 )𝑥 − (𝑓 (𝑧𝐵) − 𝑧𝐵)𝑥|
≤ |(𝑓(𝑧𝑌 ) − 𝑓(𝑧𝐵))𝑥 − (𝑧𝑌 − 𝑧𝐵)𝑥|
≤ ‖𝑓(𝑧𝑌 ) − 𝑓(𝑧𝐵)‖∞ + ‖𝑧𝑌 − 𝑧𝐵‖∞ < 𝜖 + 𝛿.
and similarly
|(𝑓(𝑧𝑌 ) − 𝑧𝑌 )𝑦| ≤ |(𝑓 (𝑧𝑌 ) − 𝑧𝑌 )𝑦 − (𝑓 (𝑧𝑅) − 𝑧𝑅)𝑦|
≤ |(𝑓(𝑧𝑌 ) − 𝑓(𝑧𝑅))𝑦 − (𝑧𝑌 − 𝑧𝑅)𝑦|
≤ ‖𝑓(𝑧𝑌 ) − 𝑓(𝑧𝑅)‖∞ + ‖𝑧𝑌 − 𝑧𝑅‖∞ < 𝜖 + 𝛿.
From here, we can just use the definition of infinity norm:
‖𝑓(𝑧𝑌 ) − 𝑧𝑌 ‖∞ = max{|(𝑓(𝑧𝑌 ) − 𝑧𝑌 )𝑥|, |(𝑓 (𝑧𝑌 ) − 𝑧𝑌 )𝑦|} < 𝜖 + 𝛿.
□
Corollary 1.1. Let 𝜖 > 0 be an arbitrary precision. The Sperner discretization of the function
with parameter 𝛿 ≔ min{𝛿(𝜖), 𝜖} is a 2𝜖-approximate Brouwer fixed point.
While this is not necessary for our discussion of the complexity of equilibrium computation, we
remark that Corollary 1.1 immediately implies, using a standard compactness argument, Brouwer’s
fixed point theorem for the two-dimensional (2D) case.
Corollary 1.2 (Brouwer’s fixed point theorem, 2D case). Any continuous function [0, 1]2 → [0, 1]2
has a fixed point.
Proof . Consider the sequence of approximations 𝜖𝑖 ≔ 2−𝑖 for 𝑖 ∈ ℕ≥1, and the corresponding
discretization parameters 𝛿𝑖 ≔ min{𝛿(𝜖𝑖), 𝜖𝑖}. For each 𝑖, we can isolate a yellow vertex 𝑧𝑌 ,𝑖. Since
𝑧𝑌 ,𝑖 ∈ [0, 1]2, and [0, 1]2 is a compact set, there exists a convergent subsequence 𝑧𝑌 ,𝑗; let 𝑧𝑌 denote
the limit of such a subsequence. By the continuity of 𝑓, the function 𝑑(𝑧) ≔ ‖𝑓(𝑧) − 𝑧‖∞ is also
continuous. Hence,
𝑑(𝑧𝑌 ) = lim 𝑑(𝑧𝑌 ,𝑗).
Since 𝑑(𝑧𝑌 ,𝑗) ∈ [0, 2 ⋅ 2−𝑗] by Corollary 1.1, we conclude 𝑑(𝑧𝑌 ) = 0, which is equivalent to 𝑓(𝑧𝑌 ) =
𝑧𝑌 . This proves that a fixed point exists. □
2 Proof of Sperner’s lemma, and the PPAD complexity class
How can one prove Sperner’s lemma? As it turns out, the lemma can be restated as a pretty
simple property of graphs. By following this process, we will be able to shed more light into the
nonconstructive nature of the proof of existence.
Before jumping into the proof, let’s operate a simpli-
fication. Without loss of generality, we will assume
that the boundary of the Sperner coloring is as in
the figure on the right: red on the left (except for the
bottom-left corner), yellow on the bottom (expect for
the bottom-right corner), and blue everywhere else.
We will call any such instance a standard Sperner
coloring.
The previous assumption is without loss of general-
ity. Indeed, if the boundary of the instance does
not respect the assumption (e.g., Figure 1), we
can always pad the grid with a boundary that satisfies the assumption, and embed the non-respecting
grid in the inside. This will not change the number of positions of the trichromatic triangles.
The proof of Sperner’s lemma is based on a graph-
theoretic argument. We can convert any standard
Sperner coloring into a Sperner graph as follows:
• Each cell is converted into a node;
• Two neighboring cells 𝑢, 𝑣 (nodes) are con-
nected by a directed edge 𝑢 → 𝑣 if to go
from cell 𝑢 to cell 𝑣 one passes through a
red-yellow portal, i.e., a segment that has a
red color on the left and a yellow color on
the right.
For the standard Sperner coloring of Figure 1, the corresponding graph is shown just above on
the left.
2.1 Properties of the Sperner graph
As you might have guessed from the picture, the following key properties hold.
Theorem 2.1. In any Sperner graph, the following properties hold:
(1) every node has outdegree and indegree at most 1;
(2) any node with indegree 1 and outdegree 0 is a trichromatic triangle (marked green in the
figure above);
(3) any node with outdegree 1 and indegree 0 is a trichromatic triangle (marked green), with
the only exception of the bottomleft node (marked purple).
Proof . Property (1) follows from case analysis.
We prove property (2) by contradiction. Take any node with indegree 1 and outdegree 0, and
assume for contradiction that it is not a trichromatic triangle. Since the indegree is 1, one of
the sides of the cell corrsponding to the node is a red-yellow gate. Let’s consider now the third
vertex of the cell. Since by assumption the cell is not trichromatic, the third vertex is either red
or yellow. Either case produces another red-yellow gate, so the cell must be on the boundary of
the Sperner coloring. A simple case analysis reveals that it is impossible that such a cell exists
given the boundary conditions.
A similar argument can be made for property (3). □
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, lines, or simple cycles. Only lines have nodes with outdegree 1 and indegree 0, or
outdegree 0 and indegree 1; each has exactly one of each. Furthermore, the bottomleft node is part
of a line, and is the only node with outdegre 1 and indegree 0 that is not a trichromatic triangle.
Hence, there are an odd number of trichromatic triangles in any Sperner coloring.
2.2 The PPAD complexity class
The proof of Sperner’s lemma seen above distilled the problem of computing a trichromatic triangle
(and hence an approximate Brouwer fixed point) into the problem of finding the end of the line
connected component to which the bottom left cell belongs. In other words, approximate Brouwer
fixed points can be computed if one can follow quickly a line graph until the end. This is the essence
of the PPAD complexity class: a problem is in PPAD if it can be reduced to finding the end of a line
in a directed graph in which every node has indegree and outdegree at most 1, and a given start of
a line is given.
As just stated, the problem might seem kind of trivial: after all, why can’t we just follow the line until
the end? The problem is in the size of Sperner discretization that we need. Assuming the function
for which we need an 𝜖-approximate Brouwer fixed point is 1-Lischitz continuous, the size 𝑁 of the
Sperner coloring we need to consider is roughly of order 1/𝜖, where 𝜖 is the desired precision. This
quantity is exponentially large in the representation of 𝜖 specified in the input, which only takes
log(1/𝜖) bits to store.
★These notes are class material that has not undergone formal peer review. The TA and I are grateful for any
reports of typos.
Lecture 17
PPAD-completeness of Nash equilibria (Part I)
Instructor: Prof. Gabriele Farina ( gfarina@mit.edu)★
As promised, we close this course with a discussion of problems that, from the point of view of its
computational complexity, are equivalent to that of computing Nash equilibrium. We have already
seen in Lecture 2 that the one can prove existence of Nash equilibrium in general games directly
from applying Brouwer’s fixed-point theorem on a continuous function from a compact and convex
set to itself. This immediately shows that
Computing Nash equilibrium is not harder than computing Brouwer fixed points.
Yet, no other proof of existence of Nash equilibrium is known that does not rely on Brouwer’s fixed
point theorem. Why is that the case? One of the main reasons is the following (very much non-
trivial) fact.
The opposite is also true: from a computational point of view, the computation of a Brouwer
fixed point is equivalent to computing a Nash equilibrium of some appropriate game of
polynomial size.
In other words, Nash equilibria are the prototypical example of a Brouwer fixed points!
1 Sperner’s lemma
One of the important merits of complexity
theory is that of connecting problems that,
despite their desparate looks, are united by
their ability to encode one same hard primi-
tive. For example, all NP-complete problem
are united by the fact that they are all equiv-
alent methods for checking whether satisfying
assignment to a Boolean formula exists.
What is the primitive that unites Brouwer’s
fixed points and Nash equilibria? To shed
light in this direction, let us consider
another problem that, at first glance,
has nothing to do with neither fixed
points nor equilibria: Sperner’s lemma.
No blue
No red
No yellow
Figure 1: Sample Sperner coloring.
Upon further inspection, it will turn out to be another problem in the same “family” as the previous
two.
Sperner’s lemma has to do with colored 𝑁 × 𝑁 grids of points. 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:
i. The left column cannot contain any blue;
ii. The bottom row cannot contain any red;
iii. 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 cell whose
vertices are colored red, blue, and yellow. Sperner’s lemma guarantees that such a request is always
possible to satisfy.
Theorem 1.1 (Sperner’s lemma). Any Sperner coloring must have at least one trichromatic
triangle.
In fact, it must have an odd number number of trichromatic triangles.
We illustrate the previous theorem on the grid of Figure 1.
Example 1.1. In the grid of Figure 1, there are a total of five
trichromatic triangles, as highlighted in green on the right.
Indeed, five is an odd number, validating the prediction of
Theorem 1.1.
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 nonconstructive existence results. Furthermore, both results are trivially false
if the boundary conditions are not satisfied. In the case of Brouwer’s fixed point theorem,
the boundary conditions are that the continuous function must map
the compact set to itself. In the case of Sperner’s lemma, they are the
coloring rules on the boundary. As it turns out, Sperner’s lemma is
fundamentally a discretized version of Brouwer’s fixed point theorem for
continuous functions on [0, 1]2. The colors correspond to a discretization
of the direction in which 𝑓(𝑧) − 𝑧 points, according to the coloring rule
shown on the left.
yellow
blue
red
(This was the same coloring we used in Lecture 2, with a bit of foreboding).
Following this connection, it should then be immediate why trichromatic triangles have value: they
correspond to cells in which the function points in three different directions, at the three corners of
the triangle, which gives hope that—due to continuity—the function must have a point somewhere
in the interior of the triangle in which all directions coexist and cancel out leading to a fixed point.
If we had access to an algorithm to find trichromatic triangles, we could use it to find approximate
Brouwer fixed points of continuous functions [0, 1]2 → [0, 1]2 by discretizing the space and coloring
the points according to the direction in which the function points. The discretization parameter
would then determine the precision of the fixed point. We illustrate this with an example.
Example 1.2. The following plots illustrate the Sperner discretization of the Nash improvement
function in three games we used in Lecture 2.
Nash improvement
function (Brouwer) Theater or football Prisoner's dilemma Penalty shot game
→
→
→
Sperner discretization
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 on a compact set is uniformly continuous, meaning
that
∀𝜖 > 0, ∃𝛿(𝜖) > 0 : ‖𝑧 − 𝑤‖∞ ≤ 𝛿(𝜖) ⟹ ‖𝑓(𝑧) − 𝑓(𝑤)‖∞ ≤ 𝜖.
Consider now a Sperner discretization in which the diameter of every cell is at most 𝛿 ≤ 𝛿(𝜖). Then,
the following approximation bound can be established.
Theorem 1.2. If 𝑧𝑌 is the yellow corner of a trichromatic triangle in a Sperner discretization
with cell diameter 𝛿 ≤ 𝛿(𝜖), then
‖𝑓(𝑧𝑌 ) − 𝑧𝑌 ‖∞ < 𝜀 + 𝛿.
Proof . Let 𝑧𝑅, 𝑧𝐵, and 𝑧𝑌 be the red, blue, and yellow vertices of the trichromatic triangle. The
key observation is that, by the coloring rule,
(𝑓(𝑧𝑌 ) − 𝑧𝑌 )𝑥 and (𝑓(𝑧𝐵) − 𝑧𝐵)𝑥 have opposite signs, and
(𝑓(𝑧𝑌 ) − 𝑧𝑌 )𝑦 and (𝑓(𝑧𝑅) − 𝑧𝑅)𝑦 have opposite signs.
Thus, we can write
|(𝑓(𝑧𝑌 ) − 𝑧𝑌 )𝑥| ≤ |(𝑓 (𝑧𝑌 ) − 𝑧𝑌 )𝑥 − (𝑓 (𝑧𝐵) − 𝑧𝐵)𝑥|
≤ |(𝑓(𝑧𝑌 ) − 𝑓(𝑧𝐵))𝑥 − (𝑧𝑌 − 𝑧𝐵)𝑥|
≤ ‖𝑓(𝑧𝑌 ) − 𝑓(𝑧𝐵)‖∞ + ‖𝑧𝑌 − 𝑧𝐵‖∞ < 𝜖 + 𝛿.
and similarly
|(𝑓(𝑧𝑌 ) − 𝑧𝑌 )𝑦| ≤ |(𝑓 (𝑧𝑌 ) − 𝑧𝑌 )𝑦 − (𝑓 (𝑧𝑅) − 𝑧𝑅)𝑦|
≤ |(𝑓(𝑧𝑌 ) − 𝑓(𝑧𝑅))𝑦 − (𝑧𝑌 − 𝑧𝑅)𝑦|
≤ ‖𝑓(𝑧𝑌 ) − 𝑓(𝑧𝑅)‖∞ + ‖𝑧𝑌 − 𝑧𝑅‖∞ < 𝜖 + 𝛿.
From here, we can just use the definition of infinity norm:
‖𝑓(𝑧𝑌 ) − 𝑧𝑌 ‖∞ = max{|(𝑓(𝑧𝑌 ) − 𝑧𝑌 )𝑥|, |(𝑓 (𝑧𝑌 ) − 𝑧𝑌 )𝑦|} < 𝜖 + 𝛿.
□
Corollary 1.1. Let 𝜖 > 0 be an arbitrary precision. The Sperner discretization of the function
with parameter 𝛿 ≔ min{𝛿(𝜖), 𝜖} is a 2𝜖-approximate Brouwer fixed point.
While this is not necessary for our discussion of the complexity of equilibrium computation, we
remark that Corollary 1.1 immediately implies, using a standard compactness argument, Brouwer’s
fixed point theorem for the two-dimensional (2D) case.
Corollary 1.2 (Brouwer’s fixed point theorem, 2D case). Any continuous function [0, 1]2 → [0, 1]2
has a fixed point.
Proof . Consider the sequence of approximations 𝜖𝑖 ≔ 2−𝑖 for 𝑖 ∈ ℕ≥1, and the corresponding
discretization parameters 𝛿𝑖 ≔ min{𝛿(𝜖𝑖), 𝜖𝑖}. For each 𝑖, we can isolate a yellow vertex 𝑧𝑌 ,𝑖. Since
𝑧𝑌 ,𝑖 ∈ [0, 1]2, and [0, 1]2 is a compact set, there exists a convergent subsequence 𝑧𝑌 ,𝑗; let 𝑧𝑌 denote
the limit of such a subsequence. By the continuity of 𝑓, the function 𝑑(𝑧) ≔ ‖𝑓(𝑧) − 𝑧‖∞ is also
continuous. Hence,
𝑑(𝑧𝑌 ) = lim 𝑑(𝑧𝑌 ,𝑗).
Since 𝑑(𝑧𝑌 ,𝑗) ∈ [0, 2 ⋅ 2−𝑗] by Corollary 1.1, we conclude 𝑑(𝑧𝑌 ) = 0, which is equivalent to 𝑓(𝑧𝑌 ) =
𝑧𝑌 . This proves that a fixed point exists. □
2 Proof of Sperner’s lemma, and the PPAD complexity class
How can one prove Sperner’s lemma? As it turns out, the lemma can be restated as a pretty
simple property of graphs. By following this process, we will be able to shed more light into the
nonconstructive nature of the proof of existence.
Before jumping into the proof, let’s operate a simpli-
fication. Without loss of generality, we will assume
that the boundary of the Sperner coloring is as in
the figure on the right: red on the left (except for the
bottom-left corner), yellow on the bottom (expect for
the bottom-right corner), and blue everywhere else.
We will call any such instance a standard Sperner
coloring.
The previous assumption is without loss of general-
ity. Indeed, if the boundary of the instance does
not respect the assumption (e.g., Figure 1), we
can always pad the grid with a boundary that satisfies the assumption, and embed the non-respecting
grid in the inside. This will not change the number of positions of the trichromatic triangles.
The proof of Sperner’s lemma is based on a graph-
theoretic argument. We can convert any standard
Sperner coloring into a Sperner graph as follows:
• Each cell is converted into a node;
• Two neighboring cells 𝑢, 𝑣 (nodes) are con-
nected by a directed edge 𝑢 → 𝑣 if to go
from cell 𝑢 to cell 𝑣 one passes through a
red-yellow portal, i.e., a segment that has a
red color on the left and a yellow color on
the right.
For the standard Sperner coloring of Figure 1, the corresponding graph is shown just above on
the left.
2.1 Properties of the Sperner graph
As you might have guessed from the picture, the following key properties hold.
Theorem 2.1. In any Sperner graph, the following properties hold:
(1) every node has outdegree and indegree at most 1;
(2) any node with indegree 1 and outdegree 0 is a trichromatic triangle (marked green in the
figure above);
(3) any node with outdegree 1 and indegree 0 is a trichromatic triangle (marked green), with
the only exception of the bottomleft node (marked purple).
Proof . Property (1) follows from case analysis.
We prove property (2) by contradiction. Take any node with indegree 1 and outdegree 0, and
assume for contradiction that it is not a trichromatic triangle. Since the indegree is 1, one of
the sides of the cell corrsponding to the node is a red-yellow gate. Let’s consider now the third
vertex of the cell. Since by assumption the cell is not trichromatic, the third vertex is either red
or yellow. Either case produces another red-yellow gate, so the cell must be on the boundary of
the Sperner coloring. A simple case analysis reveals that it is impossible that such a cell exists
given the boundary conditions.
A similar argument can be made for property (3). □
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, lines, or simple cycles. Only lines have nodes with outdegree 1 and indegree 0, or
outdegree 0 and indegree 1; each has exactly one of each. Furthermore, the bottomleft node is part
of a line, and is the only node with outdegre 1 and indegree 0 that is not a trichromatic triangle.
Hence, there are an odd number of trichromatic triangles in any Sperner coloring.
2.2 The PPAD complexity class
The proof of Sperner’s lemma seen above distilled the problem of computing a trichromatic triangle
(and hence an approximate Brouwer fixed point) into the problem of finding the end of the line
connected component to which the bottom left cell belongs. In other words, approximate Brouwer
fixed points can be computed if one can follow quickly a line graph until the end. This is the essence
of the PPAD complexity class: a problem is in PPAD if it can be reduced to finding the end of a line
in a directed graph in which every node has indegree and outdegree at most 1, and a given start of
a line is given.
As just stated, the problem might seem kind of trivial: after all, why can’t we just follow the line until
the end? The problem is in the size of Sperner discretization that we need. Assuming the function
for which we need an 𝜖-approximate Brouwer fixed point is 1-Lischitz continuous, the size 𝑁 of the
Sperner coloring we need to consider is roughly of order 1/𝜖, where 𝜖 is the desired precision. This
quantity is exponentially large in the representation of 𝜖 specified in the input, which only takes
log(1/𝜖) bits to store.
★These notes are class material that has not undergone formal peer review. The TA and I are grateful for any
reports of typos.