Proof.
For
d
= 1, this is obvious: In a string of bits that starts with 0 and
ends with 1, the number of bit flips is odd.
For
d
= 2, we will count in two ways the set
Q
of pairs consisting of a small
triangle and an edge labeled 12 on that triangle.
Let
A
12
denote the number of
12labeled edges of small triangles that lie on the boundary of the big triangle. Let
B
12
be the number of such edges in the interior. Let
N
abc
denote the number of
small triangles where the three labels are
a
,
b
and
c
. Note that
N
012
+ 2
N
112
+ 2
N
122
=

Q

=
A
12
+ 2
B
12
,
because the lefthand side counts the contribution to
Q
from each small triangle
and the righthand side counts the contribution to
Q
from each 12labeled edge.
From the case
d
= 1, we know that
A
12
is odd, and hence
N
012
is odd too.
For another proof, see Figure 5.3.
Remark
5.2.5
.
Sperner’s Lemma can be generalized to higher dimensions. See
§
5.4.
5.2.3. Brouwer’s FixedPoint Theorem.
Definition
5.2.6
.
A set
S
⊆
R
d
has the
fixedpoint property
(abbreviated
f.p.p.
)
if for any continuous function
T
:
S
→
S
, there exists
x
∈
S
such that
T
(
x
) =
x
.
Brouwer’s Theorem asserts that every closed, bounded, convex set
K
⊂
R
d
has
the f.p.p. Each of the hypotheses on
K
in the theorem is needed, as the following
examples show:
(1)
K
=
R
(closed, convex, not bounded) with
T
(
x
) =
x
+ 1.
(2)
K
= (0
,
1) (bounded, convex, not closed) with
T
(
x
) =
x/
2.
(3)
K
=
x
∈
R
:

x
 ∈
[1
,
2]
(bounded, closed, not convex) with
T
(
x
) =

x
.
Remark
5.2.7
.
On first reading of the following proof, the reader should take
n
= 2.
In two dimensions, simplices are triangles.
To understand the proof for
n >
2,
§
5.4 should be read first.
Theorem
5.2.8 (
Brouwer’s FixedPoint Theorem for the Simplex
)
.
The
standard
n
simplex
Δ =
{
x

∑
n
i
=0
x
i
= 1
,
∀
i x
i
≥
0
}
has the fixedpoint property.
Proof.
Let Γ be a subdivision (as in Sperner’s Lemma) of Δ where all triangles
(or, in higher dimension, simplices) have diameter at most
. Given a continuous
106
5. EXISTENCE OF NASH EQUILIBRIA AND FIXED POINTS
*
Figure 5.3.
Sperner’s Lemma: The left side of the figure shows a la
beling and the three fully labeled subtriangles it induces. The right side
of the figure illustrates an alternative proof of the case
d
= 2: Construct
a graph
G
with a node inside each small triangle, as well as a vertex
outside each 13 labeled edge on the outer right side of the big trian
gle. Put an edge in
G
between each pair of vertices separated only by
a 13 labeled edge. In the resulting graph
G
(whose edges are shown in
PURPLE), each vertex has degree either 0, 1 or 2, so the graph con
sists of paths and cycles. Moreover, each vertex outside the big triangle
has degree 0 or 1, and an odd number of these vertices have degree 1.
Therefore, at least one (in fact an odd number) of the paths starting at
these degree 1 vertices must end at a vertex interior to the large triangle.
Each of the latter vertices lies inside a properly labeled small triangle.