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.

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:

This was already proved by Dvoretzky, Wald, and Wolfowitz. [2]

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

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. 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 with weights if:

I.e, the piece allotted to partner is strictly more valuable for him than what he deserves.

Let be weights whose sum is 1, and assume that the value measures are normalized such that each partner values the entire cake as exactly 1.

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

If all value measures are countably-additive and nonatomic,
and if there are two partners such that ,
then a super-proportional division exists.

I.e, the necessary condition is also sufficient.

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 the former is true.

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

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

If all value measures are countably-additive and nonatomic,
then a leximin-optimal division exists.

Further developments

See also

References

  1. 1 2 3 4 5 6 Dubins, Lester Eli; Spanier, Edwin Henry (1961). "How to Cut a Cake Fairly". The American Mathematical Monthly. 68: 1. 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. 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: 17. 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.
This article is issued from Wikipedia - version of the 12/21/2015. The text is available under the Creative Commons Attribution/Share Alike but additional terms may apply for the media files.