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

Теоремы Дубинса — Спеньера — это несколько теорем в теории справедливого разрезания торта. Они были опубликованы Лестером Дубинсом и Эдвином Спеньером в 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].

См. также

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

Примечания

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. — .
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.

This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.

[_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.