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

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

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

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

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

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

ГипотезаПравить

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

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

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

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

ПротоколПравить

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

Один кусок с разными оценкамиПравить

Пусть C будет полным тортом. Протокол начинается с конкретного куска торта, скажем $\text{[math]}$ $\text{[math]}$ $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 участниковПравить

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

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

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

Выберем положительное целое q, такое, что $\text{[math]}$ $\text{[math]}$ $d>{\frac {1}{(i-1)i(q(i-1)-1)}}$

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

Участник №1 остаётся со значением $\text{[math]}$ $\text{[math]}$ ${\frac {(qi-1)-q}{qi-1}}={\frac {q(i-1)-1}{qi-1}}$ его предыдущего значения, которое было равно $\text{[math]}$ $\text{[math]}$ ${\frac {1}{i-1}}+d$ (по определению d). Первый элемент становится $\text{[math]}$ $\text{[math]}$ ${\frac {q(i-1)-1}{(i-1)(qi-1)}}$ , а d становится $\text{[math]}$ $\text{[math]}$ ${\frac {1}{i(i-1)(qi-1)}}$ . Их суммирование даёт, что новое значение превосходит $\text{[math]}$ $\text{[math]}$ ${\frac {(qi-1)(i-1)}{(i-1)i(qi-1)}}={\frac {1}{i}}$ всего торта.

После того, как новый участник после получения q частей от каждого из первых i-1 участников будет иметь полное значение, не меньшее $\text{[math]}$ $\text{[math]}$ ${\frac {q}{qi-1}}>{\frac {1}{i}}$ всего торта.

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

ПримечанияПравить

↑ Steinhaus, 1948, с. 101–4.
↑ Woodall, 1986, с. 300.

ЛитератураПравить

Hugo Steinhaus. The problem of fair division // Econometrica. — 1948. — Т. 16, вып. 1. — JSTOR 1914289.
Woodall D. R. A note on the cake-division problem // Journal of Combinatorial Theory, Series A. — 1986. — Т. 42, вып. 2. — С. 300. — doi:10.1016/0097-3165(86)90101-9.

[_9d527393db3c18d2-1] Steinhaus, 1948, с. 101–4.

[_0c94b738c88532fe-2] Woodall, 1986, с. 300.

[1]

[2]