\documentclass[12pt]{article}
\usepackage{amsthm, amssymb, amsmath, amscd}
\setlength{\textwidth}{6.5in}
\setlength{\oddsidemargin}{0in}
\setlength{\textheight}{8.5in}
\setlength{\topmargin}{0in}
\setlength{\headheight}{0in}
\setlength{\headsep}{0in}
\setlength{\parskip}{0pt}
\setlength{\parindent}{20pt}

\def\H{\mathcal{H}}
\def\Hs{\H^{*}}
\def\CC{\mathbb{C}}
\def\FF{\mathbb{F}}
\def\NN{\mathbb{N}}
\def\QQ{\mathbb{Q}}
\def\RR{\mathbb{R}}
\def\ZZ{\mathbb{Z}}

\newtheorem{theorem}{Theorem}
\newtheorem{lemma}{Lemma}
\newtheorem{prop}{Proposition}

\begin{document}
        
\begin{center}
  \bf
Fixed Points and Fair Divisions \\
Berkeley Math Circle, November 11, 2001 \\
Kiran S. Kedlaya (Berkeley)
\end{center}

\textit{Caution: these notes were originally written for
graduate students, so you may find them tough reading at first. Hopefully
this will be a lot less true by the end of the talk!}
      
What do these two facts have in common?
\begin{enumerate}
        \item[(a)] If one copy of a map is crumpled up and placed on top of 
        a second, uncrumpled copy of the map, then there is a location whose 
        image on the crumpled map lies directly over its image on the 
        uncrumpled map.
        \item[(b)] Any group of people can divide a cake amongst themselves 
        so that each person believes her piece is the biggest.
\end{enumerate}
The former is of course the Brouwer Fixed-Point Theorem (in two 
dimensions), while the latter is known to some economists as the Fair 
Division Theorem (or more precisely, the Envy-Free Fair Division 
Theorem). The overt purpose of this talk is to illustrate the close 
relationship between these two results, and in particular their common 
genesis from a combinatorial result known as Sperner's Lemma. The secret purpose
is to motivate people to think more about this connection, since at present it
lacks a certain ``naturality'' that I think is hidden somewhere, and ought to be
brought to the fore.
        
Advertisement: the entire contents of this talk are shamelessly 
lifted from the article ``Rental Harmony: Sperner's Lemma in Fair 
Division'' by Francis Su, in the December 1999 \textit{American 
Mathematical Monthly}, pp.\ 930--942. You can play around with the fair
division algorithms in this talk using a Java applet at his web site:
\begin{center}
\verb+http://www.math.hmc.edu/~su/fairdivision/+
\end{center}
        
Before proceeding, let us fix some definitions. The \emph{simplex in $\RR^n$}
is the set $\{(x_1, \dots, x_{n}): 0 \leq x_i,
\sum x_i = 1\}$. We number the vertices so that vertex $i$ is the one with nonzero
$i$-th coordinate.
The \emph{facets} of this simplex are its intersections with
its supporting hyperplanes; a codimension 1 facet is also called a \emph{face}.
We number the faces so face $i$ is opposite vertex $i$.
A \emph{triangulation} of the simplex is 
a covering of the simplex with subsimplices, such that if two subsimplices intersect,
their intersection is a $k$-facet of each of the two, for some $k < n-1$.
\begin{lemma}[Sperner's Lemma]
        Consider a triangulation of the simplex in $\RR^n$,
        whose subvertices are each labeled with 
        one of $1, \dots, n+1$, subject to the restriction that each subvertex 
        lying on the facet of the simplex with vertices $a_{1}, \dots, 
        a_{k}$ is itself labeled with one of $a_{1}, \dots, a_{k}$. Then 
        the number of subsimplices whose subvertices are labeled $1, \dots, n+1$
        is odd and thus nonzero. (If counted with 
        orientation, the number is equal to $1$.)
\end{lemma}
We defer the proof for the time being. For now, let us see how this 
lemma implies both the Fixed Point Theorem and the Fair Division 
Theorem.

\begin{theorem}[Fixed Point Theorem]
        Any continuous map from the simplex in $\RR^n$ to itself has a fixed point.
\end{theorem}
\begin{proof}[Proof of the Fixed Point Theorem.]
        For $\epsilon > 0$, construct a triangulation such that no two 
        points within a subsimplex have any coordinate differing by 
        $\epsilon$ or greater, or map to points with any coordinate 
        differing by $\epsilon$ or 
        greater. Label each subvertex $x$ with a number $i$ such 
        that the $i$-th coordinate of $x$ is nonzero, and is greater than or
        equal to the $i$-th coordinate of $f(x)$.
        This labeling is a Sperner labeling: on 
        the facet with vertices $a_{1}, \dots, a_{k}$, only these coordinates 
        are nonzero. Thus there 
        exists a subsimplex labeled $1, \dots, n$. No point in this subsimplex 
        can move to a point with a coordinate increased by $2\epsilon$ or 
        more, since there is a point in the simplex for which this coordinate 
        decreases.
        
        By compactness,
        there is a sequence of $\epsilon$ tending to 0 whose corresponding
        subsimplices have nonempty intersection. Any point in this 
        intersection must map to itself (since none of its coordinates can
        increase by more than $2\epsilon$ for arbitrarily small $\epsilon$).
\end{proof}

\begin{theorem}[Envy-Free Fair Division Theorem]
Consider a one-dimensional cake to be divided into $n$ pieces by $n-1$ 
cuts. From each possible division, each of $n$ players designates one 
or more pieces as ``preferred''. These preferences obey the following rules:
\begin{enumerate}
        \item[(a)] Continuity: If a player prefers a piece in each of a set 
        of divisions, he prefers that piece in each limiting division.
        \item[(b)] Boundary condition: No player ever prefers an empty piece.
\end{enumerate}
Then there exists a division and an assignment of each piece to a 
different player, such that each player receives one of his preferred 
pieces.
\end{theorem}

Beware that the well-known ``moving-knife'' method does not suffice to prove this result.
In that method, a knife is drawn sideways across the cake; as soon as a player 
believes the knife has covered $1/n$ of the cake, he signals the knife-mover to
cut and takes the resulting piece. The remaining players then repeat the procedure
until each player receives a piece. This method guarantees that each player 
receives at least $1/n$ of the cake in his own measure (since he believes the pieces
cut off before the one he receives are smaller than $1/n$, so even if he gets the
last piece, it will have size at least $1/n$).

There are two reasons why our result is stronger than that given by
the moving-knife method. First, our theorem does not assume that players' preferences
are given by measures on the cake. For example, if $n=4$, a player could prefer 
piece 1 in one division, and piece 2 in a division that differs from the first only
in the sizes of pieces 3 and 4! Second, even if the preferences are given by
measures, the moving-knife method only guarantees that a player receives a piece as
least as large as the average piece, and not necessarily the biggest piece (this is
why our theorem is called ``envy-free'').

\begin{proof}[Proof of the Fair Division Theorem]
        (due to Forest Simmons)
        Identify the possible divisions with the simplex in $\RR^n$,
        so that vertex $i$ corresponds to all of the cake lying in piece $i$.
        For $\epsilon > 0$, construct a triangulation of the simplex such 
        that no two subvertices are at distance $\epsilon$ or greater, and
        which can be labeled by the names of the players so that \emph{each} 
        subsimplex has subvertices labeled by the names of all of the players.
        (Given a
        triangulation satisfying the first condition, its barycentric 
        subdivision satisfies both conditions: for each of $k=0,\dots, n-1$,
        label all of the barycenters of $k$-simplices with a single player.)
        
        Now 
        construct a second labeling of this triangulation as follows: for 
        each subvertex, query the player whose name labels that subvertex, 
        and label the subvertex with one of his preferred pieces in the 
        corresponding division. The result is a 
        Sperner labeling, since on the facet with vertices $a_{1}, \dots, 
        a_{k}$, only pieces $a_{1}, \dots, a_{k}$ are nonempty, so only they 
        will be preferred. Thus there exists a subsimplex labeled $1, \dots, 
        n+1$, which is to say, a subsimplex where each player chooses a 
        different piece at his corresponding subvertex.
        
        By compactness (and the finiteness of the number of ways for the
        players to choose pieces), there exists a sequence of $\epsilon$
        tending to 0 such that the corresponding subsimplices have
        nonempty intersection, and such that each player chooses the same
        piece each time his name occurs as the label of a subvertex.
        A point in that intersection is a division in 
        which each player prefers a different piece, as desired.
\end{proof}

\begin{proof}[Proof of Sperner's Lemma]
        We proceed by induction on $n$. By the induction hypothesis, the 
        face with vertices $1, \dots, n-1$ has been given a Sperner 
        labeling and so contains an odd number of subsimplices labeled $1, 
        \dots, n-1$.
        
        We refer to each subface labeled $1, \dots, n-1$ as a 
        \emph{door}. We have just seen that there are an odd number of doors 
        on the boundary of the simplex. Moreover, each subsimplex 
        contains 1 door if it is labeled $1, \dots, n$, and 0 or 2 doors 
        otherwise. 
        
        Now consider the graph on the subsimplices, which are considered
        adjacent if they share a common subface which is also a door.
        This graph is a disjoint set of paths of two types: those 
        starting and ending on the boundary, and those starting on the 
        boundary and ending at a subsimplex labeled $1, \dots, n$. Since each 
        path of the former type uses two boundary doors, there are an odd 
        number of the second type, and so an odd number of subsimplices labeled 
        $1, \dots, n$.
\end{proof}
The algorithmic nature of this proof yields approximate algorithms 
for finding fixed points and fair divisions.

The Fair Division Theorem concerns division of benefits. What about 
the dual situation, where players must divide a certain cost? For 
example, if $n$ graduate students share an apartment, and decide to 
divide the rent by room, can this division be set so that each 
person will opt for a different room? As we shall see, Sperner's 
lemma, or rather a dual incarnation of it, can answer this question as 
well.

\begin{theorem}[Rental Division Theorem]
        Consider $n$ rooms and a total rent to be divided among the rooms. 
        For each such division, each of $n$ players designates one or more 
        rooms as ``preferred''. These 
        preferences obey the following rules:
        \begin{enumerate}
        \item[(a)] Continuity: If a player prefers a piece in each of a set 
        of divisions, he prefers that piece in each limiting division.
        \item[(b)] Boundary condition: If there is a room with rent at most $0$,
        no player will prefer a room with positive rent.
        \end{enumerate}
        Then there exists a division and an assignment of each room to a 
different player, such that each player receives one of his preferred 
rooms.
\end{theorem}
\begin{lemma}[Dual Sperner's Lemma]
        Consider a triangulation of the simplex in $\RR^n$,
        whose subvertices are each labeled with 
        one of $1, \dots, n$, subject to the restriction that each subvertex 
        lying on the intersection of faces $a_{1}, \dots, 
        a_{k}$ is itself labeled with one of $a_{1}, \dots, a_{k}$. Assume 
        moreover that each facet contains a subvertex in its interior. Then
        the number of subsimplices whose vertices are labeled $1, \dots, n$
        is odd and thus nonzero.
\end{lemma}

\begin{proof}[Proof of Dual Sperner's Lemma]
        As in the proof of Sperner's Lemma, it suffices to show that the 
        number of doors on the
        boundary of the simplex is odd. Note that a door must have at least
        one subvertex on each of faces $1, \dots, n-1$. This restriction, 
        together with the condition that the door lies on the boundary, forces
        the vertex at the intersection of faces $1, \dots, n-1$ to be a 
        subvertex of the door. Without loss of generality suppose this vertex 
        is labeled $n-1$. Then of the other subvertices of the door, one must 
        lie on each of face $1, \dots, n-2$, and so the door must have a 
        second subvertex on the intersection of face $1, \dots, n-2$. 
        Repeating this argument shows that in fact there is exactly one door 
        on the boundary of the simplex. Thus there are an odd number of 
        subsimplices labeled $1, \dots, n$ by the same argument as above.
\end{proof}
\begin{proof}[Proof of the Rental Division Theorem]
        Identify the possible divisions with the simplex in $\RR^{n}$,
        so that the $i$-th coordinate represents the price of room $i$,
        triangulated as in the proof of the Fair Division Theorem.
        For $\epsilon > 0$, construct a triangulation of the simplex such 
        that no two subvertices are at distance $\epsilon$ or greater, and which 
        can be labeled by the names of the players so that \emph{each} 
        subsimplex is labeled with the names of all of the players.
        
        Now 
        construct a second labeling of this triangulation as follows: for 
        each subvertex, query the player whose name labels that subvertex, 
        and label the subvertex with one of that player's preferred rooms in 
        the corresponding division. This new labeling is a dual Sperner 
        labeling: on the intersection of facets $a_{1}, \dots, a_{k}$, 
        rooms $a_{1}, \dots, a_{k}$ have zero rent and so no other rooms will 
        be preferred. Thus the Dual Sperner's Lemma implies the existence of 
        a subsimplex labeled $1, \dots, n$. The remainder of the argument 
        is the same as that of the Fair Division Theorem.
\end{proof}

In conclusion, it should be noted that other results from topology
also yield fair division results, and more specifically results in combinatorial
topology yield approximate algorithms for fair division problems.
For example, the Borsuk-Ulam theorem
(any map from the $n$-sphere to $\RR^{n}$ maps some pair of antipodal
points to the same point) yields the fact that a cake can be divided
in two so that each of $n$ people prefers both pieces equally. (The
proof of the latter is similar to that of the Ham Sandwich Theorem.)

On the other hand, the correspondence between topology and fair division is
not completely understood; we have fragmentary results, but no unifying
treatment.

\end{document}
