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 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: ; each measure represents the valuations of a different person over subsets of the cake. The theorem says that, for every weight , there is a subset , which all people value at exactly :

,

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

Proof sketch

edit

Let   be the subset of all weights for which the theorem is true. Then:

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

From 1-4, it follows that  . In other words, the theorem is valid for every possible weight.

Proof sketch for part 4

edit
  • Assume that   is a union of   intervals and that all   partners value it as exactly  .
  • Define the following function on the cake,  :
 
  • Define the following measures on  :
 
  • Note that  . Hence, for every partner  :  .
  • Hence, by the Stone–Tukey theorem, there is a hyper-plane that cuts   to two half-spaces,  , such that:
 
  • Define   and  . Then, by the definition of the  :
 
  • The set   has   connected components (intervals). Hence, its image   also has   connected components (1-dimensional curves in  ).
  • The hyperplane that forms the boundary between   and   intersects   in at most   points. Hence, the total number of connected components (curves) in   and   is  . Hence, one of these must have at most   components.
  • Suppose it is   that has at most   components (curves). Hence,   has at most   components (intervals).
  • Hence, we can take  . This proves that  .

Tightness proof

edit

Stromquist and Woodall prove that the number   is tight if the weight   is either irrational, or rational with a reduced fraction   such that  .

Proof sketch for  

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

See also

edit

References

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