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

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

ИсторияПравить

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

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

Брамс и Тейлор держат совместный патент США с 1999, связанный с ПБТ^[5].

ОписаниеПравить

ПБТ делит торт кусок-за-куском. Типичное промежуточное состояние ПБТ следующее:

Кусок торта, скажем, $\text{[math]}$ $\text{[math]}$ $X$ , делится среди всех участников, не создавая зависти.
Остаток торта, скажем, $\text{[math]}$ $\text{[math]}$ $Y$ , остаётся неразделённым, однако
Один участник, скажем, Алиса, имеет Неоспоримое Преимущество (англ. Irrevocable Advantage, IA) над другим партнёром, скажем, Бобом, с учётом $\text{[math]}$ $\text{[math]}$ $Y$ . Это означает, что независимо от способа, каким будет поделён $\text{[math]}$ $\text{[math]}$ $Y$ , даже если мы отдадим весь кусок $\text{[math]}$ $\text{[math]}$ $Y$ Бобу, Алиса не будет ему завидовать.

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

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

После того, как эта операция проведена, весь торт, за исключением куска $\text{[math]}$ $\text{[math]}$ $Y$ , поделён без возникновения зависти. Кроме того, Алиса имеет неоспоримое преимущество перед тем, кто взял кусок $\text{[math]}$ $\text{[math]}$ $(A\setminus Y)$ . Поскольку Алиса берёт либо $\text{[math]}$ $\text{[math]}$ $B$ , либо $\text{[math]}$ $\text{[math]}$ $C$ , а они оба равны $\text{[math]}$ $\text{[math]}$ $A$ , по её мнению, то кто бы ни взял $\text{[math]}$ $\text{[math]}$ $(A\setminus Y)$ , он может взять и $\text{[math]}$ $\text{[math]}$ $Y$ , и это не будет поводом зависти у Алисы.

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

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

См. такжеПравить

Процедура Брамса — Тейлора — Цвикера – процедура движущегося ножа для 4 партнёров, в которой делается конечное число разрезаний.
Завистливое разрезание торта – старые и новые процедуры для той же задачи.

ПримечанияПравить

↑ Dividing the Spoils (неопр.). Discover Magazine (1 марта 1995). Дата обращения: 2 мая 2015. Архивировано из оригинала 10 марта 2012 года.
↑ More Equal than Others: Weighted Voting Архивная копия от 5 декабря 2019 на Wayback Machine Sol Garfunkel. For All Practical Purposes. COMAP. 1988
↑ Brams, Taylor, 1995, с. 9.
↑ Brams, Taylor, 1996, с. 138–143.
↑ Steven J. Brams & Alan D. Taylor, "Computer-based method for the fair division of ownership of goods", US patent 5983205, issued 1999-11-09

ЛитератураПравить

Brams S. J., Taylor A. D. An Envy-Free Cake Division Protocol // The American Mathematical Monthly. — 1995. — Т. 102. — doi:10.2307/2974850. — JSTOR 2974850.
Steven J. Brams, Alan D. Taylor. Fair division: from cake-cutting to dispute resolution. — Cambridge University Press, 1996. — ISBN 0-521-55644-9.

[DSp-1] Dividing the Spoils (неопр.). Discover Magazine (1 марта 1995). Дата обращения: 2 мая 2015. Архивировано из оригинала 10 марта 2012 года.

[SG-2] More Equal than Others: Weighted Voting Архивная копия от 5 декабря 2019 на Wayback Machine Sol Garfunkel. For All Practical Purposes. COMAP. 1988

[_66f638e8ef1cba40-3] Brams, Taylor, 1995, с. 9.

[_50e99fa4aafd2499-4] Brams, Taylor, 1996, с. 138–143.

[USP-5] Steven J. Brams & Alan D. Taylor, "Computer-based method for the fair division of ownership of goods", US patent 5983205, issued 1999-11-09

[1]

[2]

[3]

[4]

[5]