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

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

Сверхпропорциональное деление лучше, чем пропорциональное деление, в котором каждый партнер гарантированно получит не менее 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 д> { гидроразрыва {1} {(я-1) я (д (я-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} {я-1}} + d}$ (по определению d). Первый элемент становится ${ Displaystyle { гидроразрыва {д (я-1) -1} {(я-1) (ци-1)}}}$ и d становится ${ Displaystyle { гидроразрыва {1} {я (я-1) (ци-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}}}$ всего торта.

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

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