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 ,1in 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 ,1/math>, 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 ,1/math> be the subset of all weights for which the theorem is true. Then:

# $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).
# If $w\in W$, then also $1-w \in W$. Proof: take $C_ := C\smallsetminus C_w$. If $C_w$ is a union of $n-1$ intervals in a circle, then $C_$ is also a union of $n-1$ intervals.
# $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.
# 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= ,1/math>. 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^n$:

:: f(t) = (t, t^2, \ldots, t^n)\,\,\,\,\,\,t\in ,1/math>

* Define the following measures on $\mathbb^n$:

:: $U_i(Y) = V_i(f^(Y) \cap C_w)\,\,\,\,\,\,\,\,\, Y\subseteq \mathbb^n$

* Note that $f^(\mathbb^n) = C$. Hence, for every partner $i$: $U_i(\mathbb^n) = w$.
* Hence, by the Stone–Tukey theorem, there is a hyper-plane that cuts $\mathbb^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^(H)\cap C_w$ and $M'=f^(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^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_=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_$.
* Define $n-1$ measures in the following way. Measure $i$ is concentrated in small neighbourhoods of the following $(n+1)$ points: $P_,P_,\ldots,P_$. So, near each point $P_$, 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

References

{{DEFAULTSORT:Stromquist-Woodall theorem
Cake-cutting
Theorems in measure theory