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

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

Процедура использует вариант процедуры Аустина для двух участников и общего дележа. Эта процедура позволяет двум участникам разделить весь торт на $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 разрезов[2].

Примечания

Brams, Taylor, 1996, с. 126–128.
BRAMS, TAYLOR, ZWICKE, 1997, с. 547–554.

Литература

Steven J. Brams, Alan D. Taylor. Fair division: from cake-cutting to dispute resolution. — Cambridge University Press, 1996. — ISBN 0-521-55644-9.
STEVEN J. BRAMS, ALAN D. TAYLOR, WILLIAM S. ZWICKE. A Moving-Knife Solution to the Four-Person Envy-Free Cake Division // Proceedings of the American Mathematical Society. — 1997. — Т. 125, вып. 2. — doi:10.1090/s0002-9939-97-03614-9.

This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.

[_041dba621f32a305-1] Brams, Taylor, 1996, с. 126–128.

[_94beea1f9e1facb5-2] BRAMS, TAYLOR, ZWICKE, 1997, с. 547–554.