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

Процедуры «Движущийся нож» Остина — это процедуры беспристрастного дележа торта. Процедуры распределяют каждому из n участников кусок торта, который этот участник оценивает ровно в ${\displaystyle 1/n}$ всего торта. Это контрастирует с процедурами пропорционального дележа, которые дают каждому участнику по меньшей мере ${\displaystyle 1/n}$ полного торта, но могут дать каждому участнику больше.

Если ${\displaystyle n=2}$, разрезание, полученное процедурой Остина, является точным дележом и в нём отсутствует зависть. Более того, можно разрезать торт на любое число k кусков, которые каждый из партнёров оценивает ровно в 1/k. Следовательно, можно разделить торт между участниками в любой пропорции (например, дать 1/3 Алисе и 2/3 Джорджу).

Если ${\displaystyle n>2}$, делёж будет ни точным, ни свободным от зависти, поскольку только оценивает свой собственный кусок в ${\displaystyle 1/n}$, но оценка других кусков может отличаться от этого значения.

Основным математическим средством, используемым процедурой Остина, является теорема о промежуточном значении^[1][2][3].

Базовые процедуры вовлекают ${\displaystyle n=2}$ участников, которые делят торт, так что оба участника получают ровно половину.

Для простоты описания назовём двух игроков именами Алиса и Джордж и предположим, что торт прямоуголен.

• Алиса помещает один нож слева от торта, а второй параллельно ему справа, где собирается разрезать торт на две части.
• Алиса передвигает оба ножа направо так, что часть между ножами всегда остаётся половиной торта (по её оценке, хотя физическое расстояние между ножами может меняться).
• Джордж говорит «стоп!», когда он считает, что между ножами находится половина торта. Как мы можем быть уверены, что Джордж произнесёт слово «стоп!» в некоторый момент? Дело в том, что если Алиса достигнет правым ножом края, позиция левого ножа должна быть в той же точке, с которой стартовал правый нож. Теорема о промежуточном значении утверждает, что Джордж должен быть удовлетворён делением торта пополам в какой-то точке.
• Бросание монеты определяет два варианта — либо Джордж получает кусок между ножами, а Алиса получает два крайних куска, либо наоборот. Если участники честны, они согласятся, что часть между ножами имеет значение в точности 1/2, так что разрезание будет точным.

Для достижения того же эффекта можно использовать один нож.

• Алиса вращает нож над тортом до 180°, сохраняя равными половинки с обеих сторон от ножа.
• Джордж говорит «стоп!», когда он согласен.

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

Как заметил Остин, два участника могут найти один кусок торта, который оба оценивают ровно в ${\displaystyle 1/k}$ для любого целого ${\displaystyle k\geqslant 2}$^[2]. Назовём вышеописанную процедуру как ${\displaystyle \mathrm {Cut} _{2}(1/k)}$:

• Алиса делает ${\displaystyle k-1}$ параллельных меток на торте, так что ${\displaystyle k}$ кусков имеют значение ровно ${\displaystyle 1/k}$.
• Если есть кусок, который Джордж считает тоже равным ${\displaystyle 1/k}$, мы завершили выделение такого куска.
• В противном случае должен быть кусок, который Джордж оценивает меньше чем в ${\displaystyle 1/k}$ и смежный к нему кусок, который Джордж оценивает больше чем в ${\displaystyle 1/k}$.
• Позволим Алисе поместить два ножа на двух метках одного из этих кусков и пусть она передвигает ножи параллельно, сохраняя значение между ножами ровно в ${\displaystyle 1/k}$, пока ножи не встанут на метки второго куска. По теореме о промежуточном значении должна быть точка, в которой Джордж должен согласиться, что значение между ножами в точности равно ${\displaystyle 1/k}$.

Рекурсивно применяя ${\displaystyle \mathrm {Cut} _{2}}$ два участника могут разделить весь торт на ${\displaystyle k}$ частей, каждую из которых оба участника оценивают в точности в ${\displaystyle 1/k}$^[2]:

• Используем процедуру ${\displaystyle \mathrm {Cut} _{2}(1/k)}$ для отрезания куска, который оба игрока оценивают ровно в ${\displaystyle 1/k}$.
• Теперь остаток торта оба игрока оценивают ровно в ${\displaystyle (k-1)/k}$. Используем ${\displaystyle \mathrm {Cut} _{2}(1/(k-1))}$, чтобы отрезать кусок, который оба игрока оценивают в точности в ${\displaystyle 1/k}$.
• Продолжаем, пока не получим все ${\displaystyle k}$ кусков.

Два участника могут получить точный делёж с любым рациональным отношением причитающихся долей^[англ.] путём слегка более сложной процедуры^[4].

При комбинировании процедуры ${\displaystyle \mathrm {Cut} _{2}}$ с протоколом Финка можно разделить торт между ${\displaystyle n}$ участниками, так что каждый участник получает кусок, который он оценивает ровно в ${\displaystyle 1/n}$^[1][5]:

• Участники № 1 и № 2 используют ${\displaystyle \mathrm {Cut} _{2}(1/2)}$, чтобы дать каждому из них ровно 1/2, по его мнению.
• Участник № 3 использует ${\displaystyle \mathrm {Cut} _{2}(1/3)}$ с участником № 1, чтобы получить в точности 1/3 от его доли, а затем ${\displaystyle \mathrm {Cut} _{2}(1/3)}$ с участником № 2, чтобы получить в точности 1/3 от его доли. Выделенная доля от куска участника № 1 оценивается обоими участниками в точности 1/6, так что у участника № 1 остаётся в точности 1/3. То же самое верно для участника № 2. Для участника № 3, хотя куски он может оценивать больше или меньше 1/6, сумма двух кусков должна быть в точности 1/3 всего торта.

Заметим, что для ${\displaystyle n>2}$ получаемое разрезание не является точным, поскольку кусок оценивается в ${\displaystyle 1/n}$ только владельцем куска, но не обязательно во столько же другими участниками. На 2015 год не было известно процедуры точного дележа для ${\displaystyle n>2}$ участников, известны только процедуры почти точного дележа.

• Процедура Остина используется процедурой Брамса — Тейлора — Цвикера.
• Другие процедуры и результаты беспристрастного дележа и точного дележа.

• Austin A. K. Sharing a Cake // The Mathematical Gazette. — 1982. — Т. 66, вып. 437. — doi:10.2307/3616548. — JSTOR 3616548.
• Jack Robertson, William Webb. Cake-Cutting Algorithms: Be Fair If You Can. — Natick, Massachusetts: A. K. Peters, 1998. — ISBN 978-1-56881-076-8.
• Steven J. Brams, Alan D. Taylor. Fair Division. — 1996. — ISBN 978-0-521-55644-6.
  • Перевод Стивен Дж. Брамс, Алан Д. Тейлор. Делим по справедливости или гарантия выигрыша каждому. — Москва: СИНТЕГ, 2002. — (Серия «Экономика и бизнес»). — ISBN 5-89638-058-5.

• Fischer, Daniel. Consensus division of a cake to two people in arbitrary ratios  (неопр.). Math.SE. Дата обращения: 23 июня 2015.