Misplaced Pages

This article only references primary sources. Please help improve this article by adding secondary or tertiary sources. Find sources: "Stromquist–Woodall theorem" – news · newspapers · books · scholar · JSTOR (November 2022) (Learn how and when to remove this message)

This article relies largely or entirely on a single source. Relevant discussion may be found on the talk page. Please help improve this article by introducing citations to additional sources. Find sources: "Stromquist–Woodall theorem" – news · newspapers · books · scholar · JSTOR (November 2022)

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 ${\displaystyle 2n-2}$ cuts.

The theorem is about a circular 1-dimensional cake (a "pie"). Formally, it can be described as the interval in which the two endpoints are identified. There are n continuous measures over the cake: ${\displaystyle 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 ${\displaystyle w\in }$, there is a subset ${\displaystyle C_{w}}$, which all people value at exactly ${\displaystyle w}$:

${\displaystyle \forall i=1,\ldots ,n:\,\,\,\,\,V_{i}(C_{w})=w}$,

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

Proof sketch

Let ${\displaystyle W\subseteq }$ be the subset of all weights for which the theorem is true. Then:

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

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

Proof sketch for part 4

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

${\displaystyle f(t)=(t,t^{2},\ldots ,t^{n})\,\,\,\,\,\,t\in }$

• Define the following measures on ${\displaystyle \mathbb {R} ^{n}}$:

${\displaystyle U_{i}(Y)=V_{i}(f^{-1}(Y)\cap C_{w})\,\,\,\,\,\,\,\,\,Y\subseteq \mathbb {R} ^{n}}$

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

${\displaystyle \forall i=1,\ldots ,n:\,\,\,\,\,U_{i}(H)=U_{i}(H')=w/2}$

• Define ${\displaystyle M=f^{-1}(H)\cap C_{w}}$ and ${\displaystyle M'=f^{-1}(H')\cap C_{w}}$. Then, by the definition of the ${\displaystyle U_{i}}$:

${\displaystyle \forall i=1,\ldots ,n:\,\,\,\,\,V_{i}(M)=V_{i}(M')=w/2}$

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

Tightness proof

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

Proof sketch for ${\displaystyle w=1/n}$

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

See also

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

References

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.

• Cake-cutting
• Theorems in measure theory