24.08.2021

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


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

История

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

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

Описание

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

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

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

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

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

Анализ

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

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

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

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

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

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

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

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

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

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

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

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

Улучшения

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


Похожие новости:

Красный бархат (торт)

Красный бархат (торт)
Торт Красный бархат (англ. Red Velvet cake) — шоколадный торт тёмно-красного, ярко-красного или красно-коричневого цвета. Традиционно готовится как слоёный пирог с глазурью из сливочного сыра. Для

Что такое оценка недвижимости для Сбербанка: отвечаем на частые вопросы

Что такое оценка недвижимости для Сбербанка: отвечаем на частые вопросы
Ипотечный кредит от Сбербанка под залог недвижимости – вполне распространенная практика. Однако, чтобы его получить, необходимо провести оценку жилья. Чтобы понять суть процедуры, ответим на самые

Педикюр для коня

Педикюр для коня
Педикюр для коня — думаете, это невозможно? На самом деле это необходимая процедура для каждой лошади. Чтобы кони хорошо бегали, необходимо следить за такой деталью, как копыта.

Вызов ветеринара: что следует знать?

Вызов ветеринара: что следует знать?
Иногда питомцу требуется неотложная помощь. Безутешные хозяева не могут дожидаться утра, когда состояние животного не позволяет посетить ветклинику.
Комментариев пока еще нет. Вы можете стать первым!

Добавить комментарий!

Ваше Имя:
Ваш E-Mail:
Введите два слова, показанных на изображении: *
Популярные новости
Перепланировка за счет объединения туалета и ванной комнаты
Перепланировка за счет объединения туалета и ванной комнаты
Обычно вопроса о том, нужно ли объединять туалет и ванную комнату не стоит в новых домах....
Особенности и плюсы каркасных домов
Особенности и плюсы каркасных домов
Кирпич – традиционный материал для строительства загородных домов, однако в последнее время его...
Зачем нужны конвекторы в частном доме
Зачем нужны конвекторы в частном доме
Частный дом - это то, что сегодня требует вложений времени и внимания. И, тут стоит понимать, что...
Все новости