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


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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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


  • Квантили распределения Стьюдента
  • Эффективное разрезание торта
  • Процедура «Движущийся нож» Робертсона — Уэбба
  • Дважды стохастическая матрица
  • Процедура «одиночный делящий»

  •  

    • Яндекс.Метрика
    • Индекс цитирования