Jump to content

Stromquist–Woodall theorem

From Wikipedia, the free encyclopedia
(Redirected from 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.