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 $2n-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 $2n-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).
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.
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 \mathbb {R} ^{n}$ :

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

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

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

Note that $f^{-1}(\mathbb {R} ^{n})=C$ . Hence, for every partner $i$ : $U_{i}(\mathbb {R} ^{n})=w$ .
Hence, by the Stone–Tukey theorem, there is a hyper-plane that cuts $\mathbb {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 $\mathbb {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 $2n-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/{\big (}(n+1)(n-1){\big )}$ ; 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.

References

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.

This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.

[stromquistwoodall85-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.