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

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

Условия

Имеется множество $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}$ выпукло.

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

Следствия

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

Разрезание торта $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

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

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

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

Доказательство: Для любого $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 конечно-аддитивна, но не счётно-аддитивна^[англ.].

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

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

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

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

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

Разрезание торта $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}}

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

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

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

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

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

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

См. также

Примечания

↑ Dubins, Spanier, 1961, с. 1.
↑ Dvoretzky, Wald, Wolfowitz, 1951, с. 59.
↑ Dubins, Spanier, 1961, с. 5.
↑ ¹ ² Dubins, Spanier, 1961, с. 7.
↑ Dubins, Spanier, 1961, с. 8.
↑ Dall'Aglio, 2001, с. 17.
↑ 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.

[_700691cd32c23f7a-1] Dubins, Spanier, 1961, с. 1.

[_c9725e6343bfb514-2] Dvoretzky, Wald, Wolfowitz, 1951, с. 59.

[_700691cd32c23f7e-3] Dubins, Spanier, 1961, с. 5.

[_700691cd32c23f7c-4] ¹ ² Dubins, Spanier, 1961, с. 7.

[_700691cd32c23f73-5] Dubins, Spanier, 1961, с. 8.

[_22180fd2440e9d8e-6] Dall'Aglio, 2001, с. 17.

[_f0c3e11b46d44006-7] Neyman, 1946, с. 843–845.

[1]

[2]

[3]

[4]

[5]

[6]

[7]