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

Теоремы теории меры

Теоремы Дубинса–Спаньера — это несколько теорем в теории справедливого разрезания торта . Они были опубликованы Лестером Дубинсом и Эдвином Спаниером в 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{\text{ is a }}k{\text{-partition of }}U\}}$

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

Заявления

Если все меры стоимости являются счетно-аддитивными и неатомарными , то: ${\displaystyle V_{i}}$

• ${\displaystyle \mathbb {M} }$представляет собой компактный набор ;
• ${\displaystyle \mathbb {M} }$является выпуклым множеством .

Это уже доказали Дворецкий, Вальд и Вулфовиц. ^[2]

Следствия

Консенсусный раздел

Разбиение торта на k частей называется консенсусным разбиением с весами (также называется точным делением ), если: ${\displaystyle X}$ ${\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}}$

Предположим, что — веса, сумма которых равна 1: ${\displaystyle w_{1},w_{2},\ldots ,w_{k}}$

${\displaystyle \sum _{j=1}^{k}w_{j}=1}$

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

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

Выпуклая часть теоремы DS подразумевает, что: ^{[1] : 5}

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

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

ДОКАЗАТЕЛЬСТВО: Для каждого определите раздел следующим образом: ${\displaystyle j\in \{1,\dots ,k\}}$ ${\displaystyle X^{j}}$

${\displaystyle X_{j}^{j}=U}$

${\displaystyle \forall r\neq j:X_{r}^{j}=\emptyset }$

В разбиении все партнеры оценивают -ю часть как 1, а все остальные части как 0. Следовательно, в матрице в -м столбце стоят единицы, а во всех остальных столбцах — нули. ${\displaystyle X^{j}}$ ${\displaystyle j}$ ${\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}}$

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

Суперпропорциональное деление

Раздел торта на n частей (по одной части на партнера) называется сверхпропорциональным разделом с весами , если: ${\displaystyle X}$ ${\displaystyle w_{1},w_{2},...,w_{n}}$

${\displaystyle \forall i\in 1\dots n:V_{i}(X_{i})>w_{i}}$

То есть, кусок, отведенный партнеру , строго более ценен для него, чем тот, которого он заслуживает. Следующее утверждение — теорема Дубинса-Спаньера о существовании сверхпропорционального дележа ^{: 6} ${\displaystyle i}$

Теорема  —  В этих обозначениях пусть будут весами, сумма которых равна 1, предположим, что точка является внутренней точкой (n-1)-мерного симплекса с попарно разными координатами, и предположим, что меры стоимости нормализованы таким образом, что каждый партнер оценивает весь торт ровно как 1 (т. е. они являются неатомарными мерами вероятности). Если по крайней мере две из мер не равны ( ), то существуют сверхпропорциональные дележи. ${\displaystyle w_{1},w_{2},...,w_{n}}$ ${\displaystyle w:=(w_{1},w_{2},...,w_{n})}$ ${\displaystyle V_{1},...,V_{n}}$ ${\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}}$

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

Предположим, что wlog, что . Тогда есть некоторый кусок пирога, , такой, что . Пусть будет дополнением к ; тогда . Это означает, что . Однако, . Следовательно, либо , либо . Предположим, что wlog, что и истинны. ${\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}\leq 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}}$: раздел, который дает партнеру 1, партнеру 2 и ничего всем остальным. ${\displaystyle Z}$ ${\displaystyle {\overline {Z}}}$
• ${\displaystyle X^{i}}$(для ): раздел, который отдает весь торт партнеру и ничего всем остальным. ${\displaystyle i\geq 2}$ ${\displaystyle i}$

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

• В запись 1 — это , запись 2 — это , а остальные записи — 0. ${\displaystyle {\textrm {diag}}(M_{X^{1}})}$ ${\displaystyle V_{1}(Z)}$ ${\displaystyle V_{2}({\overline {Z}})}$
• В (для ) запись равна 1, а остальные целые равны 0. ${\displaystyle {\textrm {diag}}(M_{X^{i}})}$ ${\displaystyle i\geq 2}$ ${\displaystyle i}$

В силу выпуклости для каждого набора весов существует разбиение такое, что: ${\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}$

Утилитарно-оптимальное деление

Раздел торта на n частей (по одной части на партнера) называется утилитарно -оптимальным, если он максимизирует сумму ценностей. То есть, он максимизирует: ${\displaystyle X}$

${\displaystyle \sum _{i=1}^{n}{V_{i}(X_{i})}}$

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

Проблема с приведенным выше примером заключается в том, что мера ценности партнера 2 является конечно-аддитивной, но не счетно-аддитивной .

Из компактной части теоремы DS немедленно следует, что: ^{[1] : 7}

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

тогда существует утилитарно-оптимальное разделение.

В этом особом случае неатомарность не требуется: если все меры стоимости являются счетно-аддитивными, то существует утилитарно-оптимальное разбиение. ^{[1] : 7}

Лексимин-оптимальное деление

Разделение торта на n частей (по одной части на партнера) называется лексимин -оптимальным с весами , если оно максимизирует лексикографически упорядоченный вектор относительных значений. То есть, оно максимизирует следующий вектор: ${\displaystyle X}$ ${\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}}\leq {V_{2}(X_{2}) \over w_{2}}\leq \dots \leq {V_{n}(X_{n}) \over w_{n}}}$

Оптимальное по лексимину разбиение максимизирует ценность самого бедного партнера (относительно его веса); при этом оно максимизирует ценность следующего самого бедного партнера (относительно его веса) и т. д.

Из компактной части теоремы DS немедленно следует, что: ^{[1] : 8}

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

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

Дальнейшее развитие событий

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

Смотрите также

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

Ссылки

1. Дубинс, Лестер Эли ; Спаниер, Эдвин Генри (1961). «Как честно разрезать торт». The American Mathematical Monthly . 68 (1): 1–17. doi :10.2307/2311357. JSTOR  2311357.
2. Дворецкий, А.; Вальд, А.; Вольфовиц, Дж. (1951). «Отношения между определенными диапазонами векторных мер». Pacific Journal of Mathematics . 1 : 59–74. doi : 10.2140/pjm.1951.1.59 .
3. Dall'Aglio, Marco (2001). "Проблема оптимизации Дубинса–Спаньера в теории справедливого деления". Журнал вычислительной и прикладной математики . 130 (1–2): 17–40. Bibcode :2001JCoAM.130...17D. doi : 10.1016/S0377-0427(99)00393-3 .
4. Нейман, Дж (1946). «Теорема существования». ЧР акад. Наука . 222 : 843–845.