Введение

Процедуры справедливого раздела торта Процедуры движущегося ножа Остина - это процедуры справедливого раздела торта. Каждому из n партнеров они выделяют кусочек торта, который этот партнер оценивает как точный кусочек торта. Это отличается от пропорционального деления, когда каждый партнер получает по меньшей мере часть торта, но может дать больше некоторым партнерам. Когда , деление, полученное процедурой Остина, является точным делением, и оно также свободно от зависти. Кроме того, можно разделить пирог на любое количество к кусков, которые оба партнера оценивают как точно 1/k. Таким образом, можно разделить торт между партнерами в любой доле (например, 1/3 Алисе и 2/3 Джорджу). Когда , разделение не является ни точным, ни свободным от зависти, поскольку каждый партнер оценивает только свою собственную фигуру как , но может оценивать другие фигуры по-разному. Основным математическим инструментом, используемым в процедуре Остина, является теорема промежуточных значений (IVT).

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

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

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

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

Одна ножная процедура

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

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

Как отмечает Остин, два партнера могут найти один кусок торта, который они оба оценивают как точно , для любого целого числа, которое используют партнеры No 1 и No 2, чтобы дать каждому из них кусок, который стоит точно 1/2 для них. Партнер No3 использует с партнером No1 чтобы получить ровно 1/3 его доли, а затем с партнером No2 чтобы получить ровно 1/3 ее доли. Первая фигура стоит ровно 1/6 для партнера No1 и поэтому партнер No1 остается с ровно 1/3; то же самое верно для партнера No2. Что касается партнера No3, то каждый кусок может быть больше или меньше 1/6, но сумма двух кусков должна быть ровно 1/3 от всего торта. Обратите внимание, что для , полученное деление не является точным, поскольку часть стоит только для ее владельца, а не обязательно для других партнеров. По состоянию на 2015 год не существует точной процедуры деления для партнеров; известны только почти точные процедуры деления.