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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Два участника могут получить точный делёж с любым рациональным отношением Шаблон:Не переведено 5 путём слегка более сложной процедурыШаблон:Sfn.

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

При комбинировании процедуры ${\mathrm{C}\mathrm{u}\mathrm{t}}_2$ с протоколом Финка можно разделить торт между $n$ участниками, так что каждый участник получает кусок, который он оценивает ровно в $1/n$Шаблон:SfnШаблон:Sfn:

• Участники № 1 и № 2 используют ${\mathrm{C}\mathrm{u}\mathrm{t}}_2(1/2)$, чтобы дать каждому из них ровно 1/2, по его мнению.
• Участник № 3 использует ${\mathrm{C}\mathrm{u}\mathrm{t}}_2(1/3)$ с участником № 1, чтобы получить в точности 1/3 от его доли, а затем ${\mathrm{C}\mathrm{u}\mathrm{t}}_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$ участников, известны только процедуры почти точного дележа.

См. также

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

Литература

• Шаблон:Статья
• Шаблон:Книга
• Шаблон:Книга
  • Перевод Шаблон:Книга

Ссылки

• Шаблон:Cite web