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

Процедура последний уменьшивший — это процедура справедливого разрезания торта. Процедура предназначена для распределения неоднородного делимого ресурса, такого как торт на день рождения, и предусматривает n участников дележа с различными предпочтениями для разных частей торта. Процедура позволяет для n человек получить пропорциональный делёж, то есть разделить торт среди них так, что каждый участник получит по меньшей мере ${\tfrac {1}{n}}$ полного значения согласно его собственной (субъективной) оценке. Например, если оценка всего торта Алисой составляет $100 и имеется 5 участников, то Алиса может получить кусок, который она оценивает по меньшей мере в $20, независимо от того, что другие участники думают или делают.

История

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

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

Описание

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

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

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

Вырожденный случай общей функции предпочтений

Алгоритм упрощается в вырожденном случае, когда все участники имеют те же самые функции предпочтения, поскольку участник, сделавший первое оптимальное отрезание, становится и последним уменьшившим. Эквивалентно, каждый участник 1, 2, ..., n−1 в свою очередь отрезает кусок от оставшегося торта. Затем в обратном порядке каждый участник n, n−1, ..., 1 выбирает кусок, на который ещё не было требования..

Анализ

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

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

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

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

Непрерывная версия

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

Приближённая версия без зависти

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

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

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

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

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

Улучшения

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