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

Материал из Википедии — свободной энциклопедии
Перейти к навигации Перейти к поиску

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

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

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

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

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

[править | править код]

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

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

[править | править код]

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

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

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

[править | править код]

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

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

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

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

[править | править код]

Как заметил Остин, два участника могут найти один кусок торта, который оба оценивают ровно в для любого целого [2]. Назовём вышеописанную процедуру как :

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

Рекурсивно применяя два участника могут разделить весь торт на частей, каждую из которых оба участника оценивают в точности в [2]:

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

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

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

[править | править код]

При комбинировании процедуры с протоколом Финка можно разделить торт между участниками, так что каждый участник получает кусок, который он оценивает ровно в [1][5]:

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

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

Примечания

[править | править код]
  1. 1 2 Austin, 1982, с. 212.
  2. 1 2 3 Brams, Taylor, 1996, с. 22–27.
  3. Robertson, Webb, 1998, с. 66.
  4. Robertson, Webb, 1998, с. 71.
  5. 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.