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

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

${ Displaystyle M_ {X} [я, j] = V_ {i} (X_ {j})}$

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

Позволять ${ Displaystyle mathbb {M}}$ - набор всех таких матриц (для одинаковых величин, одинаковых ${ displaystyle k}$, и разные разделы):

${ displaystyle mathbb {M} = {M_ {X} mid X { text {is a}} k { text {-часть 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 сумма _ {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 V_ {1}, ..., V_ {n}}$ не тождественны надо. В противном случае сумма ${ displaystyle sum _ {i = 1} ^ {n} V_ {i} (X_ {i}) = sum _ {i = 1} ^ {n} V_ {1} (X_ {i})> сумма _ {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 substeq 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 сумма _ {я = 1} ^ {п} {V_ {я} (X_ {я})}}$

Утилитарно-оптимальные разделения существуют не всегда. Например, предположим ${ 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}) над w_ {1}} leq {V_ {2} (X_ {2}) над w_ {2}} leq dots leq {V_ { n} (X_ {n}) over w_ {n}}}$

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

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

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

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

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

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

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

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

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