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

Эта статья находится на начальном уровне проработки, в одной из её версий выборочно используется текст из источника, распространяемого под свободной лицензией
Материал из энциклопедии Руниверсалис

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

Условия

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

Имеется [math]\displaystyle{ n }[/math] участников. Любой участник [math]\displaystyle{ i }[/math] имеет персональную меру предпочтений [math]\displaystyle{ V_i: \mathbb{U} \to \mathbb{R} }[/math]. Эта функция определяет, насколько каждое подмножество [math]\displaystyle{ U }[/math] ценно для участника.

Пусть [math]\displaystyle{ X }[/math] будет разбиением [math]\displaystyle{ U }[/math] на [math]\displaystyle{ k }[/math] измеримых множеств: [math]\displaystyle{ U = X_1 \sqcup \cdots \sqcup X_k }[/math]. Определим матрицу [math]\displaystyle{ M_X }[/math] как матрицу [math]\displaystyle{ n\times k }[/math]:

[math]\displaystyle{ M_X[i,j] = V_i(X_j) }[/math]

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

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

[math]\displaystyle{ \mathbb{M} = \{M_X \mid X }[/math] является k-разбиением [math]\displaystyle{ U\} }[/math]

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

Утверждения

Если все меры предпочтений [math]\displaystyle{ V_i }[/math] счётно-аддитивны[en] и неатомарны, то:

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

Следствия

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

Разрезание торта [math]\displaystyle{ X }[/math] на k частей называется согласованным разрезанием с весами [math]\displaystyle{ w_1, w_2, \ldots, w_k }[/math] (говорят также о точном дележе), если:

[math]\displaystyle{ \forall i \in \{1,\dots, n\}: \forall j \in \{1,\dots, k\}: V_i(X_j) = w_j }[/math]

То есть: есть согласие всех участников, что значение куска j равно в точности [math]\displaystyle{ w_j }[/math].

Предположим теперь, что [math]\displaystyle{ w_1, w_2, \ldots, w_k }[/math] являются весами, сумма которых равна 1:

[math]\displaystyle{ \sum_{j=1}^k w_j =1 }[/math]

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

[math]\displaystyle{ \forall i \in \{1,\dots, n\}: V_i(U) = 1 }[/math]

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

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

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

[math]\displaystyle{ X^j_j = U }[/math]
[math]\displaystyle{ \forall r\neq j: X^j_r = \emptyset }[/math]

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

Согласно выпуклости, имеется разбиение [math]\displaystyle{ X }[/math], такое, что

[math]\displaystyle{ M_X = \sum_{j=1}^k w_j\cdot M_{X^j} }[/math]

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

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

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

Разрезание торта [math]\displaystyle{ X }[/math] на n кусков (по одному на каждого участника дележа) называется суперпропорциональным дележом с весами [math]\displaystyle{ w_1, w_2, ..., w_n }[/math], если

[math]\displaystyle{ \forall i \in 1\dots n: V_i(X_i) \gt w_i }[/math]

То есть кусок, предназначаемый участнику [math]\displaystyle{ i }[/math] строго, более предпочтителен для него, чем кусок, на который он имеет право. Следующее утверждение является теоремой Дубинса — Спеньера о существовании суперпропорционального дележа.

Теорема Пусть [math]\displaystyle{ w_1, w_2, ..., w_n }[/math] будут весами, сумма которых равна 1. Предположим, что точка [math]\displaystyle{ w:=(w_1, w_2, ..., w_n) }[/math] является внутренней точкой (n-1)-мерного симплекса с попарно различными координатами и пусть меры полезности [math]\displaystyle{ V_1, ..., V_n }[/math] нормализованы так, что каждый участник оценивает весь торт в точности в 1 (то есть меры являются неатомарными вероятностными мерами). Если хотя бы две меры [math]\displaystyle{ V_i, V_j }[/math] не совпадают ( [math]\displaystyle{ V_i\neq V_j }[/math]), то суперпропорциональный делёж существует.

Условие, что меры полезности [math]\displaystyle{ V_1, ..., V_n }[/math] не все идентичны, необходимо. В противном случае сумма [math]\displaystyle{ \sum_{i=1}^n V_i(X_i) =\sum_{i=1}^n V_1(X_i) \gt \sum_{i=1}^n w_i =1 }[/math] приводит к противоречию.

Тогда, если все меры полезности счётно-аддитивны и неатомарны, а также существуют два участника [math]\displaystyle{ i,j }[/math] такие, что [math]\displaystyle{ V_i\neq V_j }[/math], то суперпропорциональный делёж существует. То есть необходимое условие является также и достаточным.

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

Предположим без потери общности, что [math]\displaystyle{ V_1 \neq V_2 }[/math]. Тогда существует некоторый кусок торта [math]\displaystyle{ Z\subseteq U }[/math], такой, что [math]\displaystyle{ V_1(Z)\gt V_2(Z) }[/math]. Пусть [math]\displaystyle{ \overline{Z} }[/math] будет дополнением [math]\displaystyle{ Z }[/math]. Тогда [math]\displaystyle{ V_2(\overline{Z})\gt V_1(\overline{Z}) }[/math]. Это означает, что [math]\displaystyle{ V_1(Z) + V_2(\overline{Z}) \gt 1 }[/math]. Однако [math]\displaystyle{ w_1+w_2\leqslant 1 }[/math]. Следовательно, либо [math]\displaystyle{ V_1(Z)\gt w_1 }[/math], либо [math]\displaystyle{ V_2(\overline{Z})\gt w_2 }[/math]. Предположим без потери общности, что неравенства [math]\displaystyle{ V_1(Z)\gt V_2(Z) }[/math] и [math]\displaystyle{ V_1(Z)\gt w_1 }[/math] верны.

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

  • [math]\displaystyle{ X^1 }[/math]: разрезание, которое отдаёт [math]\displaystyle{ Z }[/math] участнику 1, [math]\displaystyle{ \overline{Z} }[/math] участнику 2 и ничего остальным участникам.
  • [math]\displaystyle{ X^i }[/math] (для [math]\displaystyle{ i\geqslant 2 }[/math]): разрезание, которое даёт весь торт участнику [math]\displaystyle{ i }[/math] и ничего остальным.

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

  • В матрице [math]\displaystyle{ \textrm{diag}(M_{X^1}) }[/math] первый элемент равен [math]\displaystyle{ V_1(Z) }[/math], второй элемент равен [math]\displaystyle{ V_2(\overline{Z}) }[/math], остальные элементы равны 0.
  • В матрице [math]\displaystyle{ \textrm{diag}(M_{X^i}) }[/math] (для [math]\displaystyle{ i\geqslant 2 }[/math]), элемент [math]\displaystyle{ i }[/math] равен 1, а другие элементы равны 0.

По условию выпуклости для любого множества весов [math]\displaystyle{ z_1, z_2, ..., z_n }[/math] существует разбиение [math]\displaystyle{ X }[/math], такое, что

[math]\displaystyle{ M_X = \sum_{j=1}^n {z_j\cdot M_{X^j}}. }[/math]

Можно выбрать веса [math]\displaystyle{ z_i }[/math] таким образом, что на диагонали [math]\displaystyle{ M_X }[/math], находятся в том же отношении, что и веса [math]\displaystyle{ w_i }[/math]. Поскольку мы предположили, что [math]\displaystyle{ V_1(Z)\gt w_1 }[/math], можно доказать, что [math]\displaystyle{ \forall i \in 1\dots n: V_i(X_i) \gt w_i }[/math], так что [math]\displaystyle{ X }[/math] является суперпропорциональным дележом.

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

Разрезание торта [math]\displaystyle{ X }[/math] на n кусков (по одному куску на каждого участника) называется утилитарно-оптимально, если оно максимизирует сумму оценок полезности. То есть оно максимизирует

[math]\displaystyle{ \sum_{i=1}^n{V_i(X_i)} }[/math]

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

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

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

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

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

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

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

[math]\displaystyle{ {V_1(X_1) \over w_1}, {V_2(X_2) \over w_2}, \dots , {V_n(X_n) \over w_n} }[/math]

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

[math]\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} }[/math]

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

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

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

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

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

См. также

Примечания

  1. ↑ Dubins, Spanier, 1961, с. 1.
  2. ↑ Dvoretzky, Wald, Wolfowitz, 1951, с. 59.
  3. ↑ Dubins, Spanier, 1961, с. 5.
  4. ↑ 4,0 4,1 Dubins, Spanier, 1961, с. 7.
  5. ↑ Dubins, Spanier, 1961, с. 8.
  6. ↑ Dall'Aglio, 2001, с. 17.
  7. ↑ 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.
Источник — https://xn--h1ajim.xn--p1ai/index.php?title=Теоремы_Дубинса_—_Спеньера&oldid=5859728