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

Dubins–Spanier theorems

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

Параметр

Есть набор , и набор который является сигма-алгебра подмножеств .

Есть партнеры. Каждый партнер имеет личную ценность . Эта функция определяет, сколько каждого подмножества стоит для этого партнера.

Позволять раздел к измеримые множества: . Определить матрицу в дальнейшем матрица:

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

Позволять - набор всех таких матриц (для одинаковых величин, одинаковых , и разные разделы):

Теоремы Дубинса – Спаниера касаются топологических свойств .

Заявления

Если все меры стоимости находятся счетно-аддитивный и неатомный, тогда:

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

Следствия

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

Перегородка для торта к k штук называется консенсусное разделение с весами (также называемый точное деление) если:

То есть, все партнеры согласны с тем, что ценность штуки j точно .

Предположим, что с этого момента веса, сумма которых равна 1:

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

В выпуклость Часть теоремы DS означает, что:[1]:5

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

ДОКАЗАТЕЛЬСТВО: Для каждого , определите раздел следующее:

В разделе , все партнеры ценят -й кусок как 1, а все остальные как 0. Следовательно, в матрице , есть на -й столбец и нули везде.

По выпуклости имеется разбиение такой, что:

В этой матрице -й столбец содержит только значение . Это означает, что в разделе , все партнеры ценят -я штука точно так же .

Примечание: это следствие подтверждает предыдущее утверждение Хьюго Штайнхаус. Это также дает утвердительный ответ на проблема Нила при условии, что существует только конечное количество высот наводнения.

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

Перегородка для торта к п штук (одна штука на партнера) называется сверхпропорциональное деление с весами если:

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

Теорема — В этих обозначениях пусть - веса, сумма которых равна 1, предположим, что точка является внутренней точкой (n-1) -мерного симплекса с попарно разными координатами, и предположим, что величина измеряет нормализованы так, что каждый партнер оценивает весь торт как ровно 1 (то есть они не являются атомарными вероятностными мерами). Если хотя бы две меры не равны ( ), то существуют сверхпропорциональные деления.

Гипотеза о том, что ценность измеряет не тождественны надо. В противном случае сумма приводит к противоречию.

А именно, если все меры стоимости являются счетно-аддитивными и неатомарными, и если есть два партнера такой, что , то существует сверхпропорциональное деление, т. е. достаточно и необходимого условия.

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

Предположим, что w.l.o.g. который . Тогда есть кусок пирога, , так что . Позволять быть дополнением ; тогда . Это означает, что . Тем не мение, . Следовательно, либо или же . Предположим, что w.l.o.g. который и верны.

Определите следующие разделы:

  • : раздел, который дает партнеру 1, партнеру 2 и ничего остальным.
  • (за ): перегородка, которая передает партнеру весь торт и ничего остальным.

Здесь нас интересуют только диагонали матриц , которые представляют оценки партнеров по собственному усмотрению:

  • В , запись 1 - , запись 2 - , а остальные записи - 0.
  • В (за ), Вход равно 1, а остальные элементы равны 0.

По выпуклости для любого набора весов есть перегородка такой, что:

Есть возможность выбора веса такое, что по диагонали , записи находятся в том же соотношении, что и веса . Поскольку мы предположили, что , можно доказать, что , так это сверхпропорциональное деление.

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

Перегородка для торта к п штук (одна штука на партнера) называется утилитарный-оптимально если он максимизирует сумму значений. То есть максимизирует:

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

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

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

Если все меры стоимости являются счетно-аддитивными и неатомарными,
тогда существует утилитарно-оптимальное деление.

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

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

Перегородка для торта к п штук (одна штука на партнера) называется лексимин-оптимально с весами если он максимизирует лексикографически упорядоченный вектор относительных значений. То есть максимизирует следующий вектор:

где партнеры индексируются таким образом, что:

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

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

Если все меры стоимости являются счетно-аддитивными и неатомарными,
тогда существует лексимин-оптимальное деление.

Дальнейшие разработки

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

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

Рекомендации

  1. ^ а б c d е Дубинс, Лестер Эли; 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.