Процедура «Движущийся нож» Робертсона — Уэбба

Процедура «Движущийся нож» Робертсона — Уэбба — это процедура завистливого разрезания двухмерного торта на трёх участников[1]. Процедура делает всего два разреза, так что каждый участник получает один цельный кусок.

Главным преимуществом процедуры над более ранней процедурой «Движущийся нож» Стромквиста и более поздней процедурой «Движущийся нож» Барбанеля — Брамса является использование всего одного движущегося ножа. Для этого используется двухмерность торта.

Процедура

Первоначально каждый участник делает вертикальный разрез, так что торт слева участник оценивает в точности в 1/3. Выбирается самый левый разрез. Предположим, что этот разрез сделала Алиса. Тогда Алиса получает левый кусок, который она оценивает ровно в 1/3. Остаток следует разделить между оставшимися участниками (Бобом и Карлом).

Заметим, что доля Алисы оценивается не более чем в 1/3, а остаток не менее чем в 2/3 как Бобом, так и Карлом. Таким образом, если Боб и Карл получат по меньшей мере половину остатка, у них нет повода для зависти. Проблема заключается в Алисе, как сделать, чтобы она не завидовала.

Решение основано на следующем наблюдении: для любого Алиса может расположить нож под таким углом и разрезать оставшийся кусок на две равные в её глазах половинки. Это означает, что Алиса может поворачивать нож над остатком торта так, что по обе стороны от ножа в её глазах куски будут равными.

Когда нож под углом 0, Боб (слабо) предпочитает либо кусок сверху от ножа, либо кусок снизу от ножа (слабо означает, что ему куски могут казаться равными и он предпочитает одинаково оба куска). Когда нож находится под углом , куски меняются местами. Следовательно, по теореме о промежуточном значении, должен существовать угол, при котором Боб думает, что куски по обе стороны от ножа одинаковы. Когда нож примет такой угол, Боб восклицает «стоп!». Торт разрезается и Карл выбирает кусок, а Боб забирает оставшийся кусок.

Анализ

Алиса не завидует, поскольку для неё все три куска оцениваются ровно в 1/3.

Боб и Карл не завидуют Алисе, поскольку её кусок оценивают максимум в 1/3 а свой кусок — не менее чем в (1/2)*(2/3) = 1/3.

Боб не завидует Карлу, поскольку их куски (в его глазах) одинаковы. Карл не завидует Бобу, поскольку он выбрал лучший из кусков.

Делёж «плохого» торта

Процедура «движущийся нож» может быть приспособлена для дележа обязанностей, то есть торта с отрицательной общей оценкой[2]. В этом случае на начальном этапе выбирается не левый кусок, а правый.

См. также

Примечания
  1. Robertson, Webb, 1998, с. 77–78.
  2. Robertson, Webb, 1998, с. exercise 5.10.

Литература
  • Jack Robertson, William Webb. Cake-Cutting Algorithms: Be Fair If You Can. — Natick, Massachusetts: A. K. Peters, 1998. — ISBN 978-1-56881-076-8.
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.