Dubins–Spanier theorems
Dubins–Spanier theorems
The Dubins–Spanier theorems are several theorems in the theory of fair-cake-cutting. They were published by lester-dubins and edwin-spanier in 1961. Although the original motivation for these theorems is fair-division, they are in fact general theorems in measure theory.
Setting There is a set <math>U</math>, and a set <math>\mathbb{U}</math> which is a sigma-algebra of subsets of <math>U</math>.
There are <math>n</math> partners. Every partner <math>i</math> has a personal value measure <math>V_i: \mathbb{U} \to \mathbb{R}</math>. This function determines how much each subset of <math>U</math> is worth to that partner.
Let <math>X</math> a partition of <math>U</math> to <math>k</math> measurable sets: <math>U = X_1 \sqcup \cdots \sqcup X_k</math>. Define the matrix <math>M_X</math> as the following <math>n\times k</math> matrix:
:<math>M_X[i,j] = V_i(X_j)</math>
This matrix contains the valuations of all players to all pieces of the partition.
Let <math>\mathbb{M}</math> be the collection of all such matrices (for the same value measures, the same <math>k</math>, and different partitions): :<math>\mathbb{M} = \{M_X \mid X\text{ is a }k\text{-partition of } U\}</math>
The Dubins–Spanier theorems deal with the topological properties of <math>\mathbb{M}</math>.
Statements If all value measures <math>V_i</math> are countably-additive and nonatomic, then:
- <math>\mathbb{M}</math> is a compact set;
- <math>\mathbb{M}</math> is a convex set.
This was already proved by Dvoretzky, Wald, and Wolfowitz.
Corollaries ### Consensus partition A cake partition <math>X</math> to k pieces is called a consensus partition with weights <math>w_1, w_2, \ldots, w_k</math> (also called exact division) if: :<math>\forall i \in \{1,\dots, n\}: \forall j \in \{1,\dots, k\}: V_i(X_j) = w_j</math> I.e, there is a consensus among all partners that the value of piece j is exactly <math>w_j</math>.
Suppose, from now on, that <math>w_1, w_2, \ldots, w_k</math> are weights whose sum is 1: :<math>\sum_{j=1}^k w_j =1</math> and the value measures are normalized such that each partner values the entire cake as exactly 1: :<math>\forall i \in \{1,\dots, n\}: V_i(U) = 1</math>
The convexity part of the DS theorem implies that: