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

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

УсловияПравить

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

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

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

$M_X[i,j]=V_i(X_j)$$M_{X}[i,j]=V_{i}(X_{j})$ 

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

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

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

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

УтвержденияПравить

Если все меры предпочтений $V_i$$V_i$  счётно-аддитивны^[en] и неатомарны, то:

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

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

СледствияПравить

Согласованный делёжПравить

Разрезание торта $X$$X$  на k частей называется согласованным разрезанием с весами $w_1,w_2,\dots <!--\; \dots \; -->,w_k$$w_{1},w_{2},\ldots ,w_{k}$  (говорят также о точном дележе), если:

$\mathrm{\forall <!--\; \forall \; -->}i\in <!--\; \in \; -->\{1,\dots <!--\; \dots \; -->,n\}:\mathrm{\forall <!--\; \forall \; -->}j\in <!--\; \in \; -->\{1,\dots <!--\; \dots \; -->,k\}:V_i(X_j)=w_j$$\forall i\in \{1,\dots ,n\}:\forall j\in \{1,\dots ,k\}:V_{i}(X_{j})=w_{j}$ 

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

Предположим теперь, что $w_1,w_2,\dots <!--\; \dots \; -->,w_k$$w_{1},w_{2},\ldots ,w_{k}$  являются весами, сумма которых равна 1:

$\underset{j=1}{\overset{k}{\sum <!--\; \sum \; -->}}{w}_j=1$$\sum _{j=1}^{k}w_{j}=1$ 

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

$\mathrm{\forall <!--\; \forall \; -->}i\in <!--\; \in \; -->\{1,\dots <!--\; \dots \; -->,n\}:V_i(U)=1$$\forall i\in \{1,\dots ,n\}:V_{i}(U)=1$ 

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

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

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

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

$X_j^j=U$$X_{j}^{j}=U$ 

$\mathrm{\forall <!--\; \forall \; -->}r\ne <!--\; \ne \; -->j:X_r^j=\mathrm{\varnothing <!--\; \varnothing \; -->}$$\forall r\neq j:X_{r}^{j}=\emptyset$ 

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

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

$M_X=\underset{j=1}{\overset{k}{\sum <!--\; \sum \; -->}}{w}_j\cdot <!--\; \cdot \; -->M_{X^j}$$M_{X}=\sum _{j=1}^{k}w_{j}\cdot M_{X^{j}}$ 

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

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

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

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

$\mathrm{\forall <!--\; \forall \; -->}i\in <!--\; \in \; -->1\dots <!--\; \dots \; -->n:V_i(X_i)>w_i$$\forall i\in 1\dots n:V_{i}(X_{i})>w_{i}$ 

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

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

Условие, что меры полезности $V_1,...,V_n$$V_{1},...,V_{n}$  не все идентичны, необходимо. В противном случае сумма $\underset{i=1}{\overset{n}{\sum <!--\; \sum \; -->}}{V}_i(X_i)=\underset{i=1}{\overset{n}{\sum <!--\; \sum \; -->}}{V}_1(X_i)>\underset{i=1}{\overset{n}{\sum <!--\; \sum \; -->}}{w}_i=1$$\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$$i,j$  такие, что $V_i\ne <!--\; \ne \; -->V_j$$V_{i}\neq V_{j}$ , то суперпропорциональный делёж существует. То есть необходимое условие является также и достаточным.

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

Предположим без потери общности, что $V_1\ne <!--\; \ne \; -->V_2$$V_{1}\neq V_{2}$ . Тогда существует некоторый кусок торта $Z\subseteq <!--\; \subseteq \; -->U$$Z\subseteq U$ , такой, что $V_1(Z)>V_2(Z)$$V_{1}(Z)>V_{2}(Z)$ . Пусть $\stackrel{¯<!--\; ¯\; -->}{Z}$${\overline {Z}}$  будет дополнением $Z$$Z$ . Тогда $V_2(\stackrel{¯<!--\; ¯\; -->}{Z})>V_1(\stackrel{¯<!--\; ¯\; -->}{Z})$$V_{2}({\overline {Z}})>V_{1}({\overline {Z}})$ . Это означает, что $V_1(Z)+V_2(\stackrel{¯<!--\; ¯\; -->}{Z})>1$$V_{1}(Z)+V_{2}({\overline {Z}})>1$ . Однако $w_1+w_2⩽<!--\; ⩽\; -->1$$w_{1}+w_{2}\leqslant 1$ . Следовательно, либо $V_1(Z)>w_1$$V_{1}(Z)>w_{1}$ , либо $V_2(\stackrel{¯<!--\; ¯\; -->}{Z})>w_2$$V_{2}({\overline {Z}})>w_{2}$ . Предположим без потери общности, что неравенства $V_1(Z)>V_2(Z)$$V_{1}(Z)>V_{2}(Z)$  и $V_1(Z)>w_1$$V_{1}(Z)>w_{1}$  верны.

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

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

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

• В матрице $\text{diag}(M_{X^1})$${\textrm {diag}}(M_{X^{1}})$  первый элемент равен $V_1(Z)$$V_{1}(Z)$ , второй элемент равен $V_2(\stackrel{¯<!--\; ¯\; -->}{Z})$$V_{2}({\overline {Z}})$ , остальные элементы равны 0.
• В матрице $\text{diag}(M_{X^i})$${\textrm {diag}}(M_{X^{i}})$  (для $i⩾<!--\; ⩾\; -->2$$i\geqslant 2$ ), элемент $i$$i$  равен 1, а другие элементы равны 0.

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

$M_X=\underset{j=1}{\overset{n}{\sum <!--\; \sum \; -->}}{z}_j\cdot <!--\; \cdot \; -->M_{X^j}.$$M_{X}=\sum _{j=1}^{n}{z_{j}\cdot M_{X^{j}}}.$ 

Можно выбрать веса $z_i$$z_{i}$  таким образом, что на диагонали $M_X$$M_{X}$ , находятся в том же отношении, что и веса $w_i$$w_{i}$ . Поскольку мы предположили, что $V_1(Z)>w_1$$V_{1}(Z)>w_{1}$ , можно доказать, что $\mathrm{\forall <!--\; \forall \; -->}i\in <!--\; \in \; -->1\dots <!--\; \dots \; -->n:V_i(X_i)>w_i$$\forall i\in 1\dots n:V_{i}(X_{i})>w_{i}$ , так что $X$$X$  является суперпропорциональным дележом.

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

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

$\underset{i=1}{\overset{n}{\sum <!--\; \sum \; -->}}{V}_i(X_i)$$\sum _{i=1}^{n}{V_{i}(X_{i})}$ 

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

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

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

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

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

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

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

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

$\frac{V_1(X_1)}{w_1},\frac{V_2(X_2)}{w_2},\dots <!--\; \dots \; -->,\frac{V_n(X_n)}{w_n}$${V_{1}(X_{1}) \over w_{1}},{V_{2}(X_{2}) \over w_{2}},\dots ,{V_{n}(X_{n}) \over w_{n}}$ 

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

$\frac{V_1(X_1)}{w_1}⩽<!--\; ⩽\; -->\frac{V_2(X_2)}{w_2}⩽<!--\; ⩽\; -->\cdots <!--\; \cdots \; -->⩽<!--\; ⩽\; -->\frac{V_n(X_n)}{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}}$ 

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

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

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

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

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

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

См. такжеПравить

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