Stromquist–Woodall theorem

The Stromquist–Woodall theorem is a theorem in fair division and measure theory. Informally, it says that, for any cake, for any n people with different tastes, and for any fraction w, there exists a subset of the cake that all people value at exactly a fraction w of the total cake value, and it can be cut using at most $2n-2$ cuts.

The theorem is about a circular 1-dimensional cake (a "pie"). Formally, it can be described as the interval [0,1] in which the two endpoints are identified. There are n continuous measures over the cake: $V_{1},\ldots ,V_{n}$; each measure represents the valuations of a different person over subsets of the cake. The theorem says that, for every weight $w\in [0,1]$, there is a subset $C_{w}$, which all people value at exactly $w$:

$\forall i=1,\ldots ,n:\,\,\,\,\,V_{i}(C_{w})=w$,

where $C_{w}$ is a union of at most $n-1$ intervals. This means that $2n-2$ cuts are sufficient for cutting the subset $C_{w}$. If the cake is not circular (that is, the endpoints are not identified), then $C_{w}$ may be the union of up to $n$ intervals, in case one interval is adjacent to 0 and one other interval is adjacent to 1.

Proof sketch

Let $W\subseteq [0,1]$ be the subset of all weights for which the theorem is true. Then:

1. $1\in W$. Proof: take $C_{1}:=C$ (recall that the value measures are normalized such that all partners value the entire cake as 1).
2. If $w\in W$, then also $1-w\in W$. Proof: take $C_{1-w}:=C\smallsetminus C_{w}$. If $C_{w}$ is a union of $n-1$ intervals in a circle, then $C_{1-w}$ is also a union of $n-1$ intervals.
3. $W$ is a closed set. This is easy to prove, since the space of unions of $n-1$ intervals is a compact set under a suitable topology.
4. If $w\in W$, then also $w/2\in W$. This is the most interesting part of the proof; see below.

From 1-4, it follows that $W=[0,1]$. In other words, the theorem is valid for every possible weight.

Proof sketch for part 4

• Assume that $C_{w}$ is a union of $n-1$ intervals and that all $n$ partners value it as exactly $w$.
• Define the following function on the cake, $f:C\to \mathbb {R} ^{n}$:

$f(t)=(t,t^{2},\ldots ,t^{n})\,\,\,\,\,\,t\in [0,1]$

• Define the following measures on $\mathbb {R} ^{n}$:

$U_{i}(Y)=V_{i}(f^{-1}(Y)\cap C_{w})\,\,\,\,\,\,\,\,\,Y\subseteq \mathbb {R} ^{n}$

• Note that $f^{-1}(\mathbb {R} ^{n})=C$. Hence, for every partner $i$: $U_{i}(\mathbb {R} ^{n})=w$.
• Hence, by the Stone–Tukey theorem, there is a hyper-plane that cuts $\mathbb {R} ^{n}$ to two half-spaces, $H,H'$, such that:

$\forall i=1,\ldots ,n:\,\,\,\,\,U_{i}(H)=U_{i}(H')=w/2$

• Define $M=f^{-1}(H)\cap C_{w}$ and $M'=f^{-1}(H')\cap C_{w}$. Then, by the definition of the $U_{i}$:

$\forall i=1,\ldots ,n:\,\,\,\,\,V_{i}(M)=V_{i}(M')=w/2$

• The set $C_{w}$ has $n-1$ connected components (intervals). Hence, its image $f(C_{w})$ also has $n-1$ connected components (1-dimensional curves in $\mathbb {R} ^{n}$).
• The hyperplane that forms the boundary between $H$ and $H'$ intersects $f(C_{w})$ in at most $n$ points. Hence, the total number of connected components (curves) in $H\cap f(C_{w})$ and $H'\cap f(C_{w})$ is $2n-1$. Hence, one of these must have at most $n-1$ components.
• Suppose it is $H$ that has at most $n-1$ components (curves). Hence, $M$ has at most $n-1$ components (intervals).
• Hence, we can take $C_{w/2}=M$. This proves that $w\in W$.

Tightness proof

Stromquist and Woodall prove that the number $n-1$ is tight if the weight $w$ is either irrational, or rational with a reduced fraction $r/s$ such that $s\geq n$.

Proof sketch for $w=1/n$

• Choose $(n-1)(n+1)$ equally-spaced points along the circle; call them $P_{1},\ldots ,P_{(n-1)(n+1)}$.
• Define $n-1$ measures in the following way. Measure $i$ is concentrated in small neighbourhoods of the following $(n+1)$ points: $P_{i},P_{i+(n-1)},\ldots ,P_{i+n(n-1)}$. So, near each point $P_{i+k(n-1)}$, there is a fraction $1/(n+1)$ of the measure $u_{i}$.
• Define the $n$-th measure as proportional to the length measure.
• Every subset whose consensus value is $1/n$, must touch at least two points for each of the first $n-1$ measures (since the value near each single point is $1/(n+1)$ which is slightly less than the required $1/n$). Hence, it must touch at least $2(n-1)$ points.
• On the other hand, every subset whose consensus value is $1/n$, must have total length $1/n$ (because of the $n$-th measure). The number of "gaps" between the points is $1/{\big (}(n+1)(n-1){\big )}$; hence the subset can contain at most $n-1$ gaps.
• The consensus subset must touch $2(n-1)$ points but contain at most $n-1$ gaps; hence it must contain at least $n-1$ intervals.

See also

• Fair cake-cutting
• Fair pie-cutting
• Exact division
• Stone–Tukey theorem