Процедура Брамса — Тейлора — Цвикера — это протокол завистливого разрезания торта на 4 участников.
Процедура использует вариант процедуры Аустина для двух участников и общего дележа. Эта процедура позволяет двум участникам разделить весь торт на кусков, каждый из которых оба участника оценивают в точности как .
Основная процедура работает следующим образом:
A. Используем процедуру Аустина с и участниками #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 разрезов.
Примечания
Литература
Категория:Протоколы справедливого дележа