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

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

Эта процедура была первой процедурой движущегося ножа для завистливого разрезания, разработанная для трёх участников. Процедура требует четыре ножа, но делается только два разреза, так что каждый участник получает один связный кусок. Нет естественного обобщения процедуры для более чем трёх участников, которое делит торт без дополнительных разрезов. Получающееся разрезание торта не обязательно будет эффективно^[2].

Арбитр передвигает меч слева направо над тортом, гипотетически, деля его на маленькую левую часть и большую правую. Каждый игрок передвигает нож над правым куском, всегда сохраняя параллельность с мечом. Игроки должны передвигать свои ножи непрерывно, «прыжки» не допускаются^[3]. Когда кто-то из игроков воскликнет: «Режь!», меч опускается и отрезается кусок торта, при этом какой-то нож окажется посередине между двумя другими (то есть вторым, если считать от меча). Тогда торт разрезается следующим образом:

• Кусок слева от меча, который мы будем называть Левым, отдаётся игроку, воскликнувшему «Режь!». Назовём этого игрока «крикуном», других двух игроков назовём «молчунами».
• Кусок торта оказавшийся между мечом и средним ножом, который мы назовём Средним, отдаётся игроку, чей нож оказался ближе к мечу.
• Оставшийся кусок, Правый, отдаётся третьему игроку.

Каждый игрок может действовать так, что ему будет гарантировано (согласно его собственным оценкам), что никакой другой игрок не получит больше его:

• Всегда держи нож так, что он делит правую от меча часть на два куска, которые в ваших глазах равны (то есть первоначально нож делит весь торт пополам и движется направо по мере движения меча направо).
• Кричи «Режь!», когда «Левый кусок» становится равной куску который ты получишь, если промолчишь (то есть, если ваш нож крайний слева, кричи «Режь!», когда «Левый кусок»=«Среднему куску». Если ваш нож крайний справа, кричи, когда «Левый кусок»=«Правому куску». Если ваш нож находится посередине, крича «Режь!», когда все три части равны («Левый кусок»=«Средний кусок»=«Правый кусок»).

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

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

Крикун получает «Левый кусок», который равен куску, который он получил бы, промолчав, и больше, чем третий кусок, следовательно, крикун не завидует никому из молчунов.

Следуя этой стратегии, каждый участник получает больший кусок (по оценке самого участника), а потому в результате дележа будет отсутствовать зависть.

Тот же анализ показывает, что в результате дележа не будет зависти, даже в случае, когда крикунов будет двое и левый кусок будет отдан любому из них.

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

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