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

Перейти к навигацииПерейти к поиску

Процедура «Движущийся нож» Левмора — Кук — это процедура завистливого разрезания торта на трёх участников. Она названа именами Сола Левмора и Элизабет Кук, предложивших её в 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].

См. также

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

Примечания

  1. ↑ Levmore, Cook, 1981.
  2. ↑ Cytron, 2012.
  3. ↑ Brams, Taylor, 1996, с. 122–124.

Литература

  • 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.