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.
be the collection of all such matrices (for the same value measures, the same
, and different partitions): The Dubins–Spanier theorems deal with the topological properties of
are countably-additive and nonatomic, then: This was already proved by Dvoretzky, Wald, and Wolfowitz.
to k pieces is called a consensus partition with weights
(also called exact division) if: I.e, there is a consensus among all partners that the value of piece j is exactly
are weights whose sum is 1: 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:[1]: 5 PROOF: For every
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.
if: I.e, the piece allotted to partner
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
be weights whose sum is 1, assume that the point
is an interior point of the (n-1)-dimensional simplex with coordinates pairwise different, and assume that the value measures
are normalized such that each partner values the entire cake as exactly 1 (i.e. they are non-atomic probability measures).
Namely, if all value measures are countably-additive and non-atomic, and if there are two partners
, then a super-proportional division exists.I.e, the necessary condition is also sufficient.
Define the following partitions: Here, we are interested only in the diagonals of the matrices
, which represent the valuations of the partners to their own pieces: By convexity, for every set of weights
to n pieces (one piece per partner) is called utilitarian-optimal if it maximizes the sum of values.
I.e, it maximizes: Utilitarian-optimal divisions do not always exist.
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.
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 In this special case, non-atomicity is not required: if all value measures are countably-additive, then a utilitarian-optimal partition exists.
if it maximizes the lexicographically-ordered vector of relative values.
I.e, it maximizes the following vector: 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:[1]: 8