Суперпропорциональный делёж

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

Суперпропорциональный делёж лучше, чем пропорциональный делёж, в котором каждый участник гарантированно получает по меньшей мере 1/n (${\displaystyle V\geqslant 1/n}$). Однако, в отличие от пропорционального дележа, суперпропорциональный делёж существует не всегда. Когда все участники дележа имеют в точности те же функции оценок, лучшее, что мы можем дать каждому участнику, это в точности 1/n.

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

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

Существование суперпропорционального дележа было предложено в виде гипотезы в 1948 году^[1].

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

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

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

Пусть C будет полным тортом. Протокол начинается с конкретного куска торта, скажем ${\displaystyle X\subseteq C}$, который оценивается двумя участниками. Скажем, это будут Алиса и Боб.

Пусть a=V_Алиса(X) и b=V_Боб(X) и предположим без потери общности, что b>a.

Найдём рациональное число между b и a, скажем p/q, такое, что b > p/q > a. Попросим Боба разрезать X на p равных частей и разрезать C \ X на q-p равных частей.

По нашим предположениям, значения Боба для каждого куска X больше 1/q, а для каждого куска C \ X меньше 1/q. Однако для Алисы по меньшей мере один кусок X (скажем, Y) должно иметь значение, меньшее 1/q, и по меньшей мере один кусок C\X (say, Z) должен иметь значение, большее 1/q.

Таким образом, мы имеем два куска Y и Z, такие, что:

V_Боб(Y)>V_Боб(Z)

V_Алиса(Y)<V_Алиса(Z)

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

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

Расширение этого протокола на n участников основано на протоколе «Одиночного Выбирающего» Финка.

Предположим, что у нас уже есть суперпропорциональный делёж для i-1 участников (для ${\displaystyle i\geqslant 3}$). Новый участник №i вступает в игру и нам следует отдать ему некоторые доли от первых i-1 участников так, чтобы новый делёж оставался суперпропорциональным.

Рассмотрим, например, партнёра №1. Пусть d будет разницей между текущим значением партнёра №1 и (1/(i-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 частей от каждого из первых i-1 участников будет иметь полное значение, не меньшее ${\displaystyle {\frac {q}{qi-1}}>{\frac {1}{i}}}$ всего торта.

Это доказывает, что новый делёж является также суперпропорциональным.