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 [math]\displaystyle{ 2n-2 }[/math] 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: [math]\displaystyle{ V_1,\ldots,V_n }[/math]; each measure represents the valuations of a different person over subsets of the cake. The theorem says that, for every weight [math]\displaystyle{ w \in [0,1] }[/math], there is a subset [math]\displaystyle{ C_w }[/math], which all people value at exactly [math]\displaystyle{ w }[/math]:

[math]\displaystyle{ \forall i = 1,\ldots,n: \,\,\,\,\, V_i(C_w)=w }[/math],

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

Proof sketch

Let [math]\displaystyle{ W \subseteq [0,1] }[/math] be the subset of all weights for which the theorem is true. Then:

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

From 1-4, it follows that [math]\displaystyle{ W=[0,1] }[/math]. In other words, the theorem is valid for every possible weight.

Proof sketch for part 4

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

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

• Define the following measures on [math]\displaystyle{ \mathbb{R}^n }[/math]:

[math]\displaystyle{ U_i(Y) = V_i(f^{-1}(Y) \cap C_w)\,\,\,\,\,\,\,\,\, Y\subseteq \mathbb{R}^n }[/math]

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

[math]\displaystyle{ \forall i = 1,\ldots,n: \,\,\,\,\, U_i(H)=U_i(H')=w/2 }[/math]

• Define [math]\displaystyle{ M=f^{-1}(H)\cap C_w }[/math] and [math]\displaystyle{ M'=f^{-1}(H')\cap C_w }[/math]. Then, by the definition of the [math]\displaystyle{ U_i }[/math]:

[math]\displaystyle{ \forall i = 1,\ldots,n: \,\,\,\,\, V_i(M)=V_i(M')=w/2 }[/math]

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

Tightness proof

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

Proof sketch for [math]\displaystyle{ w=1/n }[/math]

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

See also

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