Dubins–Spanier theorems

There is a set $U$, and a set $\backslash mathbb\{U\}$ which is a sigma-algebra of subsets of $U$.

There are $n$ partners. Every partner $i$ has a personal value measure $V\_i:\; \backslash mathbb\{U\}\; \backslash to\; \backslash mathbb\{R\}$. This function determines how much each subset of $U$ is worth to that partner.

Let $X$ a partition of $U$ to $k$ measurable sets: $U\; =\; X\_1\; \backslash sqcup\; \backslash cdots\; \backslash sqcup\; X\_k$. Define the matrix $M\_X$ as the following $n\backslash times\; k$ matrix:

:$M\_X[i,j]\; =\; V\_i(X\_j)$

This matrix contains the valuations of all players to all pieces of the partition.

Let $\backslash mathbb\{M\}$ be the collection of all such matrices (for the same value measures, the same $k$, and different partitions):

:$\backslash mathbb\{M\}\; =\; \backslash \{M\_X\; \backslash mid\; X\backslash text\{\; is\; a\; \}k\backslash text\{-partition\; of\; \}\; U\backslash \}$

The Dubins–Spanier theorems deal with the topological properties of $\backslash mathbb\{M\}$.

If all value measures $V\_i$ are countably-additive and nonatomic, then:

• $\backslash mathbb\{M\}$ is a compact set;
• $\backslash mathbb\{M\}$ is a convex set.

This was already proved by Dvoretzky, Wald, and Wolfowitz.{{Cite journal|doi=10.2140/pjm.1951.1.59|title=Relations among certain ranges of vector measures|journal=Pacific Journal of Mathematics|volume=1|pages=59–74|year=1951|last1=Dvoretzky|first1=A.|last2=Wald|first2=A.|last3=Wolfowitz|first3=J.|doi-access=free}}

A cake partition $X$ to k pieces is called a consensus partition with weights $w\_1,\; w\_2,\; \backslash ldots,\; w\_k$ (also called exact division) if:

:$\backslash forall\; i\; \backslash in\; \backslash \{1,\backslash dots,\; n\backslash \}:\; \backslash forall\; j\; \backslash in\; \backslash \{1,\backslash dots,\; k\backslash \}:\; V\_i(X\_j)\; =\; w\_j$

I.e, there is a consensus among all partners that the value of piece j is exactly $w\_j$.

Suppose, from now on, that $w\_1,\; w\_2,\; \backslash ldots,\; w\_k$ are weights whose sum is 1:

:$\backslash sum\_\{j=1\}^k\; w\_j\; =1$

and the value measures are normalized such that each partner values the entire cake as exactly 1:

:$\backslash forall\; i\; \backslash in\; \backslash \{1,\backslash dots,\; n\backslash \}:\; V\_i(U)\; =\; 1$

The convexity part of the DS theorem implies that:{{rp|5}}

:::If all value measures are countably-additive and nonatomic,

:::then a consensus partition exists.

PROOF: For every $j\; \backslash in\; \backslash \{1,\backslash dots,\; k\backslash \}$, define a partition $X^j$ as follows:

:$X^j\_j\; =\; U$

:$\backslash forall\; r\backslash neq\; j:\; X^j\_r\; =\; \backslash emptyset$

In the partition $X^j$, all partners value the $j$-th piece as 1 and all other pieces as 0. Hence, in the matrix $M\_\{X^j\}$, there are ones on the $j$-th column and zeros everywhere else.

By convexity, there is a partition $X$ such that:

:$M\_X\; =\; \backslash sum\_\{j=1\}^k\; w\_j\backslash cdot\; M\_\{X^j\}$

In that matrix, the $j$-th column contains only the value $w\_j$. This means that, in the partition $X$, all partners value the $j$-th piece as exactly $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 $X$ to n pieces (one piece per partner) is called a super-proportional division with weights $w\_1,\; w\_2,\; ...,\; w\_n$ if:

:$\backslash forall\; i\; \backslash in\; 1\backslash dots\; n:\; V\_i(X\_i)\; >\; w\_i$

I.e, the piece allotted to partner $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 {{rp|6}}

{{math_theorem

|With these notations, let $w\_1,\; w\_2,\; ...,\; w\_n$ be weights whose sum is 1, assume that the point $w:=(w\_1,\; w\_2,\; ...,\; w\_n)$ is an interior point of the (n-1)-dimensional simplex with coordinates pairwise different, and assume that the value measures $V\_1,\; ...,\; V\_n$ are normalized such that each partner values the entire cake as exactly 1 (i.e. they are non-atomic probability measures). If at least two of the measures $V\_i,\; V\_j$ are not equal ( $V\_i\backslash neq\; V\_j$), then super-proportional divisions exist.}}

The hypothesis that the value measures $V\_1,\; ...,\; V\_n$ are not identical is necessary. Otherwise, the sum $\backslash sum\_\{i=1\}^n\; V\_i(X\_i)\; =\backslash sum\_\{i=1\}^n\; V\_1(X\_i)\; >\; \backslash 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 $i,j$ such that $V\_i\backslash neq\; V\_j$,

then a super-proportional division exists.I.e, the necessary condition is also sufficient.

Suppose w.l.o.g. that $V\_1\; \backslash neq\; V\_2$. Then there is some piece of the cake, $Z\backslash subseteq\; U$, such that $V\_1(Z)>V\_2(Z)$. Let $\backslash overline\{Z\}$ be the complement of $Z$; then $V\_2(\backslash overline\{Z\})>V\_1(\backslash overline\{Z\})$. This means that $V\_1(Z)\; +\; V\_2(\backslash overline\{Z\})\; >\; 1$. However, $w\_1+w\_2\backslash leq\; 1$. Hence, either $V\_1(Z)>w\_1$ or $V\_2(\backslash overline\{Z\})>w\_2$. Suppose w.l.o.g. that $V\_1(Z)>V\_2(Z)$ and $V\_1(Z)>w\_1$ are true.

Define the following partitions:

• $X^1$: the partition that gives $Z$ to partner 1, $\backslash overline\{Z\}$ to partner 2, and nothing to all others.
• $X^i$ (for $i\backslash geq\; 2$): the partition that gives the entire cake to partner $i$ and nothing to all others.

Here, we are interested only in the diagonals of the matrices $M\_\{X^j\}$, which represent the valuations of the partners to their own pieces:

• In $\backslash textrm\{diag\}(M\_\{X^1\})$, entry 1 is $V\_1(Z)$, entry 2 is $V\_2(\backslash overline\{Z\})$, and the other entries are 0.
• In $\backslash textrm\{diag\}(M\_\{X^i\})$ (for $i\backslash geq\; 2$), entry $i$ is 1 and the other entires are 0.

By convexity, for every set of weights $z\_1,\; z\_2,\; ...,\; z\_n$ there is a partition $X$ such that:

:$M\_X\; =\; \backslash sum\_\{j=1\}^n\; \{z\_j\backslash cdot\; M\_\{X^j\}\}.$

It is possible to select the weights $z\_i$ such that, in the diagonal of $M\_X$, the entries are in the same ratios as the weights $w\_i$. Since we assumed that $V\_1(Z)>w\_1$, it is possible to prove that $\backslash forall\; i\; \backslash in\; 1\backslash dots\; n:\; V\_i(X\_i)\; >\; w\_i$, so $X$ is a super-proportional division.

A cake partition $X$ to n pieces (one piece per partner) is called utilitarian-optimal if it maximizes the sum of values. I.e, it maximizes:

:$\backslash sum\_\{i=1\}^n\{V\_i(X\_i)\}$

Utilitarian-optimal divisions do not always exist. For example, suppose $U$ is the set of positive integers. There are two partners. Both value the entire set $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:{{rp|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.{{rp|7}}

A cake partition $X$ to n pieces (one piece per partner) is called leximin-optimal with weights $w\_1,\; w\_2,\; ...,\; w\_n$ if it maximizes the lexicographically-ordered vector of relative values. I.e, it maximizes the following vector:

:$\{V\_1(X\_1)\; \backslash over\; w\_1\},\; \{V\_2(X\_2)\; \backslash over\; w\_2\},\; \backslash dots\; ,\; \{V\_n(X\_n)\; \backslash over\; w\_n\}$

where the partners are indexed such that:

:$\{V\_1(X\_1)\; \backslash over\; w\_1\}\; \backslash leq\; \{V\_2(X\_2)\; \backslash over\; w\_2\}\; \backslash leq\; \backslash dots\; \backslash leq\; \{V\_n(X\_n)\; \backslash 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:{{rp|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.{{Cite journal|doi=10.1016/S0377-0427(99)00393-3|title=The Dubins–Spanier optimization problem in fair division theory|journal=Journal of Computational and Applied Mathematics|volume=130|pages=17–40|year=2001|last1=Dall'Aglio|first1=Marco|issue=1–2|bibcode=2001JCoAM.130...17D|doi-access=free}}

• Lyapunov vector-measure theorem{{cite journal|last1=Neyman|first1=J|title=Un théorèm dʼexistence|journal=C. R. Acad. Sci.|date=1946|volume=222|pages=843–845}}
• Weller's theorem

{{reflist}}

{{DEFAULTSORT:Dubins-Spanier theorems}}

Category:Fair division

Category:Theorems in measure theory