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

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

Условия

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

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

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

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

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

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

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

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

Утверждения

Если все меры предпочтений ${\displaystyle V_{i}}$ счётно-аддитивны^[англ.] и неатомарны, то:

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

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

Следствия

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

${\displaystyle {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}}}$

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

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

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

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

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

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

См. также

• Теорема Ляпунова о векторной мере^{[англ.][7]}
• Теорема Веллера

Примечания

1. Dubins, Spanier, 1961, с. 1.
2. Dvoretzky, Wald, Wolfowitz, 1951, с. 59.
3. Dubins, Spanier, 1961, с. 5.
4. Dubins, Spanier, 1961, с. 7.
5. Dubins, Spanier, 1961, с. 8.
6. Dall'Aglio, 2001, с. 17.
7. Neyman, 1946, с. 843–845.

Литература

• Lester Eli Dubins, Edwin Henry Spanier. How to Cut a Cake Fairly // The American Mathematical Monthly. — 1961. — Т. 68. — doi:10.2307/2311357. — JSTOR 2311357.
• Dvoretzky A., Wald A., Wolfowitz J. Relations among certain ranges of vector measures // Pacific Journal of Mathematics. — 1951. — Т. 1. — doi:10.2140/pjm.1951.1.59.
• Marco Dall'Aglio. The Dubins–Spanier optimization problem in fair division theory // Journal of Computational and Applied Mathematics. — 2001. — Т. 130. — doi:10.1016/S0377-0427(99)00393-3.
• Neyman J. Un théorèm dʼexistence // C. R. Acad. Sci.. — 1946. — Т. 222.