Stromquist–Woodall theorem

game-theory 1454 tokens 3 outbound links

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 <math>2n-2</math> cuts.

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: <math>V_1,\ldots,V_n</math>; each measure represents the valuations of a different person over subsets of the cake. The theorem says that, for every weight <math>w \in [0,1]</math>, there is a subset <math>C_w</math>, which all people value at exactly <math>w</math>:

: <math>\forall i = 1,\ldots,n: \,\,\,\,\, V_i(C_w)=w</math>, where <math>C_w</math> is a union of at most <math>n-1</math> intervals. This means that <math>2n-2</math> cuts are sufficient for cutting the subset <math>C_w</math>. If the cake is not circular (that is, the endpoints are not identified), then <math>C_w</math> may be the union of up to <math>n</math> intervals, in case one interval is adjacent to 0 and one other interval is adjacent to 1.

Proof sketch Let <math>W \subseteq [0,1]</math> be the subset of all weights for which the theorem is true. Then:

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

From 1-4, it follows that <math>W=[0,1]</math>. In other words, the theorem is valid for every possible weight.

Proof sketch for part 4 * Assume that <math>C_w</math> is a union of <math>n-1</math> intervals and that all <math>n</math> partners value it as exactly <math>w</math>. * Define the following function on the cake, <math>f: C \to \mathbb{R}^n</math>:

:: <math>f(t) = (t, t^2, \ldots, t^n)\,\,\,\,\,\,t\in[0,1]</math>

Define the following measures on <math>\mathbb{R}^n</math>:

:: <math>U_i(Y) = V_i(f^{-1}(Y) \cap C_w)\,\,\,\,\,\,\,\,\, Y\subseteq \mathbb{R}^n</math>

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

:: <math>\forall i = 1,\ldots,n: \,\,\,\,\, U_i(H)=U_i(H')=w/2</math>

Define <math>M=f^{-1}(H)\cap C_w</math> and <math>M'=f^{-1}(H')\cap C_w</math>. Then, by the definition of the <math>U_i</math>:

:: <math>\forall i = 1,\ldots,n: \,\,\,\,\, V_i(M)=V_i(M')=w/2</math>

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

Tightness proof Stromquist and Woodall prove that the number <math>n-1</math> is tight if the weight <math>w</math> is either irrational, or rational with a reduced fraction <math>r/s</math> such that <math>s\geq n</math>.

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

Stromquist–Woodall theorem