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

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

Условия

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

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

Пусть $X$ будет разбиением $U$ на $k$ измеримых множеств: $U=X_1\bigsqcup \cdots \bigsqcup X_k$. Определим матрицу $M_X$ как матрицу $n\times k$:

$M_X[i,j]=V_i(X_j)$

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

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

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

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

Утверждения

Если все меры предпочтений $V_i$ Шаблон:Не переведено 5 и неатомарны, то:

• $𝕄$ компактно;
• $𝕄$ выпукло.

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

Следствия

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

Разрезание торта $X$ на k частей называется согласованным разрезанием с весами $w_1,w_2,\dots ,w_k$ (говорят также о точном дележе), если:

$\mathrm{\forall }i\in \{1,\dots ,n\}:\mathrm{\forall }j\in \{1,\dots ,k\}:V_i(X_j)=w_j$

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

Предположим теперь, что $w_1,w_2,\dots ,w_k$ являются весами, сумма которых равна 1:

$\sum _{j=1}^k{w}_j=1$

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

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

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

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

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

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

$X_j^j=U$

$\mathrm{\forall }r\ne j:X_r^j=\mathrm{\varnothing }$

В разбиении $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$, если

$\mathrm{\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\ne 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\ne V_j$, то суперпропорциональный делёж существует. То есть необходимое условие является также и достаточным.

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

Предположим без потери общности, что $V_1\ne V_2$. Тогда существует некоторый кусок торта $Z\subseteq U$, такой, что $V_1(Z)>V_2(Z)$. Пусть $\bar{Z}$ будет дополнением $Z$. Тогда $V_2(\bar{Z})>V_1(\bar{Z})$. Это означает, что $V_1(Z)+V_2(\bar{Z})>1$. Однако $w_1+w_2⩽1$. Следовательно, либо $V_1(Z)>w_1$, либо $V_2(\bar{Z})>w_2$. Предположим без потери общности, что неравенства $V_1(Z)>V_2(Z)$ и $V_1(Z)>w_1$ верны.

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

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

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

• В матрице $\text{diag}(M_{X^1})$ первый элемент равен $V_1(Z)$, второй элемент равен $V_2(\bar{Z})$, остальные элементы равны 0.
• В матрице $\text{diag}(M_{X^i})$ (для $i⩾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$, можно доказать, что $\mathrm{\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 конечно-аддитивна, но не Шаблон:Не переведено 5.

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

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

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

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

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

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

$\frac{V_1(X_1)}{w_1},\frac{V_2(X_2)}{w_2},\dots ,\frac{V_n(X_n)}{w_n}$

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

$\frac{V_1(X_1)}{w_1}⩽\frac{V_2(X_2)}{w_2}⩽\dots ⩽\frac{V_n(X_n)}{w_n}$

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

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

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

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

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

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

См. также

• Шаблон:Не переведено 5Шаблон:Sfn
• Теорема Веллера

Литература

• Шаблон:Статья
• Шаблон:Статья
• Шаблон:Статья
• Шаблон:Статья