Процедура «последний уменьшивший»

Во время второй мировой войны польский еврейский математик Гуго Штейнгауз, прятавшийся от нацистов, заинтересовался вопросом, как разделить ресурс справедливо. Вдохновлённый процедурой «Дели-и-выбирай» дележа торта между двумя братьями, он спросил своих студентов, Стефана Банаха и Бронислава Кнастера, найти процедуру, которая может работать для большего числа людей, и опубликовал их решение[1].

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

Ниже приведено авторское описание протокола дележа:

«Имеются участники A, B, C,.. N. Участник A отрезает от торта произвольный кусок. Участник B имеет теперь право, но не обязан, уменьшить кусок, отрезав часть. После того, как он это сделал, C имеет право (но не обязанность) уменьшить уже уменьшенный (или не уменьшенный) кусок и так далее до участника N. Правило обязывает последнего уменьшившего (отрезавшего) забрать свою часть. Этот участник выбывает из дележа и оставшиеся n−1 участников начинают ту же самую игру с остатком торта. После того, как число участников сократится до двух, они применяют классическое правило дележа пополам.»

Каждый участник имеет метод, который гарантирует, чтобы он получил кусок со значением, не меньшим ${\displaystyle {\tfrac {1}{n}}}$. Метод следующий: всегда режь текущий кусок, чтобы оставшееся значение было ${\displaystyle {\tfrac {1}{n}}}$ для тебя. Имеется два варианта — либо ты получишь кусок, который ты отрезал, либо другой человек получит меньшую часть, которую ты оцениваешь меньше чем ${\displaystyle {\tfrac {1}{n}}}$. В последнем случае имеется n−1 оставшихся участников и оценка оставшегося торта больше ${\displaystyle {\tfrac {n-1}{n}}}$. По индукции можно доказать, что полученное значение будет не меньше ${\displaystyle {\tfrac {1}{n}}}$.

Протокол «Последний уменьшивший» дискретен и его можно осуществить по раундам. В худшем случае нужно будет ${\displaystyle {\tfrac {n\times (n-1)}{2}}=O(n^{2})}$ действий — по одному действию на раунд.

Однако большинство этих ${\displaystyle O(n^{2})}$ действий не являются реальными разрезами, то есть Алиса может пометить желаемый кусок на бумаге, а другой участник уменьшает его на том же листе бумаги, и так далее. Только «последний уменьшивший» должен реально резать торт. Таким образом, нужно только n−1 разрезов.

Процедура очень либеральна относительно разрезов. Разрезы, сделанные участниками, могут иметь любую форму. Они даже могут быть несвязными. С другой стороны, можно ограничить разрезы для гарантии, чтобы куски имели приемлемую форму. В частности:

• Если исходный торт связен, то можно гарантировать, чтобы каждый кусок был связным (непрерывным).
• Если исходный торт является выпуклым множеством, то можно гарантировать, что каждый кусок будет выпуклым.
• Если исходный торт является прямоугольником, то можно гарантировать, что каждый кусок будет прямоугольником.
• Если исходный торт является треугольником, то можно гарантировать, что каждый кусок будет треугольником.

Непрерывная по времени версия протокола может быть исполнена с помощью процедуры «Движущийся нож» Дубинса — Спеньера[2]. Это был первый пример непрерывной процедуры справедливого дележа. Нож продвигается над тортом слева направо. Любой участник может сказать «стоп», если считает, что значение куска слева от ножа составляет ${\displaystyle 1/n}$. Торт режется и участник, сказавший «стоп», получает этот кусок. Повторяем с оставшимся тортом и участниками. Последний участник получает остаток торта. Аналогично процедуре «последний уменьшивший» эта процедура может быть использована для получения непрерывных кусков для каждого участника.

Если имеется 3 и более участников, разбиение, полученное с помощью протокола «последний уменьшивший», не всегда свободно от зависти. Например, предположим, что первый участник Алиса получает кусок (который она оценивает в 1/3). Затем другие два участника, Боб и Чарли, делят оставшуюся часть справедливо, по их мнению, но по мнению Алисы, доля Боба стоит 2/3, в то время как доля Чарли стоит 0. Получается, что Алиса завидует Бобу.

Простое решение[3] заключается в позволении возврата. То есть участник, который выиграл кусок по протоколу «последний уменьшивший», не выбывает из игры, а может оставаться в игре и участвовать в следующих шагах. Если он выигрывает опять, он должен вернуть свой текущий кусок в торт. Чтобы протокол наверняка завершился, мы выбираем некоторую константу ${\displaystyle \varepsilon }$ и добавляем правило, что каждый участник может вернуться в игру не более ${\displaystyle {\tfrac {1}{\varepsilon }}}$ раз.

В версии с возвратом каждый участник имеет метод, гарантирующий, что он получит кусок, значение которого не меньше самого большого куска минус ${\displaystyle \varepsilon }$. Метод следующий: всегда отрезаем текущий кусок так, чтобы оставшаяся часть имела значение ${\displaystyle \varepsilon }$ плюс твой текущий кусок. Это гарантирует, что значение твоего куска растёт на ${\displaystyle \varepsilon }$ каждый раз, когда ты выигрываешь, а когда ты не выигрываешь, значение выигравшего не превосходит твоего собственного значения. Таким образом, уровень зависти не превосходит ${\displaystyle \varepsilon }$.

Время работы алгоритма не превосходит ${\displaystyle {\tfrac {n^{2}}{\varepsilon }}}$, поскольку имеется не более ${\displaystyle {\tfrac {n}{\varepsilon }}}$ шагов и на каждом шаге мы опрашиваем ${\displaystyle n}$ участников.

Недостатком приближённой версии без зависти является то, что куски будут не обязательно связными, поскольку куски постоянно возвращаются в торт и перераспределяются. См. Завистливое разрезание торта#Связные куски для других решений этой проблемы.

Процедура «Последний уменьшивший» улучшалась позднее разными способами. Подробности см. в статье Пропорциональный делёж.