Misplaced Pages

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

There are ${\displaystyle n}$ partners. Every partner ${\displaystyle i}$ has a personal value measure ${\displaystyle V_{i}:\mathbb {U} \to \mathbb {R} }$. This function determines how much each subset of ${\displaystyle U}$ is worth to that partner.

Let ${\displaystyle X}$ a partition of ${\displaystyle U}$ to ${\displaystyle k}$ measurable sets: ${\displaystyle U=X_{1}\sqcup \cdots \sqcup X_{k}}$. Define the matrix ${\displaystyle M_{X}}$ as the following ${\displaystyle n\times k}$ matrix:

${\displaystyle M_{X}=V_{i}(X_{j})}$

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

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

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

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

Statements

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

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

This was already proved by Dvoretzky, Wald, and Wolfowitz.

Corollaries

Consensus partition

A cake partition ${\displaystyle X}$ to k pieces is called a consensus partition with weights ${\displaystyle w_{1},w_{2},\ldots ,w_{k}}$ (also called exact division) if:

${\displaystyle \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 ${\displaystyle w_{j}}$.

Suppose, from now on, that ${\displaystyle w_{1},w_{2},\ldots ,w_{k}}$ are weights whose sum is 1:

${\displaystyle \sum _{j=1}^{k}w_{j}=1}$

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

${\displaystyle \forall i\in \{1,\dots ,n\}: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 ${\displaystyle j\in \{1,\dots ,k\}}$, define a partition ${\displaystyle X^{j}}$ as follows:

${\displaystyle X_{j}^{j}=U}$

${\displaystyle \forall r\neq j:X_{r}^{j}=\emptyset }$

In the partition ${\displaystyle X^{j}}$, all partners value the ${\displaystyle j}$-th piece as 1 and all other pieces as 0. Hence, in the matrix ${\displaystyle M_{X^{j}}}$, there are ones on the ${\displaystyle j}$-th column and zeros everywhere else.

By convexity, there is a partition ${\displaystyle X}$ such that:

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

In that matrix, the ${\displaystyle j}$-th column contains only the value ${\displaystyle w_{j}}$. This means that, in the partition ${\displaystyle X}$, all partners value the ${\displaystyle j}$-th piece as exactly ${\displaystyle 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 ${\displaystyle X}$ to n pieces (one piece per partner) is called a super-proportional division with weights ${\displaystyle w_{1},w_{2},...,w_{n}}$ if:

${\displaystyle \forall i\in 1\dots n:V_{i}(X_{i})>w_{i}}$

I.e, the piece allotted to partner ${\displaystyle 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

Theorem — With these notations, let ${\displaystyle w_{1},w_{2},...,w_{n}}$ be weights whose sum is 1, assume that the point ${\displaystyle 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 ${\displaystyle 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 ${\displaystyle V_{i},V_{j}}$ are not equal ( ${\displaystyle V_{i}\neq V_{j}}$), then super-proportional divisions exist.

The hypothesis that the value measures ${\displaystyle V_{1},...,V_{n}}$ are not identical is necessary. Otherwise, the sum ${\displaystyle \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 ${\displaystyle i,j}$ such that ${\displaystyle 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 ${\displaystyle V_{1}\neq V_{2}}$. Then there is some piece of the cake, ${\displaystyle Z\subseteq U}$, such that ${\displaystyle V_{1}(Z)>V_{2}(Z)}$. Let ${\displaystyle {\overline {Z}}}$ be the complement of ${\displaystyle Z}$; then ${\displaystyle V_{2}({\overline {Z}})>V_{1}({\overline {Z}})}$. This means that ${\displaystyle V_{1}(Z)+V_{2}({\overline {Z}})>1}$. However, ${\displaystyle w_{1}+w_{2}\leq 1}$. Hence, either ${\displaystyle V_{1}(Z)>w_{1}}$ or ${\displaystyle V_{2}({\overline {Z}})>w_{2}}$. Suppose w.l.o.g. that ${\displaystyle V_{1}(Z)>V_{2}(Z)}$ and ${\displaystyle V_{1}(Z)>w_{1}}$ are true.

Define the following partitions:

• ${\displaystyle X^{1}}$: the partition that gives ${\displaystyle Z}$ to partner 1, ${\displaystyle {\overline {Z}}}$ to partner 2, and nothing to all others.
• ${\displaystyle X^{i}}$ (for ${\displaystyle i\geq 2}$): the partition that gives the entire cake to partner ${\displaystyle i}$ and nothing to all others.

Here, we are interested only in the diagonals of the matrices ${\displaystyle M_{X^{j}}}$, which represent the valuations of the partners to their own pieces:

• In ${\displaystyle {\textrm {diag}}(M_{X^{1}})}$, entry 1 is ${\displaystyle V_{1}(Z)}$, entry 2 is ${\displaystyle V_{2}({\overline {Z}})}$, and the other entries are 0.
• In ${\displaystyle {\textrm {diag}}(M_{X^{i}})}$ (for ${\displaystyle i\geq 2}$), entry ${\displaystyle i}$ is 1 and the other entires are 0.

By convexity, for every set of weights ${\displaystyle z_{1},z_{2},...,z_{n}}$ there is a partition ${\displaystyle X}$ such that:

${\displaystyle M_{X}=\sum _{j=1}^{n}{z_{j}\cdot M_{X^{j}}}.}$

It is possible to select the weights ${\displaystyle z_{i}}$ such that, in the diagonal of ${\displaystyle M_{X}}$, the entries are in the same ratios as the weights ${\displaystyle w_{i}}$. Since we assumed that ${\displaystyle V_{1}(Z)>w_{1}}$, it is possible to prove that ${\displaystyle \forall i\in 1\dots n:V_{i}(X_{i})>w_{i}}$, so ${\displaystyle X}$ is a super-proportional division.

Utilitarian-optimal division

A cake partition ${\displaystyle X}$ to n pieces (one piece per partner) is called utilitarian-optimal if it maximizes the sum of values. I.e, it maximizes:

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

Utilitarian-optimal divisions do not always exist. For example, suppose ${\displaystyle U}$ is the set of positive integers. There are two partners. Both value the entire set ${\displaystyle 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:

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 ${\displaystyle X}$ to n pieces (one piece per partner) is called leximin-optimal with weights ${\displaystyle w_{1},w_{2},...,w_{n}}$ if it maximizes the lexicographically-ordered vector of relative values. I.e, it maximizes the following vector:

${\displaystyle {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:

${\displaystyle {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:

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

References

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.
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.

• Fair division
• Theorems in measure theory