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

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

История

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

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

Описание

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

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

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

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

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

Анализ

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

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

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

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

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

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

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

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

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

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

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

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

Улучшения

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

Ссылки

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

[steinhaus48-1] Штайнхаус, Хьюго (1948). «Проблема справедливого дележа». Эконометрика . 16 (1): 101–4. JSTOR 1914289 .

[ds61-2] Дубинс, Лестер Эли ; Спаниер, Эдвин Генри (1961). «Как красиво разрезать торт». Американский математический ежемесячник . 68 (1): 1–17. дои : 10.2307/2311357 . JSTOR 2311357 .

[bramstaylor130-3] Брамс, Стивен Дж.; Тейлор, Алан Д. (1996). Справедливое разделение: от разрезания торта до разрешения споров . Издательство Кембриджского университета. стр. 130–131. ISBN 0-521-55644-9 .

[1]

[2]

[3]