Процедуры «Движущийся нож» Остина (Hjkey;rjd «:fn'rpnwvx uk'» Kvmnug)

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Как заметил Остин, два участника могут найти один кусок торта, который оба оценивают ровно в $1/k$ для любого целого $k\geqslant 2$ ^[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$ ^[2]:

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

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

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

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

Участники № 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, 1982, с. 212.
↑ ¹ ² ³ Brams, Taylor, 1996, с. 22–27.
↑ Robertson, Webb, 1998, с. 66.
↑ Robertson, Webb, 1998, с. 71.
↑ Brams, Taylor, 1996, с. 43–44.

Литература

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.

[_8b6ae5ed06a1ccc2-1] ¹ ² Austin, 1982, с. 212.

[_3ecde3881d5b36a4-2] ¹ ² ³ Brams, Taylor, 1996, с. 22–27.

[_0c712c4de16b73b6-3] Robertson, Webb, 1998, с. 66.

[_0c712d4de16b7502-4] Robertson, Webb, 1998, с. 71.

[_10adea5aa2a93378-5] Brams, Taylor, 1996, с. 43–44.

[1]

[2]

[3]

[4]

[5]