Stromquist–Woodall theorem explained

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

2 n -2 cuts.^[1]

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 2 n -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 \in W . Proof: take C _{1} : = C (recall that the value measures are normalized such that all partners value the entire cake as 1).

1. 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.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.

1. 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 R ^{n} :f(t) = (t, t ^{2,} \ldots, t ^{n)t\in[0,1]}

• Define the following measures on

R ^{n} :U _{i(Y)} = V ^{-1} _{i(f} (Y) \cap C _{w)} Y\subseteq R ^{n}

• Note that

f ^{-1} ( R ^{n)} = C . Hence, for every partner i : U ^{n)} _{i( R} = w .

• Hence, by the Stone–Tukey theorem, there is a hyper-plane that cuts

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 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 2 n -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 / ( (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

Notes and References

1. Stromquist. Walter. Woodall. D.R. 1985. Sets on which several measures agree. Journal of Mathematical Analysis and Applications. 108. 241–248. 10.1016/0022-247x(85)90021-6.