Процедура «Движущийся нож» Левмора — Кук

Процедура «Движущийся нож» Левмора — Кук — это процедура завистливого разрезания торта на трёх участников. Она названа именами Сола Левмора и Элизабет Кук, предложивших её в 1981 году^[1]. Процедура предполагает, что торт двумерен, требует два ножа и четыре разреза, так что некоторые участники могут получить несвязные куски.

ПроцедураПравить

Назовём участников именами Алиса, Боб и Карл.

Сначала Алиса разрезает торт на три равные (по её мнению) куска. Боб и Карл указывают на предпочтительные (для них) куски.

Простой случай: Боб и Карл указывают на различные куски. Каждый получает понравившийся кусок, а Алиса получает оставшийся.

Трудный случай: Боб и Карл указывают на тот же самый кусок. Скажем, пусть это будет кусок X, а два других куска — Y и Z. Теперь Алиса берёт два ножа и передвигает их одновременно над куском X:

Нож #1 движется горизонтально с левого края куска X к правому краю. Он делит кусок X на две части — левую часть XL и правую часть XR.
Нож #2 движется вертикально так, что слева от ножа #1 кусок XL делится в её глазах на две одинаковые части — левую-верхнюю XLT и левую-нижнюю XLB.

Первоначально кусок XR=X, так что для Боба и Карла он больше, чем Y и Z. Более того, первоначально XLT и XLB пусты, так что XR больше, чем две пары — Y+XLT и Z+XLB.

По мере движения ножа #1 направо XR уменьшается, в то время как XLT и XLB растут. В некоторой точке Боб или Карл считает, что XR равен одному куску из двух пар. Первый, кто считает, что наблюдается равенство, восклицает «стоп!» и получает выбранную им пару. Алиса получает другую пару, а промолчавший получает XR.

АнализПравить

Мы проанализируем случай, когда Боб воскликнул «стоп!» и выбрал пару Y + XLT. Алиса получает Z + XLB, а Карл получает XR. В дележе будет отсутствовать зависть, поскольку

Для Алисы Z > X > XR, так что она не завидует Карлу. Более того, Z=Y и XLB=XLT, так что Алиса не завидует Бобу.
Для Боба Y + XLT = XR > Z + XLB, так что он тоже не завидует.
Для Карла кусок XR больше обоих пар (он же не воскликнул стоп!), так что он тоже не завидует.

Другие случаи аналогичны.

ВариантыПравить

Можно позволить воскликнувшему выбрать одну из пар Y+XLT, Y+XLB, Z+XLT или Z+XLB. Эта модификация даёт преимущество промолчавшему^[2].

Левмор и Кук предложили обобщение их процедуры для четырёх участников, но позднее было показано, что их обобщение не во всех случаях работает^[3].

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

Процедура «Движущийся нож» Стромквиста использует четыре ножа, но только два из них могут резать, так что каждый из участников получает связный кусок.

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

Saul X. Levmore, Elizabeth Early Cook. Super strategies for puzzles and games. — Garden City, NY: Doubleday, 1981.
Steven J. Brams, Alan D. Taylor. Fair division: from cake-cutting to dispute resolution. — Cambridge University Press, 1996. — ISBN 0-521-55644-9.

Ron Cytron. Cake Cutting Algorithms - Lecture 8. — 2012.

[_180589fc35b6cd8a-1] Levmore, Cook, 1981.

[_cf0a3bd50e00d62d-2] Cytron, 2012.

[_3a0a6068340d2075-3] Brams, Taylor, 1996, с. 122–124.

[1]

[2]

[3]