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.
Contents
Setting
There is a set
There are
Let
This matrix contains the valuations of all players to all pieces of the partition.
Let
The Dubins–Spanier theorems deal with the topological properties of
Statements
If all value measures
This was already proved by Dvoretzky, Wald, and Wolfowitz.
Consensus partition
A cake partition
I.e, there is a consensus among all partners that the value of piece j is exactly
Suppose, from now on, that
and the value measures are normalized such that each partner values the entire cake as exactly 1:
The convexity part of the DS theorem implies that:
PROOF: For every
In the partition
By convexity, there is a partition
In that matrix, the
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
I.e, the piece allotted to partner
Let
A necessary condition for the existence of super-proportional divisions is that the value measures are not identical. PROOF: if the value measures are identical, then the sum of values of the pieces is exactly 1. Hence, it is not possible that all partners receive more than their fair share (if one gets more, another must get less).
The convexity part of the DS theorem implies that:
I.e, the necessary condition is also sufficient.
PROOF: Suppose w.l.o.g. that
Define the following partitions:
Here, we are interested only in the diagonals of the matrices
By convexity, for every set of weights
It is possible to select the weights
Utilitarian-optimal division
A cake partition
Utilitarian-optimal divisions do not always exist. For example, suppose
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:
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
where the partners are indexed such that:
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: