Теоремы Дубинса – Спаньера. - Dubins–Spanier theorems

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

Следствия

Раздел консенсуса

Перегородка для торта ${\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}$

В выпуклость Часть теоремы 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 }$

В разделе ${\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}$ к п штук (одна штука на партнера) называется сверхпропорциональное деление с весами ${\displaystyle w_{1},w_{2},...,w_{n}}$ если:

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

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

Теорема — В этих обозначениях пусть ${\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}}$, то существует сверхпропорциональное деление, т. е. достаточно и необходимого условия.

Эскиз доказательства

Предположим, что w.l.o.g. который ${\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}}$. Предположим, что w.l.o.g. который ${\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\geq 2}$): перегородка, которая передает партнеру весь торт ${\displaystyle i}$ и ничего остальным.

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

• В ${\displaystyle {\textrm {diag}}(M_{X^{1}})}$, запись 1 - ${\displaystyle V_{1}(Z)}$, запись 2 - ${\displaystyle V_{2}({\overline {Z}})}$, а остальные записи - 0.
• В ${\displaystyle {\textrm {diag}}(M_{X^{i}})}$ (за ${\displaystyle i\geq 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}$ к п штук (одна штука на партнера) называется утилитарный -оптимально если он максимизирует сумму значений. То есть максимизирует:

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

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

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

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

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

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

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

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

Перегородка для торта ${\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. Дубинс, Лестер Эли; Spanier, Эдвин Генри (1961). «Как правильно разрезать торт». Американский математический ежемесячник. 68: 1. Дои:10.2307/2311357. JSTOR  2311357.
2. Дворецкий, А .; Wald, A .; Вулфовиц, Дж. (1951). «Отношения между некоторыми диапазонами векторных мер». Тихоокеанский математический журнал. 1: 59. Дои:10.2140 / pjm.1951.1.59.
3. Далл'Аглио, Марко (2001). «Задача оптимизации Дубинса – Спаниера в теории справедливого деления». Журнал вычислительной и прикладной математики. 130: 17. Дои:10.1016 / S0377-0427 (99) 00393-3.
4. Нейман, Дж (1946). "Un théorèm dʼexistence". C. R. Acad. Наука. 222: 843–845.