Процедуры Остина с подвижным ножом

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

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

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

Основным математическим инструментом, используемым в процедуре Остина, является теорема о промежуточном значении (IVT). ^{[ 1 ]}^{[ 2 ]}^{[ 3 ]}^: 66

Два партнера и полуторты

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

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

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

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

Процедура одним ножом

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

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

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

Два партнера и общие фракции

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

Алиса делает $k-1$ параллельные отметки на торте такие, что $k$ определенные таким образом кусочки имеют стоимость ровно $1/k$ .
Если есть произведение, которое Джордж также ценит как $1/k$ , тогда мы закончили.
В противном случае должен быть кусок, который Джордж ценит меньше, чем $1/k$ и соседний фрагмент, который Джордж ценит более чем $1/k$ .
Пусть Алиса поместит два ножа на две отметки одной из этих фигур и переместит их параллельно, сохраняя расстояние между ними точно $1/k$ , пока они не встретятся с отметками на другом куске. Согласно IVT, должна быть точка, в которой Джордж согласен, что значение между ножами точно равно $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$ куски.

Два партнера могут добиться точного раздела при любом рациональном соотношении прав, используя несколько более сложную процедуру. ^{[ 3 ]}^: 71

Множество партнеров

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

Партнеры №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/6 для партнера №1, поэтому партнер №1 остается ровно с 1/3; то же самое верно и для партнера №2. Что касается партнера №3, то хотя каждый кусок может быть больше или меньше 1/6, сумма двух кусков должна составлять ровно 1/3 всего торта.

Обратите внимание, что для $n>2$ , полученное деление неточно, так как штука стоит $1/n$ только своему владельцу и не обязательно другим партнерам. По состоянию на 2015 год не существует точной процедуры деления $n>2$ партнеры; только почти точные процедуры деления известны .

См. также

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

Ссылки

^ Jump up to: ^а ^б Остин, АК (1982). «Делимся тортом». Математический вестник . 66 (437): 212–215. дои : 10.2307/3616548 . JSTOR 3616548 . S2CID 158398839 .
^ Jump up to: ^а ^б ^с Брамс, Стивен Дж.; Тейлор, Алан Д. (1996). Справедливое разделение [ От разрезания торта до разрешения споров ]. стр. 22–27. ISBN 978-0-521-55644-6 .
^ Jump up to: ^а ^б Робертсон, Джек; Уэбб, Уильям (1998). Алгоритмы разрезания торта: будьте честны, если можете . Натик, Массачусетс: АК Питерс. ISBN 978-1-56881-076-8 . LCCN 97041258 . ОЛ 2730675В .
^ Брамс, Стивен Дж.; Тейлор, Алан Д. Fair Division [ От разрезания торта к разрешению споров ]. стр. 43–44. ISBN 978-0-521-55644-6 .

Внешние ссылки

Фишер, Дэниел. «Консенсусное разделение торта на двоих в произвольных пропорциях» . Математика.SE . Проверено 23 июня 2015 г.

[austin-1] Jump up to: ^а ^б Остин, АК (1982). «Делимся тортом». Математический вестник . 66 (437): 212–215. дои : 10.2307/3616548 . JSTOR 3616548 . S2CID 158398839 .

[bramstaylor-2] Jump up to: ^а ^б ^с Брамс, Стивен Дж.; Тейлор, Алан Д. (1996). Справедливое разделение [ От разрезания торта до разрешения споров ]. стр. 22–27. ISBN 978-0-521-55644-6 .

[rw98-3] Jump up to: ^а ^б Робертсон, Джек; Уэбб, Уильям (1998). Алгоритмы разрезания торта: будьте честны, если можете . Натик, Массачусетс: АК Питерс. ISBN 978-1-56881-076-8 . LCCN 97041258 . ОЛ 2730675В .

[bramstaylor43-4] Брамс, Стивен Дж.; Тейлор, Алан Д. Fair Division [ От разрезания торта к разрешению споров ]. стр. 43–44. ISBN 978-0-521-55644-6 .

[ 1 ]

[ 2 ]

[ 3 ]

[ 4 ]