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

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

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

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

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

Два участника и половинки торта

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

Процедура двух ножей

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

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

Процедура одного ножа

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

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

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

Два участника и части общего вида

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

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

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

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

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

Много участников

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

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

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

См. также

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

Литература

• Austin A. K. Sharing a Cake // The Mathematical Gazette. — 1982. — Т. 66, вып. 437. — doi:10.2307/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.