Сверхпропорциональное деление - Super-proportional division

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

Сверхпропорциональное деление лучше, чем пропорциональное деление, в котором каждый партнер гарантированно получит не менее 1 /п (${\displaystyle V\geq 1/n}$). Однако, в отличие от пропорционального деления, сверхпропорциональное деление существует не всегда. Когда все партнеры имеют одинаковые функции ценности, лучшее, что мы можем сделать, это дать каждому партнеру ровно 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 такой, что: ${\displaystyle d>{\frac {1}{(i-1)i(q(i-1)-1)}}}$

Попросите партнера №1 разделить свою долю между ${\displaystyle qi-1}$ предметы, которые он считает равноценными, и позволяет новому партнеру выбирать ${\displaystyle q}$ предметы, которые он считает самыми ценными.

Партнер №1 остается со значением ${\displaystyle {\frac {(qi-1)-q}{qi-1}}={\frac {q(i-1)-1}{qi-1}}}$ его предыдущей стоимости, которая была ${\displaystyle {\frac {1}{i-1}}+d}$ (по определению d). Первый элемент становится ${\displaystyle {\frac {q(i-1)-1}{(i-1)(qi-1)}}}$ и d становится ${\displaystyle {\frac {1}{i(i-1)(qi-1)}}}$; их суммирование дает, что новое значение больше, чем: ${\displaystyle {\frac {(qi-1)(i-1)}{(i-1)i(qi-1)}}={\frac {1}{i}}}$ всего торта.

Что касается нового партнера, после принятия q штуки с каждого из первых я-1 партнер, его общая стоимость не менее: ${\displaystyle {\frac {q}{qi-1}}>{\frac {1}{i}}}$ всего торта.

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

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

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