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

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

Имеется участников. Любой участник имеет персональную меру предпочтений . Эта функция определяет, насколько каждое подмножество ценно для участника.

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

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

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

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

Утверждения Если все меры предпочтений и неатомарны, то:

компактно; выпукло.

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

Следствия Согласованный делёж Разрезание торта на k частей называется согласованным разрезанием с весами (говорят также о точном дележе), если:

То есть: есть согласие всех участников, что значение куска j равно в точности .

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

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

Из выпуклости в теореме Дубинса — Спеньера следует, что : Если все значения мер счётно-аддитивны и неатомарны, то согласованное разбиение существует.

Доказательство: Для любого определим разбиение следующим образом

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

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

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

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

Суперпропорциональный делёж Разрезание торта на n кусков (по одному на каждого участника дележа) называется суперпропорциональным дележом с весами , если

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

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

Условие, что меры полезности не все идентичны, необходимо. В противном случае сумма приводит к противоречию.

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

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

Предположим без потери общности, что . Тогда существует некоторый кусок торта , такой, что . Пусть будет дополнением . Тогда . Это означает, что . Однако . Следовательно, либо , либо . Предположим без потери общности, что неравенства и верны.

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

Здесь нас интересует только диагональ матрицы , которая представляет оценки участниками из собственных кусков: В матрице первый элемент равен , второй элемент равен , остальные элементы равны 0. В матрице (для ), элемент равен 1, а другие элементы равны 0.

По условию выпуклости для любого множества весов существует разбиение , такое, что

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

Утилитарно-оптимальный делёж Разрезание торта на n кусков (по одному куску на каждого участника) называется утилитарно-оптимально, если оно максимизирует сумму оценок полезности. То есть оно максимизирует

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

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

Из компактности в теореме Дубинса — Спеньера немедленно следует, что: Если все меры предпочтений счётно-аддитивны и неатомарны, то утилитарно-оптимальный делёж существует.

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

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

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

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

Из компактности в теореме Дубинса — Спеньера немедленно следует, что: Если все меры предпочтений счётно-аддитивны и неатомарны, то лексимин-оптимальный делёж существует.

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

См. также

Теорема Веллера

Примечания

Литература

Категория:Справедливый делёж Категория:Теория меры