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

Super-proportional division

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

Сверхпропорциональное деление лучше, чем пропорциональное деление, в котором каждый партнер гарантированно получит не менее 1 /п (). Однако, в отличие от пропорционального деления, сверхпропорциональное деление существует не всегда. Когда все партнеры имеют одинаковые функции ценности, лучшее, что мы можем сделать, это дать каждому партнеру ровно 1 /п.

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

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

Гипотеза

О существовании суперпропорционального деления впервые предположили еще в 1948 году:[1]

Попутно можно сказать, что если есть два (или более) партнера с разными оценками, существует разделение, дающее каждому больше, чем ему причитается (Knaster); этот факт опровергает распространенное мнение о том, что различия в оценках затрудняют справедливое разделение.

Доказательство существования

Первое опубликованное доказательство существования сверхпропорционального деления было следующим: следствие теоремы Дубинса – Спаниера о выпуклости. Это был чисто экзистенциальное доказательство на основе аргументов выпуклости.

Протокол

Протокол для поиска суперпропорционального деления был представлен в 1986 году.[2]

Единственная часть несогласия

Позволять C быть весь торт. Протокол начинается с определенного куска торта, скажем, X ⊆ C, который по-разному оценивается двумя партнерами. Назовите этих партнеров Алисой и Бобом.

Позволять а = VАлиса(ИКС) и б = VБоб(ИКС) и предположим, что w.l.o.g. который б> а.

Два несогласия

Найдите рациональное число между б и а, сказать п / д такой, что б> р / д> а. Попросите Боба разделить Икс к п равные части и разделить С Х к q-p равные части.

По нашим предположениям, Боб ценит каждый кусок Икс как более 1 /q и каждый кусок С Х меньше чем 1 /q. Но для Алисы по крайней мере один кусок Икс (сказать, Y) должно иметь значение менее 1 /q и хотя бы один кусок С Х (сказать, Z) должно иметь значение больше 1 /q.

Итак, теперь у нас есть две штуки, Y и Z, такое, что:

VБоб(Y)> VБоб(Z)
VАлиса(Y) Алиса(Z)

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

Пусть Алиса и Боб разделят остаток C Y Z между ними пропорционально (например, используя разделяй и выбирай). Добавлять Z к части Алисы и добавить Y к части Боба.

Теперь каждый партнер думает, что его / ее распределение строго лучше, чем другое распределение, поэтому его значение строго больше 1/2.

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

Расширение этого протокола на п партнеры основаны на Протокол Финка "Lone Chooser".

Предположим, у нас уже есть суперпропорциональное деление на я-1 партнер (для i≥3). Теперь партнер #я входит в группу, и мы должны дать ему небольшой кусочек от каждого из первых я-1 партнеры, так что новый дивизион все еще сверхпропорциональный.

Рассмотрим, например, партнер №1. Позволять d быть разницей между текущим значением партнера №1 и (1 / (я-1)). Поскольку текущее деление суперпропорционально, мы знаем, что d> 0.

Выберите положительное целое число q такой, что:

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

Партнер №1 остается со значением его предыдущей стоимости, которая была (по определению d). Первый элемент становится и d становится ; их суммирование дает, что новое значение больше, чем: всего торта.

Что касается нового партнера, после принятия q штуки с каждого из первых я-1 партнер, его общая стоимость не менее: всего торта.

Это доказывает, что новое деление также сверхпропорционально.

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

  1. ^ Штейнхаус, Гюго (1948). «Проблема справедливого разделения». Econometrica. 16 (1): 101–4. JSTOR 1914289.
  2. ^ Вудалл, Д. Р. (1986). «Заметка по проблеме разделения торта». Журнал комбинаторной теории, серия А. 42 (2): 300. Дои:10.1016/0097-3165(86)90101-9.