Английская Википедия:Dubins–Spanier theorems
Шаблон:Short description 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.[1] 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. [2]
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:[1]Шаблон:Rp
- If all value measures are countably-additive and nonatomic,
- then a consensus partition exists.
PROOF: For every <math>j \in \{1,\dots, k\}</math>, define a partition <math>X^j</math> as follows:
- <math>X^j_j = U</math>
- <math>\forall r\neq j: X^j_r = \emptyset</math>
In the partition <math>X^j</math>, all partners value the <math>j</math>-th piece as 1 and all other pieces as 0. Hence, in the matrix <math>M_{X^j}</math>, there are ones on the <math>j</math>-th column and zeros everywhere else.
By convexity, there is a partition <math>X</math> such that:
- <math>M_X = \sum_{j=1}^k w_j\cdot M_{X^j}</math>
In that matrix, the <math>j</math>-th column contains only the value <math>w_j</math>. This means that, in the partition <math>X</math>, all partners value the <math>j</math>-th piece as exactly <math>w_j</math>.
Note: this corollary confirms a previous assertion by Hugo Steinhaus. It also gives an affirmative answer to the problem of the Nile provided that there are only a finite number of flood heights.
Super-proportional division
A cake partition <math>X</math> to n pieces (one piece per partner) is called a super-proportional division with weights <math>w_1, w_2, ..., w_n</math> if:
- <math>\forall i \in 1\dots n: V_i(X_i) > w_i</math>
I.e, the piece allotted to partner <math>i</math> is strictly more valuable for him than what he deserves. The following statement is Dubins-Spanier Theorem on the existence of super-proportional division Шаблон:Rp
The hypothesis that the value measures <math> V_1, ..., V_n</math> are not identical is necessary. Otherwise, the sum <math> \sum_{i=1}^n V_i(X_i) =\sum_{i=1}^n V_1(X_i) > \sum_{i=1}^n w_i =1</math> leads to a contradiction.
Namely, if all value measures are countably-additive and non-atomic, and if there are two partners <math>i,j</math> such that <math>V_i\neq V_j</math>, then a super-proportional division exists.I.e, the necessary condition is also sufficient.
Sketch of Proof
Suppose w.l.o.g. that <math>V_1 \neq V_2</math>. Then there is some piece of the cake, <math>Z\subseteq U</math>, such that <math>V_1(Z)>V_2(Z)</math>. Let <math>\overline{Z}</math> be the complement of <math>Z</math>; then <math>V_2(\overline{Z})>V_1(\overline{Z})</math>. This means that <math>V_1(Z) + V_2(\overline{Z}) > 1</math>. However, <math>w_1+w_2\leq 1</math>. Hence, either <math>V_1(Z)>w_1</math> or <math>V_2(\overline{Z})>w_2</math>. Suppose w.l.o.g. that <math>V_1(Z)>V_2(Z)</math> and <math>V_1(Z)>w_1</math> are true.
Define the following partitions:
- <math>X^1</math>: the partition that gives <math>Z</math> to partner 1, <math>\overline{Z}</math> to partner 2, and nothing to all others.
- <math>X^i</math> (for <math>i\geq 2</math>): the partition that gives the entire cake to partner <math>i</math> and nothing to all others.
Here, we are interested only in the diagonals of the matrices <math>M_{X^j}</math>, which represent the valuations of the partners to their own pieces:
- In <math>\textrm{diag}(M_{X^1})</math>, entry 1 is <math>V_1(Z)</math>, entry 2 is <math>V_2(\overline{Z})</math>, and the other entries are 0.
- In <math>\textrm{diag}(M_{X^i})</math> (for <math>i\geq 2</math>), entry <math>i</math> is 1 and the other entires are 0.
By convexity, for every set of weights <math>z_1, z_2, ..., z_n</math> there is a partition <math>X</math> such that:
- <math>M_X = \sum_{j=1}^n {z_j\cdot M_{X^j}}.</math>
It is possible to select the weights <math>z_i</math> such that, in the diagonal of <math>M_X</math>, the entries are in the same ratios as the weights <math>w_i</math>. Since we assumed that <math>V_1(Z)>w_1</math>, it is possible to prove that <math>\forall i \in 1\dots n: V_i(X_i) > w_i</math>, so <math>X</math> is a super-proportional division.
Utilitarian-optimal division
A cake partition <math>X</math> to n pieces (one piece per partner) is called utilitarian-optimal if it maximizes the sum of values. I.e, it maximizes:
- <math>\sum_{i=1}^n{V_i(X_i)}</math>
Utilitarian-optimal divisions do not always exist. For example, suppose <math>U</math> is the set of positive integers. There are two partners. Both value the entire set <math>U</math> as 1. Partner 1 assigns a positive value to every integer and partner 2 assigns zero value to every finite subset. From a utilitarian point of view, it is best to give partner 1 a large finite subset and give the remainder to partner 2. When the set given to partner 1 becomes larger and larger, the sum-of-values becomes closer and closer to 2, but it never approaches 2. So there is no utilitarian-optimal division.
The problem with the above example is that the value measure of partner 2 is finitely-additive but not countably-additive.
The compactness part of the DS theorem immediately implies that:[1]Шаблон:Rp
- If all value measures are countably-additive and nonatomic,
- then a utilitarian-optimal division exists.
In this special case, non-atomicity is not required: if all value measures are countably-additive, then a utilitarian-optimal partition exists.[1]Шаблон:Rp
Leximin-optimal division
A cake partition <math>X</math> to n pieces (one piece per partner) is called leximin-optimal with weights <math>w_1, w_2, ..., w_n</math> if it maximizes the lexicographically-ordered vector of relative values. I.e, it maximizes the following vector:
- <math>{V_1(X_1) \over w_1}, {V_2(X_2) \over w_2}, \dots , {V_n(X_n) \over w_n}</math>
where the partners are indexed such that:
- <math>{V_1(X_1) \over w_1} \leq {V_2(X_2) \over w_2} \leq \dots \leq {V_n(X_n) \over w_n}</math>
A leximin-optimal partition maximizes the value of the poorest partner (relative to his weight); subject to that, it maximizes the value of the next-poorest partner (relative to his weight); etc.
The compactness part of the DS theorem immediately implies that:[1]Шаблон:Rp
- If all value measures are countably-additive and nonatomic,
- then a leximin-optimal division exists.
Further developments
- The leximin-optimality criterion, introduced by Dubins and Spanier, has been studied extensively later. In particular, in the problem of cake-cutting, it was studied by Marco Dall'Aglio.[3]
See also
References
