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.

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}[i,j]=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} }$.

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.^[2]

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:^[1]: 5

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.

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

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.

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.

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

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

If all value measures are countably-additive and nonatomic,

then a leximin-optimal division exists.

• 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]

• Lyapunov vector-measure theorem^[4]
• Weller's theorem