Stromquist–Woodall theorem

Template:Only primary sources Template:One source 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,\dots ,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$:

$\mathrm{\forall }i=1,\dots ,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\setminus 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 {ℝ}^n$:

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

• Define the following measures on ${ℝ}^n$:

$U_i(Y)=V_i(f^{-1}(Y)\cap C_w)Y\subseteq {ℝ}^n$

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

$\mathrm{\forall }i=1,\dots ,n:U_i(H)=U_i(H^{\prime })=w/2$

• Define $M=f^{-1}(H)\cap C_w$ and $M^{\prime }=f^{-1}(H^{\prime })\cap C_w$. Then, by the definition of the $U_i$:

$\mathrm{\forall }i=1,\dots ,n:V_i(M)=V_i(M^{\prime })=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 ${ℝ}^n$).
• The hyperplane that forms the boundary between $H$ and $H^{\prime }$ 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^{\prime }\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\ge n$.

Proof sketch for $w=1/n$

• Choose $(n-1)(n+1)$ equally-spaced points along the circle; call them $P_1,\dots ,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)},\dots ,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/((n+1)(n-1))$; 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