The Dubins–Spanier theorems are several theorems in the theory of
fair cake-cutting
Fair cake-cutting is a kind of fair division problem. The problem involves a ''heterogeneous'' resource, such as a cake with different toppings, that is assumed to be ''divisible'' – it is possible to cut arbitrarily small pieces of it without ...
. 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
In mathematics, the concept of a measure is a generalization and formalization of geometrical measures (length, area, volume) and other common notions, such as magnitude (mathematics), magnitude, mass, and probability of events. These seemingl ...
.
Setting
There is a set
, and a set
which is a
sigma-algebra of subsets of
.
There are
partners. Every partner
has a personal value measure
. This function determines how much each subset of
is worth to that partner.
Let
a partition of
to
measurable sets:
. Define the matrix
as the following
matrix:
:
This matrix contains the valuations of all players to all pieces of the partition.
Let
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
.
Statements
If all value measures
are
countably-additive and
nonatomic, then:
*
is a
compact set
In mathematics, specifically general topology, compactness is a property that seeks to generalize the notion of a closed and bounded subset of Euclidean space. The idea is that a compact space has no "punctures" or "missing endpoints", i.e., i ...
;
*
is a
convex set
In geometry, a set of points is convex if it contains every line segment between two points in the set.
For example, a solid cube (geometry), cube is a convex set, but anything that is hollow or has an indent, for example, a crescent shape, is n ...
.
This was already proved by Dvoretzky, Wald, and Wolfowitz.
Corollaries
Consensus partition
A cake partition
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
.
Suppose, from now on, that
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:
[
:::If all value measures are countably-additive and nonatomic,
:::then a consensus partition exists.
PROOF: For every , define a partition as follows:
:
:
In the partition , all partners value the -th piece as 1 and all other pieces as 0. Hence, in the matrix , there are ones on the -th column and zeros everywhere else.
By convexity, there is a partition such that:
:
In that matrix, the -th column contains only the value . This means that, in the partition , all partners value the -th piece as exactly .
Note: this corollary confirms a previous assertion by ]Hugo Steinhaus
Hugo Dyonizy Steinhaus ( , ; 14 January 1887 – 25 February 1972) was a Polish mathematician and educator. Steinhaus obtained his PhD under David Hilbert at Göttingen University in 1911 and later became a professor at the Jan Kazimierz Univers ...
. 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 to ''n'' pieces (one piece per partner) is called a ''super-proportional division A strongly proportional division (sometimes called super-proportional division or super-fair division) is a kind of a fair division
Fair division is the problem in game theory of dividing a set of resources among several people who have an Entitl ...
with weights '' 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
The hypothesis that the value measures are not identical is necessary. Otherwise, the sum leads to a contradiction.
Namely, if all value measures are countably-additive and non-atomic, and if there are two partners such that ,
then a super-proportional division exists.I.e, the necessary condition is also sufficient.
Sketch of Proof
Suppose w.l.o.g. that . Then there is some piece of the cake, , such that . Let be the complement of ; then . This means that . However, . Hence, either or . Suppose w.l.o.g. that and are true.
Define the following partitions:
* : the partition that gives to partner 1, to partner 2, and nothing to all others.
* (for ): the partition that gives the entire cake to partner and nothing to all others.
Here, we are interested only in the diagonals of the matrices , which represent the valuations of the partners to their own pieces:
* In , entry 1 is , entry 2 is , and the other entries are 0.
* In (for ), entry is 1 and the other entires are 0.
By convexity, for every set of weights there is a partition such that:
:
It is possible to select the weights such that, in the diagonal of , the entries are in the same ratios as the weights . Since we assumed that , it is possible to prove that , so is a super-proportional division.
Utilitarian-optimal division
A cake partition to ''n'' pieces (one piece per partner) is called ''utilitarian
In ethical philosophy, utilitarianism is a family of normative ethical theories that prescribe actions that maximize happiness and well-being for the affected individuals. In other words, utilitarian ideas encourage actions that lead to the ...
-optimal'' if it maximizes the sum of values. I.e, it maximizes:
:
Utilitarian-optimal divisions do not always exist. For example, suppose is the set of positive integers. There are two partners. Both value the entire set 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 to ''n'' pieces (one piece per partner) is called '' leximin-optimal with weights '' 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:[
:::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 Lyapunov (, in old-Russian often written Лепунов) is a Russian surname that is sometimes also romanized as Ljapunov, Liapunov or Ljapunow. Notable people with the surname include:
* Alexey Lyapunov (1911–1973), Russian mathematician
* Alek ...
* Weller's theorem
References
{{DEFAULTSORT:Dubins-Spanier theorems
Fair division
Theorems in measure theory