Последний уменьшитель - Last diminisher

В последний уменьшитель процедура - это процедура для ярмарка разрезания торта. Он включает в себя некий разнородный и делимый ресурс, такой как праздничный торт, и п партнеры с разными предпочтениями по разным частям торта. Это позволяет п люди для достижения пропорциональное деление, то есть разделить торт между ними так, чтобы каждый получил кусок стоимостью не менее 1 /п от общей стоимости согласно его собственной субъективной оценке. Например, если Алиса оценивает весь торт как 100 долларов и есть 5 партнеров, то Алиса может получить кусок, который она оценивает как минимум как 20 долларов, независимо от того, что думают или делают другие партнеры.

История

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

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

Описание

Это описание протокола деления словами автора:

"Партнеры, расположенные в диапазоне A, B, C, ... N, A, отрезают от торта произвольную часть. B теперь имеет право, но не обязан, уменьшать отрезанный кусок. Что бы он ни делал, C имеет право (без обязательства) уменьшать уже уменьшенный (или не уменьшенный) кусок, и так далее до N. Правило обязывает «последнего уменьшающего» взять в качестве своей части кусок, к которому он прикоснулся последним. утилизировано, оставшиеся п-1 человек начинают ту же игру с остатком торта. После того, как количество участников сократилось до двух, они применяют классическое правило деления остатка вдвое ».

У каждого партнера есть метод, который гарантирует, что он получит срез со значением не менее 1 /п. Метод: всегда обрезать текущий фрагмент так, чтобы остаток имел значение 1 /п для тебя. Есть два варианта: либо вы получаете отрезанный кусок, либо другой человек получает кусок меньшего размера, значение которого для вас меньше 1 /п. В последнем случае есть п−1 остается партнер, а стоимость оставшегося торта больше (п−1)/п. Следовательно, по индукции можно доказать, что полученное значение не меньше 1 /п.

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

Алгоритм упрощается в вырожденном случае, когда все партнеры имеют одинаковую функцию предпочтения, потому что партнер, который оптимально первым разрезает срез, также будет его последним уменьшающим. Эквивалентно,^{[нужна цитата ]} каждый партнер 1, 2, ..., п−1, в свою очередь, отрезает кусок от оставшегося торта. Затем в обратном порядке каждый партнер п, п−1, ..., 1, в свою очередь, выбирает срез, который еще не востребован. Первый партнер, который разрезал кусочек, отличный от 1 /п завидовали бы другому партнеру, у которого в итоге было больше, чем у них.

Анализ

Протокол последнего уменьшения является дискретным и может использоваться по очереди. В худшем случае п × (п - 1) / 2 = О(п²) действия необходимы: одно действие на игрока за ход.

Однако большинство из них О(п²) действия не являются фактическими разрезами, т.е. Алиса может отметить желаемый фрагмент на бумаге и попросить других игроков уменьшить их на той же бумаге и т. д .; только «последний уменьшитель» должен разрезать торт. Итак, только п−1 разреза.

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

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

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

Версия этого протокола с непрерывным временем может быть выполнена с помощью Dubins-Spanier Процедура с подвижным ножом.^[2] Это был первый пример непрерывной процедуры справедливого разделения. Нож продеваем по пирогу с левого края на правый. Любой игрок может сказать стоп, когда думает ${\displaystyle 1/n}$ торта находится слева от ножа, торт разрезается, и игрок, который говорил, получает этот кусок. Повторите то же самое с оставшимся тортом и игроками, последний игрок получает остаток торта. Подобно последней процедуре уменьшения размера, его можно использовать для разрезания торта на смежные части для каждого игрока.

Примерная версия без зависти

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

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

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

Время выполнения не более ${\displaystyle n^{2}/\epsilon }$, так как есть не более ${\displaystyle n/\epsilon }$ шагов, и на каждом шаге мы запрашиваем каждый из ${\displaystyle n}$ партнеры.

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

Улучшения

Последняя процедура уменьшения размера позже была улучшена во многих отношениях. Подробнее см. пропорциональное деление.

Рекомендации

1. Штейнхаус, Гюго (1948). «Проблема справедливого разделения». Econometrica. 16 (1): 101–4. JSTOR  1914289.
2. Дубинс, Лестер Эли; Spanier, Эдвин Генри (1961). «Как правильно разрезать торт». Американский математический ежемесячник. 68: 1. Дои:10.2307/2311357. JSTOR  2311357.
3. Брамс, Стивен Дж .; Тейлор, Алан Д. (1996). Честное разделение: от нарезки торта до разрешения споров. Издательство Кембриджского университета. С. 130–131. ISBN  0-521-55644-9.