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

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