Interested Article - Процедура Брамса — Тейлора — Цвикера

Процедура Брамса — Тейлора — Цвикера — это протокол завистливого разрезания торта на 4 участников .

Процедура использует вариант процедуры Аустина для двух участников и общего дележа . Эта процедура позволяет двум участникам разделить весь торт на $k$ кусков, каждый из которых оценивается в точности в $1/k$ для обоих участников.

Основная процедура работает следующим образом:

A. Используем процедуру Аустина с $k=4$ и участниками #1 и #2. Мы получим 4 куска, которые оба первых участника оценивают в точности в 1/4.

B. Участник #3 усекает один кусок. Теперь участники выбирают куски в обратном порядке (#4, #3, #2, #1). Один из участников — #4 или #3 — должен взять отрезанную долю от усечённого куска. Благодаря этому делёж проходит без зависти для всего куска без усечения (Об этом подробно в процедуре Селфриджа — Конвея ).

C. Теперь делим отсечённый кусок. Без потери общности предположим, что отсечённый кусок достался участнику #3. Мы используем процедуру Аустина для деления этого отсечённого куска участниками #4 и #1 с целью получить 4 куска, каждый из который оба оценивают в точности в 1/4. Поскольку участники #1 и #2 имеют безоговорочное преимущество, мы можем позволить участнику #3 первым выбрать часть отсечённого куска, затем #2, затем #4 и #1.

Эффективность

Время работы процедуры, с технической точки зрения, бесконечно, поскольку процедура Аустина использует непрерывное движение ножей, и эту процедуру нельзя сделать дискретной.

Однако число разрезов ограничено. Процедура Аустина требует 2 разреза для деления торта между двумя участниками с точным значением 1/4. Каждый из этих кусков должен быть разрезан двумя дополнительными разрезами для образования 4 кусков с точным значением 1/4. Таким образом, общее число необходимых разрезаний для шага A равно 6. Одно разрезание осуществляется на шаге B и ещё 6 разрезаний на шаге C, что в общей сложности даёт 13 разрезаний.

Улучшенный вариант процедуры Брамса — Тейлора — Цвикера использует только 11 разрезов .

Примечания

, с. 126–128.
, с. 547–554.

Литература

Steven J. Brams, Alan D. Taylor. . — Cambridge University Press, 1996. — ISBN 0-521-55644-9 .
STEVEN J. BRAMS, ALAN D. TAYLOR, WILLIAM S. ZWICKE. // Proceedings of the American Mathematical Society. — 1997. — Т. 125 , вып. 2 . — doi : .