Теоремы Дубинса — Спеньера

Теоремы Дубинса — Спеньера — это несколько теорем в теории справедливого разрезания торта. Они были опубликованы Лестером Дубинсом и Эдвином Спеньером в 1961 году. Хотя исходной целью этих теорем была задача справедливого дележа, по факту они являются общими теоремами теории меры.

Условия

Имеется множество $U$ и множество $\mathbb {U}$, которое является сигма-алгеброй подмножеств множества $U$.

Имеется $n$ участников. Любой участник $i$ имеет персональную меру предпочтений $V_{i}:\mathbb {U} \to \mathbb {R}$. Эта функция определяет, насколько каждое подмножество $U$ ценно для участника.

Пусть $X$ будет разбиением $U$ на $k$ измеримых множеств: $U=X_{1}\sqcup \cdots \sqcup X_{k}$. Определим матрицу $M_{X}$ как матрицу $n\times k$:

$M_{X}[i,j]=V_{i}(X_{j})$

Эта матрица содержит оценки всех игроков для всех кусков разбиения.

Пусть $\mathbb {M}$ является набором всех таких матриц (для тех же самых мер предпочтений, того же значения $k$ и различных разбиений):

$\mathbb {M} =\{M_{X}\mid X$ является k-разбиением $U\}$

Теоремы Дубинса — Спеньера имеют дело с топологическими свойствами набора $\mathbb {M}$.

Утверждения

Если все меры предпочтений $V_{i}$ счётно-аддитивны и неатомарны, то:

• $\mathbb {M}$ компактно;
• $\mathbb {M}$ выпукло.

Это было уже доказано Дворецким, Вальдом и Вольфовичем.

Следствия

Согласованный делёж

Разрезание торта $X$ на k частей называется согласованным разрезанием с весами $w_{1},w_{2},\ldots ,w_{k}$ (говорят также о точном дележе), если:

$\forall i\in \{1,\dots ,n\}:\forall j\in \{1,\dots ,k\}:V_{i}(X_{j})=w_{j}$

То есть: есть согласие всех участников, что значение куска j равно в точности $w_{j}$.

Предположим теперь, что $w_{1},w_{2},\ldots ,w_{k}$ являются весами, сумма которых равна 1:

$\sum _{j=1}^{k}w_{j}=1$

а значения мер нормализованы так, что каждый участник оценивает значение всего торта в точности в 1:

$\forall i\in \{1,\dots ,n\}:V_{i}(U)=1$

Из выпуклости в теореме Дубинса — Спеньера следует, что :

Если все значения мер счётно-аддитивны и неатомарны,

то согласованное разбиение существует.

Доказательство: Для любого $j\in \{1,\dots ,k\}$ определим разбиение $X^{j}$ следующим образом

$X_{j}^{j}=U$

$\forall r\neq j:X_{r}^{j}=\emptyset$

В разбиении $X^{j}$ все оценки участников $j$-ого куска равны 1, а оценки всех остальных кусков равны 0. Следовательно, в матрице $M_{X^{j}}$ единицы имеются только в $j$-ом столбце и нули во всех остальных местах.

Согласно выпуклости, имеется разбиение $X$, такое, что

$M_{X}=\sum _{j=1}^{k}w_{j}\cdot M_{X^{j}}$

В этой матрице $j$-ый столбец содержит только значение $w_{j}$. Это означает, что в разбиении $X$ все оценки участников $j$-ого куска в точности равно $w_{j}$.

Примечание: это следствие подтверждает предыдущее утверждение Гуго Штейнгауза. Это даёт также положительный ответ на проблему Нила (реки), в которой утверждается, что имеется лишь конечное число высот наводнения.

Суперпропорциональный делёж

Разрезание торта $X$ на n кусков (по одному на каждого участника дележа) называется суперпропорциональным дележом с весами $w_{1},w_{2},...,w_{n}$, если

$\forall i\in 1\dots n:V_{i}(X_{i})>w_{i}$

То есть кусок, предназначаемый участнику $i$ строго, более предпочтителен для него, чем кусок, на который он имеет право. Следующее утверждение является теоремой Дубинса — Спеньера о существовании суперпропорционального дележа.

Теорема Пусть $w_{1},w_{2},...,w_{n}$ будут весами, сумма которых равна 1. Предположим, что точка $w:=(w_{1},w_{2},...,w_{n})$ является внутренней точкой (n-1)-мерного симплекса с попарно различными координатами и пусть меры полезности $V_{1},...,V_{n}$ нормализованы так, что каждый участник оценивает весь торт в точности в 1 (то есть меры являются неатомарными вероятностными мерами). Если хотя бы две меры $V_{i},V_{j}$ не совпадают ( $V_{i}\neq V_{j}$), то суперпропорциональный делёж существует.

Условие, что меры полезности $V_{1},...,V_{n}$ не все идентичны, необходимо. В противном случае сумма $\sum _{i=1}^{n}V_{i}(X_{i})=\sum _{i=1}^{n}V_{1}(X_{i})>\sum _{i=1}^{n}w_{i}=1$ приводит к противоречию.

Тогда, если все меры полезности счётно-аддитивны и неатомарны, а также существуют два участника $i,j$ такие, что $V_{i}\neq V_{j}$, то суперпропорциональный делёж существует. То есть необходимое условие является также и достаточным.

Набросок доказательства

Предположим без потери общности, что $V_{1}\neq V_{2}$. Тогда существует некоторый кусок торта $Z\subseteq U$, такой, что $V_{1}(Z)>V_{2}(Z)$. Пусть ${\overline {Z}}$ будет дополнением $Z$. Тогда $V_{2}({\overline {Z}})>V_{1}({\overline {Z}})$. Это означает, что $V_{1}(Z)+V_{2}({\overline {Z}})>1$. Однако $w_{1}+w_{2}\leqslant 1$. Следовательно, либо $V_{1}(Z)>w_{1}$, либо $V_{2}({\overline {Z}})>w_{2}$. Предположим без потери общности, что неравенства $V_{1}(Z)>V_{2}(Z)$ и $V_{1}(Z)>w_{1}$ верны.

Определим следующее разрезание:

• $X^{1}$: разрезание, которое отдаёт $Z$ участнику 1, ${\overline {Z}}$ участнику 2 и ничего остальным участникам.
• $X^{i}$ (для $i\geqslant 2$): разрезание, которое даёт весь торт участнику $i$ и ничего остальным.

Здесь нас интересует только диагональ матрицы $M_{X^{j}}$, которая представляет оценки участниками из собственных кусков:

• В матрице ${\textrm {diag}}(M_{X^{1}})$ первый элемент равен $V_{1}(Z)$, второй элемент равен $V_{2}({\overline {Z}})$, остальные элементы равны 0.
• В матрице ${\textrm {diag}}(M_{X^{i}})$ (для $i\geqslant 2$), элемент $i$ равен 1, а другие элементы равны 0.

По условию выпуклости для любого множества весов $z_{1},z_{2},...,z_{n}$ существует разбиение $X$, такое, что

$M_{X}=\sum _{j=1}^{n}{z_{j}\cdot M_{X^{j}}}.$

Можно выбрать веса $z_{i}$ таким образом, что на диагонали $M_{X}$, находятся в том же отношении, что и веса $w_{i}$. Поскольку мы предположили, что $V_{1}(Z)>w_{1}$, можно доказать, что $\forall i\in 1\dots n:V_{i}(X_{i})>w_{i}$, так что $X$ является суперпропорциональным дележом.

Утилитарно-оптимальный делёж

Разрезание торта $X$ на n кусков (по одному куску на каждого участника) называется утилитарно-оптимально, если оно максимизирует сумму оценок полезности. То есть оно максимизирует

$\sum _{i=1}^{n}{V_{i}(X_{i})}$

Утилитарно-оптимальные дележи не всегда существуют. Например, допустим, что $U$ является множеством положительных целых чисел. Пусть имеется два участника, оба оценивают значение всего множества $U$ в 1. Участник 1 назначает положительное значение каждому целому числу, а участник 2 назначает 0 любому конечному подмножеству. С утилитарной точки зрения лучше всего отдать первому участнику большое конечное подмножество, а остаток отдать второму участнику. По мере того, как отдаваемое первому участнику множество становится всё больше и больше, сумма значений становится ближе и ближе к 2, но значения 2 мы никогда не получим. Таким образом, утилитарно-оптимального дележа не существует.

Проблема в выше приведённом примере заключается в том, что мера полезности для участника 2 конечно-аддитивна, но не счётно-аддитивна.

Из компактности в теореме Дубинса — Спеньера немедленно следует, что:

Если все меры предпочтений счётно-аддитивны и неатомарны,

то утилитарно-оптимальный делёж существует.

В этом специальном случае неатомарность не требуется — если все меры предпочтений счётно-аддитивны, то утилитарно-оптимальный делёж существует.

Лексимин-оптимальный делёж

Разрезание торта $X$ на n кусков (по одному куску на каждого участника) называется лексимин-оптимальным с весами $w_{1},w_{2},...,w_{n}$, если оно максимизирует лексикографически упорядоченный вектор относительных значений. То есть оно максимизирует следующий вектор:

${V_{1}(X_{1}) \over w_{1}},{V_{2}(X_{2}) \over w_{2}},\dots ,{V_{n}(X_{n}) \over w_{n}}$

где участники проиндексированы так, что:

${V_{1}(X_{1}) \over w_{1}}\leqslant {V_{2}(X_{2}) \over w_{2}}\leqslant \dots \leqslant {V_{n}(X_{n}) \over w_{n}}$

Лексимин-оптимальное разрезание максимизирует значение наиболее бедного участника (согласно его весу), затем второго по бедности участника и т.д..

Из компактности в теореме Дубинса — Спеньера немедленно следует, что:

Если все меры предпочтений счётно-аддитивны и неатомарны,

то лексимин-оптимальный делёж существует.

Дальнейшие исследования

• Критерий лексимин-оптимальности, введённый Дубинсом и Спеньером, впоследствии интенсивно изучался. В частности, для задачи справедливого разрезания торта критерий изучал Марко Дель Альо.

См. также

• Теорема Ляпунова о векторной мере
• Теорема Веллера