HOME

TheInfoList



OR:

The Dubins–Spanier theorems are several theorems in the theory of
fair cake-cutting Fair cake-cutting is a kind of fair division problem. The problem involves a ''heterogeneous'' resource, such as a cake with different toppings, that is assumed to be ''divisible'' – it is possible to cut arbitrarily small pieces of it without ...
. They were published by Lester Dubins and
Edwin Spanier Edwin Henry Spanier (August 8, 1921 – October 11, 1996) was an American mathematician at the University of California at Berkeley, working in algebraic topology. He co-invented Spanier–Whitehead duality and Alexander–Spanier cohomology ...
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 U, and a set \mathbb which is a sigma-algebra of subsets of U. There are n partners. Every partner i has a personal value measure V_i: \mathbb \to \mathbb. This function determines how much each subset of U is worth to that partner. Let X a partition of U to k measurable sets: U = X_1 \sqcup \cdots \sqcup X_k. Define the matrix M_X as the following n\times k matrix: :M_X ,j= V_i(X_j) This matrix contains the valuations of all players to all pieces of the partition. Let \mathbb be the collection of all such matrices (for the same value measures, the same k, and different partitions): :\mathbb = \ The Dubins–Spanier theorems deal with the topological properties of \mathbb.


Statements

If all value measures V_i are
countably-additive In mathematics, an additive set function is a function mapping sets to numbers, with the property that its value on a union of two disjoint sets equals the sum of its values on these sets, namely, \mu(A \cup B) = \mu(A) + \mu(B). If this additivity ...
and nonatomic, then: * \mathbb is a
compact set In mathematics, specifically general topology, compactness is a property that seeks to generalize the notion of a closed and bounded subset of Euclidean space by making precise the idea of a space having no "punctures" or "missing endpoints", ...
; * \mathbb is a
convex set In geometry, a subset of a Euclidean space, or more generally an affine space over the reals, is convex if, given any two points in the subset, the subset contains the whole line segment that joins them. Equivalently, a convex set or a convex ...
. This was already proved by Dvoretzky, Wald, and Wolfowitz.


Corollaries


Consensus partition

A cake partition X to ''k'' pieces is called a ''consensus partition with weights w_1, w_2, \ldots, w_k'' (also called
exact division Exact division, also called consensus division, is a partition of a continuous resource ("cake") into some ''k'' pieces, such that each of ''n'' people with different tastes agree on the value of each of the pieces. For example, consider a cake whic ...
) if: :\forall i \in \: \forall j \in \: V_i(X_j) = w_j I.e, there is a consensus among all partners that the value of piece ''j'' is exactly w_j. Suppose, from now on, that w_1, w_2, \ldots, w_k are weights whose sum is 1: :\sum_^k w_j =1 and the value measures are normalized such that each partner values the entire cake as exactly 1: :\forall i \in \: V_i(U) = 1 The convexity part of the DS theorem implies that: :::If all value measures are countably-additive and nonatomic, :::then a consensus partition exists. PROOF: For every j \in \, define a partition X^j as follows: :X^j_j = U :\forall r\neq j: X^j_r = \emptyset In the partition X^j, all partners value the j-th piece as 1 and all other pieces as 0. Hence, in the matrix M_, there are ones on the j-th column and zeros everywhere else. By convexity, there is a partition X such that: :M_X = \sum_^k w_j\cdot M_ In that matrix, the j-th column contains only the value w_j. This means that, in the partition X, all partners value the j-th piece as exactly w_j. Note: this corollary confirms a previous assertion by
Hugo Steinhaus Hugo Dyonizy Steinhaus ( ; ; January 14, 1887 – February 25, 1972) was a Polish mathematician and educator. Steinhaus obtained his PhD under David Hilbert at Göttingen University in 1911 and later became a professor at the Jan Kazimierz Un ...
. 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 X to ''n'' pieces (one piece per partner) is called a ''
super-proportional division A strongly-proportional division (sometimes called super-proportional division) is a kind of a fair division. It is a division of resources among ''n'' partners, in which the value received by each partner is strictly more than his/her due share of ...
with weights w_1, w_2, ..., w_n'' if: :\forall i \in 1\dots n: V_i(X_i) > w_i I.e, the piece allotted to partner i is strictly more valuable for him than what he deserves. The following statement is Dubins-Spanier Theorem on the existence of super-proportional division The hypothesis that the value measures V_1, ..., V_n are not identical is necessary. Otherwise, the sum \sum_^n V_i(X_i) =\sum_^n V_1(X_i) > \sum_^n w_i =1 leads to a contradiction. Namely, if all value measures are countably-additive and non-atomic, and if there are two partners i,j such that V_i\neq V_j, then a super-proportional division exists.I.e, the necessary condition is also sufficient.


Sketch of Proof

Suppose w.l.o.g. that V_1 \neq V_2. Then there is some piece of the cake, Z\subseteq U, such that V_1(Z)>V_2(Z). Let \overline be the complement of Z; then V_2(\overline)>V_1(\overline). This means that V_1(Z) + V_2(\overline) > 1. However, w_1+w_2\leq 1. Hence, either V_1(Z)>w_1 or V_2(\overline)>w_2. Suppose w.l.o.g. that V_1(Z)>V_2(Z) and V_1(Z)>w_1 are true. Define the following partitions: * X^1: the partition that gives Z to partner 1, \overline to partner 2, and nothing to all others. * X^i (for i\geq 2): the partition that gives the entire cake to partner i and nothing to all others. Here, we are interested only in the diagonals of the matrices M_, which represent the valuations of the partners to their own pieces: * In \textrm(M_), entry 1 is V_1(Z), entry 2 is V_2(\overline), and the other entries are 0. * In \textrm(M_) (for i\geq 2), entry i is 1 and the other entires are 0. By convexity, for every set of weights z_1, z_2, ..., z_n there is a partition X such that: :M_X = \sum_^n . It is possible to select the weights z_i such that, in the diagonal of M_X, the entries are in the same ratios as the weights w_i. Since we assumed that V_1(Z)>w_1, it is possible to prove that \forall i \in 1\dots n: V_i(X_i) > w_i, so X is a super-proportional division.


Utilitarian-optimal division

A cake partition X to ''n'' pieces (one piece per partner) is called ''
utilitarian In ethical philosophy, utilitarianism is a family of normative ethical theories that prescribe actions that maximize happiness and well-being for all affected individuals. Although different varieties of utilitarianism admit different charact ...
-optimal'' if it maximizes the sum of values. I.e, it maximizes: :\sum_^n Utilitarian-optimal divisions do not always exist. For example, suppose U is the set of positive integers. There are two partners. Both value the entire set U 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 In mathematics, an additive set function is a function mapping sets to numbers, with the property that its value on a union of two disjoint sets equals the sum of its values on these sets, namely, \mu(A \cup B) = \mu(A) + \mu(B). If this additivity ...
. The compactness part of the DS theorem immediately implies that: :::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.


Leximin-optimal division

A cake partition X to ''n'' pieces (one piece per partner) is called ''
leximin In mathematics, leximin order is a total preorder on finite-dimensional vectors. A more accurate, but less common term is leximin preorder. The leximin order is particularly important in social choice theory and fair division. Definition A ve ...
-optimal with weights w_1, w_2, ..., w_n'' if it maximizes the lexicographically-ordered vector of relative values. I.e, it maximizes the following vector: :, , \dots , where the partners are indexed such that: : \leq \leq \dots \leq 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: :::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.


See also

* Lyapunov vector-measure theorem *
Weller's theorem Weller's theorem is a theorem in economics. It says that a heterogeneous resource ("cake") can be divided among ''n'' partners with different valuations in a way that is both Pareto-efficient (PE) and envy-free (EF). Thus, it is possible to divide a ...


References

{{DEFAULTSORT:Dubins-Spanier theorems Fair division Theorems in measure theory