Процедура Брамса-Тейлора

Процедура Брамса-Тейлора (BTP) – это процедура разрезания торта без зависти . Он объяснил первую конечную процедуру, позволяющую без зависти разделить торт между любым положительным целым числом игроков. ^[1]

История

В 1988 году, еще до открытия BTP, Сол Гарфанкел утверждал, что проблема, решаемая теоремой, а именно разрезание торта без зависти n людьми, была одной из наиболее важных задач математики 20-го века. ^[2]

BTP был обнаружен Стивеном Брэмсом и Аланом Д. Тейлором . Впервые оно было опубликовано в январском номере журнала American Mathematical Monthly за 1995 год . ^[3] и позже в 1996 г. в книге авторов. ^[4]

Брэмс и Тейлор владеют совместным патентом США от 1999 года, касающимся BTP. ^[5]

Описание

BTP делит торт по частям. Типичное промежуточное состояние БТП выглядит следующим образом:

Часть торта, скажем $X$ , делится без зависти между всеми партнерами.
Остальная часть торта, скажем $Y$ , остается неделимым, но -
Один партнер, скажем, Алиса, имеет безотзывное преимущество (IA) перед другим партнером, скажем, Бобом, в отношении $Y$ . Это означает, что независимо от того, как $Y$ делится, даже если мы дадим $Y$ полностью принадлежит Бобу, Алиса все еще не завидует Бобу.

В качестве примера того, как можно сгенерировать IA, рассмотрим первый этап дискретной процедуры Селфриджа-Конвея :

Алиса делит торт на 3 части, которые считает равными; давайте назовем части $A,B,C$ .
Боб обрезает тот кусок, который считает самым большим (скажем, $A$ ), чтобы сделать его равным второму по величине; давайте назовем обрезки $Y$ и обрезанный кусок $A\setminus Y$ .
Чарли выбирает кусок из $(A\setminus Y),B,C$ ; тогда Боб выбирает (он должен взять $(A\setminus Y)$ если он доступен); и, наконец, Алиса.

После завершения этого этапа весь торт, кроме $Y$ делится без зависти. Кроме того, у Алисы теперь есть IA на того, кто взял $(A\setminus Y)$ . Почему? потому что Алиса взяла либо $B$ или $C$ , и оба они равны $A$ по ее мнению. Итак, по мнению Алисы, кто бы ни взял $(A\setminus Y)$ также может иметь $Y$ – это не вызовет у нее зависти.

Если мы хотим убедиться, что Алиса получит ИА по конкретному игроку (например, Бобу), тогда потребуется гораздо более сложная процедура. Он последовательно делит торт на все меньшие и меньшие части, всегда давая Алисе кусок, который она ценит больше, чем кусок Боба, так что IA сохраняется. Это может занять неограниченное время – в зависимости от точных оценок Алисы и Боба.

Используя процедуру IA, основная процедура BTP создает IA для всех заказанных пар партнеров. Например, при наличии 4 партнеров получается 12 упорядоченных пар партнеров. Для каждой такой пары (X,Y) мы запускаем подпроцедуру, которая гарантирует, что партнер X имеет IA над партнером Y. После того, как каждый партнер имеет IA над каждым другим партнером, мы можем просто передать остаток произвольному партнеру и Результатом является дележ всего торта без зависти.

См. также

Процедура Брамса-Тейлора-Цвикера - процедура движущегося ножа для 4 партнеров, использующая конечное число разрезов.
Разрезание торта без зависти – старые и новые процедуры для решения одной и той же проблемы.
Процедура скорректированного победителя - процедура, разработанная Брэмсом и Тейлором для решения аналогичной, но отличной проблемы разделения товаров между двумя агентами.

Ссылки

^ «Деление добычи» . Откройте для себя журнал. 01.03.1995. Архивировано из оригинала 10 марта 2012 г. Проверено 2 мая 2015 г.
^ Более равные, чем другие: взвешенное голосование. Архивировано 5 декабря 2019 г. в Wayback Machine Сола Гарфанкеля . Для всех практических целей. КОМАП. 1988 год
^ Брамс, С.Дж.; Тейлор, AD (1995). «Протокол разделения тортов без зависти». Американский математический ежемесячник . 102 (1): 9–18. дои : 10.2307/2974850 . JSTOR 2974850 .
^ Брамс, Стивен Дж.; Тейлор, Алан Д. (1996). Справедливое разделение: от разрезания торта до разрешения споров . Издательство Кембриджского университета. стр. 138–143. ISBN 0-521-55644-9 .
^ Патент США 5983205 , Стивен Дж. Брамс и Алан Д. Тейлор, «Компьютерный метод справедливого разделения собственности на товары», выдан 9 ноября 1999 г., передан Нью-Йоркскому университету.

[1] «Деление добычи» . Откройте для себя журнал. 01.03.1995. Архивировано из оригинала 10 марта 2012 г. Проверено 2 мая 2015 г.

[2] Более равные, чем другие: взвешенное голосование. Архивировано 5 декабря 2019 г. в Wayback Machine Сола Гарфанкеля . Для всех практических целей. КОМАП. 1988 год

[3] Брамс, С.Дж.; Тейлор, AD (1995). «Протокол разделения тортов без зависти». Американский математический ежемесячник . 102 (1): 9–18. дои : 10.2307/2974850 . JSTOR 2974850 .

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

[patent5983205-5] Патент США 5983205 , Стивен Дж. Брамс и Алан Д. Тейлор, «Компьютерный метод справедливого разделения собственности на товары», выдан 9 ноября 1999 г., передан Нью-Йоркскому университету.

[1]

[2]

[3]

[4]

[5]