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.[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 $U$ , and a set $\mathbb {U}$ which is a sigma-algebra of subsets of $U$ .

There are $n$ partners. Every partner $i$ has a personal value measure $V_{i}:\mathbb {U} \to \mathbb {R}$ . 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}[i,j]=V_{i}(X_{j})

This matrix contains the valuations of all players to all pieces of the partition.

Let $\mathbb {M}$ be the collection of all such matrices (for the same value measures, the same $k$ , and different partitions):

\mathbb {M} =\{M_{X}\mid X{\text{ is a }}k{\text{-partition of }}U\}

The Dubins–Spanier theorems deal with the topological properties of $\mathbb {M}$ .

Statements

If all value measures $V_{i}$ are countably-additive and nonatomic, then:

$\mathbb {M}$ is a compact set;
$\mathbb {M}$ is a convex set.

This was already proved by Dvoretzky, Wald, and Wolfowitz. [2]

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) if:

\forall i\in \{1,\dots ,n\}:\forall j\in \{1,\dots ,k\}: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 _{j=1}^{k}w_{j}=1

and the value measures are normalized such that each partner values the entire cake as exactly 1:

\forall i\in \{1,\dots ,n\}:V_{i}(U)=1

The convexity part of the DS theorem implies that:[1]^: 5

If all value measures are countably-additive and nonatomic,

then a consensus partition exists.

PROOF: For every $j\in \{1,\dots ,k\}$ , define a partition $X^{j}$ as follows:

X_{j}^{j}=U

\forall r\neq j:X_{r}^{j}=\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_{X^{j}}$ , there are ones on the $j$ -th column and zeros everywhere else.

By convexity, there is a partition $X$ such that:

M_{X}=\sum _{j=1}^{k}w_{j}\cdot M_{X^{j}}

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. 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 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 ^: 6

Theorem — With these notations, let $w_{1},w_{2},...,w_{n}$ be weights whose sum is 1, assume that the point $w:=(w_{1},w_{2},...,w_{n})$ is an interior point of the (n-1)-dimensional simplex with coordinates pairwise different, and assume that the value measures $V_{1},...,V_{n}$ are normalized such that each partner values the entire cake as exactly 1 (i.e. they are non-atomic probability measures). If at least two of the measures $V_{i},V_{j}$ are not equal ( $V_{i}\neq V_{j}$ ), then super-proportional divisions exist.

The hypothesis that the value measures $V_{1},...,V_{n}$ are not identical is necessary. Otherwise, the sum $\sum _{i=1}^{n}V_{i}(X_{i})=\sum _{i=1}^{n}V_{1}(X_{i})>\sum _{i=1}^{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 {Z}}$ be the complement of $Z$ ; then $V_{2}({\overline {Z}})>V_{1}({\overline {Z}})$ . This means that $V_{1}(Z)+V_{2}({\overline {Z}})>1$ . However, $w_{1}+w_{2}\leq 1$ . Hence, either $V_{1}(Z)>w_{1}$ or $V_{2}({\overline {Z}})>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 {Z}}$ 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_{X^{j}}$ , which represent the valuations of the partners to their own pieces:

In ${\textrm {diag}}(M_{X^{1}})$ , entry 1 is $V_{1}(Z)$ , entry 2 is $V_{2}({\overline {Z}})$ , and the other entries are 0.
In ${\textrm {diag}}(M_{X^{i}})$ (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 _{j=1}^{n}{z_{j}\cdot M_{X^{j}}}.

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-optimal if it maximizes the sum of values. I.e, it maximizes:

\sum _{i=1}^{n}{V_{i}(X_{i})}

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.

The compactness part of the DS theorem immediately implies that:[1]^: 7

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]^: 7

Leximin-optimal division

A cake partition $X$ to n pieces (one piece per partner) is called leximin-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:

{V_{1}(X_{1}) \over w_{1}},{V_{2}(X_{2}) \over w_{2}},\dots ,{V_{n}(X_{n}) \over w_{n}}

where the partners are indexed such that:

{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}}

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]^: 8

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]

References

Dubins, Lester Eli; Spanier, Edwin Henry (1961). "How to Cut a Cake Fairly". The American Mathematical Monthly. 68 (1): 1–17. doi:10.2307/2311357. JSTOR 2311357.
Dvoretzky, A.; Wald, A.; Wolfowitz, J. (1951). "Relations among certain ranges of vector measures". Pacific Journal of Mathematics. 1: 59–74. doi:10.2140/pjm.1951.1.59.
Dall'Aglio, Marco (2001). "The Dubins–Spanier optimization problem in fair division theory". Journal of Computational and Applied Mathematics. 130 (1–2): 17–40. Bibcode:2001JCoAM.130...17D. doi:10.1016/S0377-0427(99)00393-3.
Neyman, J (1946). "Un théorèm dʼexistence". C. R. Acad. Sci. 222: 843–845.

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

[DS-1] Dubins, Lester Eli; Spanier, Edwin Henry (1961). "How to Cut a Cake Fairly". The American Mathematical Monthly. 68 (1): 1–17. doi:10.2307/2311357. JSTOR 2311357.

[2] Dvoretzky, A.; Wald, A.; Wolfowitz, J. (1951). "Relations among certain ranges of vector measures". Pacific Journal of Mathematics. 1: 59–74. doi:10.2140/pjm.1951.1.59.

[dallaglio01-3] Dall'Aglio, Marco (2001). "The Dubins–Spanier optimization problem in fair division theory". Journal of Computational and Applied Mathematics. 130 (1–2): 17–40. Bibcode:2001JCoAM.130...17D. doi:10.1016/S0377-0427(99)00393-3.

[4] Neyman, J (1946). "Un théorèm dʼexistence". C. R. Acad. Sci. 222: 843–845.

Dubins–Spanier theorems

Setting

Statements

Corollaries

Consensus partition

Super-proportional division

Sketch of Proof

Utilitarian-optimal division

Leximin-optimal division

Further developments

See also

References