Задача справедливого разрезания пирога

Задача справедливого разрезания пирога — это вариант задачи справедливого дележа торта, в которой предмет, требующий дележа, имеет форму круга.

В качестве примера рассмотрим торт на день рождения в виде круга. Торт следует разделить между несколькими детьми таким образом, чтобы ни один из них не завидовал другому (как в стандартной задаче деления торта). Дополнительным условием является то, что разрезы должны быть радиальными, чтобы каждый ребёнок получил сектор круга. Термин «торт» является лишь метафорой процедуры для разрезания торта, которую можно использовать для разделения различного рода ресурсов. К примеру: земельная собственность, места под рекламу или время вещания.

Задачу разрезания торта предложил Гуго Штейнгауз после второй мировой войны. С тех пор она оставалась предметом пристального изучения в математике, информатике, экономике и политической науке.

Модель деления пирога может быть применима для деления береговой линии острова на непрерывные участки. Другим возможным вариантом применения является деление периодического времени — деление дневного цикла на «дежурные» периоды.

Модель

Пирог обычно моделируется как одномерный интервал [0,2π] (или [0,1]), в котором две конечные точки отождествлены.

Эта модель предложена в 1985 году и, позднее, в 1993 году.

Любая процедура справедливого дележа торта может быть применена к разрезанию пирога при игнорировании того факта, что две конечные точки можно отождествить. Например, если в результате процедуры разрезания торта Алиса получает [0,1/3], а Джордж получает [1/3,1], то мы дадим Алисе круговой сектор в 120 градусов, тогда как Джорджу достанется оставшийся сектор в 240 градусов.

Разрезание пирога становится более интересным, когда мы рассматриваем вопросы эффективности, поскольку при дележе пирога возможно больше разрезаний.

Два партнёра

Делёж без зависти

Делёж называется дележом с отсутствием зависти (ОЗ, англ. envy-free, EF), если каждый партнёр думает, что его кусок по меньшей мере такой же цены, как и все остальные.

Делёж пирога с ОЗ может быть произведён с помощью процедуры дели-и-выбирай — один партнёр режет пирог на два сектора, которые он считает равными, а другой партнёр выбирает сектор, который он считает лучшим. Но для пирога может существовать делёж лучше.

Делёж без зависти и эффективный по Парето

Делёж называется эффективным по Парето (ЭП, англ. Pareto efficient, PE), если ни одно другое деление пирога не является лучшим для одного партнёра, и худшим для другого. Часто эффективность по Парето определяется только для подмножеств всех возможных дележей. А именно только для разрезания на два непрерывных сектора (разрезание с минимальным числом разрезов).

Делёж называется ЭПОЗ, если он как ЭП, так и ОЗ.

Если оценки партнёров являются (аддитивными) мерами, следующая процедура «Движущийся нож» гарантирует деление, которое является ОЗ и ЭП при дележе на непрерывные сектора.

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

Другой партнёр (Выбирающий) наблюдает этот процесс в течение всего цикла. Затем, при следующем цикле он определяет позицию, в которой, с его точки зрения, получается максимальное значение для одного из двух секторов. Выбирающий получает этот сектор, а Вращающий получает оставшийся сектор.

Это деление очевидно является ОЗ, поскольку Вращающему всё равно, какие сектора выберет Выбирающий. Это является ЭП, поскольку нет деления, которое дало бы Выбирающему большее значение и оставило значение 1/2 для Вращающего.

Ограничения по аддитивности

Описанная выше процедура работает только если функция значений Вращающего аддитивна, так что равные части всегда имеют одно и то же значение 1/2. Если же она не аддитивна, то деление оставалось бы свободным от зависти, но не обязательно эффективным по Парето.

Более того, если оценки обоих игроков не аддитивны (так что ни один из них не может выступать в роли Вращающего), делёж ЭПОЗ не всегда существует.

Согласованный делёж и взвешенный пропорциональный делёж

Делёж называется точным (или согласованным), если значение куска $i$ равно в точности $w_{i}$ согласно всем партнёрам, где $w_{i}$ — предопределённые веса.

Предположим, что сумма всех весов равна 1, а значение пирога для всех агентов также нормализовано к 1. По теореме Стромквиста — Вудала для любого веса $w\in [0,1]$ существует подмножество $C_{w}$, которое является объединением максимум $n-1$ секторов, значение которого все партнёры оценивают в точности в $w$. Для случая $n=2$ агентов следует, что всегда существует согласованное деление пирога со связными секторами, где агенту 1 даём сектор, который сто́ит в точности $w_{1}$ для обоих агентов, а агенту 2 даём оставшийся сектор, который сто́ит $1-w_{1}=w_{2}$ для обоих агентов (см. статью Брамса, Джоса и Кламлера для альтернативного доказательства).

Это можно обобщить на любое число агентов — каждый кусок, за исключением последнего, требует не более $2(n-1)$ разрезов, так что общее число требуемых разрезов равно $2(n-1)^{2}$.

Делёж называется пропорциональным, если каждый из двух партнёров получает значение по меньшей мере 1/2. Делёж называется взвешенным пропорциональным (ВПД, англ. Weighted Proportional Division, WPR), если партнёр $i$ получает значение по меньшей мере $w_{i}$, где $w_{i}$ является предопределёнными весами, представляющими различные доли партнёров в торте. Описанная выше процедура показывает, что в пироге делёж ВПД со связными кусками всегда существует. Это контрастирует с некруглым тортом (интервалом), в котором взвешенный пропорциональный делёж (ВПД, англ. Weighted proportional division, WPR) со связными частями может не существовать.

Взвешенный делёж без обид

Если оценки партнёров абсолютно непрерывны по отношению друг к другу, тогда существует ВПД делёж который также является ВОЗ (взвешенный при отсутствии зависти, англ. weighted-envy-free, WEF) и эффективный по Парето (ЭП, англ. Pareto efficient, PE), а отношение между значениями партнёров равно в точности w₁/w₂.

Доказательство. Для любого угла t пусть $y(t)$ будет углом, при котором отношение ${\tfrac {v_{1}(t,y(t))}{v_{2}(t,y(t))}}={\tfrac {w_{1}}{w_{2}}}$.

Функция $v_{1}([t,y(t)])$ непрерывна от t и достигает максимума на некотором $t^{\ast }$. Режем пирог радиальными разрезами в точках $t^{\ast }$ и $y(t^{\ast })$, даём кусок $[t^{\ast },y(t^{\ast })]$ партнёру № 1 и дополнение партнёру и основная № 2. Разбиение является ВОЗ, поскольку значение каждого партнёра равны в точности его оценке. Оно также является ЭП, поскольку доля партнёра № 1 максимизировано, так что нет возможности дать больше партнёру № 2 без потерь для партнёра № 1.

Беспристрастный делёж

Беспристрастный делёж — это делёж, в котором субъективное значение обоих партнёров то же самое (то есть каждый партнёр одинаково доволен).

Всегда существует разделение пирога для двух партнёров, которое и свободно от зависти, и беспристрастно. Однако, на настоящее время не известно никакой процедуры для нахождения такого разделения.

Если значения мер партнёров абсолютно непрерывны относительно друг друга (то есть любой кусок, который имеет положительное значение для одного партнёра, имеет также положительное значение для другого партнёра), то существует свободное от зависти разбиение, которое также беспристрастно и эффективно по Парето. Опять же, не известно какой-либо процедуры для такого дележа.

Правильный делёж

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

Правило дележа называется диктаторским, если оно отдаёт весь торт единственному предварительно определённому партнёру.

Правило ЭП дележа правильно тогда и только тогда, когда оно диктаторское.

Три и более партнёров

Делёж без зависти для 3 партнёров

Процедура «Движущийся нож» Стромквиста может быть использована для разрезания при размерности 1, так что, очевидно, оно может быть использовано для разрезания пирога.

Но существует более простой алгоритм, который использует преимущество круглой формы пирога.

Партнёр A вращает три радиальных ножа непрерывно вокруг пирога, следя за тем, чтобы сектора имели (по его/её оценке) размеры 1/3-1/3-1/3.

Партнёр B оценивает значение этих трёх секторов. Обычно все они имеют различную ценность, но в некоторой точке два сектора будут иметь одно и то же значение. Так происходит, поскольку после вращения на 120 градусов сектор, имевший до этого наиболее важное значение, теперь будет иметь меньшее значение, а другой сектор теперь становится наиболее значимым. Следовательно, по теореме о промежуточном значении должно существовать положение при вращении, когда пользователь B видит два одинаковых сектора. В этой точке партнёр B говорит «стоп».

Затем партнёры выбирают сектора в порядке C — B — A. Партнёр C, конечно, не чувствует никакой зависти, поскольку он выбирает первым. Партнёр B имеет по меньшей мере один больший сектор для выбора, а партнёр A считает, что все куски имеют одинаковую ценность.

Версии дележа без зависти и эффективные по Парето

Для 3 партнёров, существует пирог и соответствующие меры, для которых никакое разрезание не будет ЭПОЗ.

Это верно также для более чем 3 партнёров. Это верно даже если все функции значений аддитивны и строго положительны (то есть любой партнёр оценивает любой кусок пирога).

Оба этих примера используют меры, которые почти однородны, но с очень тонким уточнением. Поскольку меры почти однородны, легко найти места разреза пирога, которые почти свободны от зависти и почти недоминируемы. Неизвестно, возможно ли найти примеры, в которых несогласия много больше.

Пропорциональный делёж с различными долями

Когда имеется 3 и более партнёров с различными долями, требуется взвешенно-пропорциональный делёж (ВПД). ВПД делёж со связными кусками не всегда существует.

Это аналогично невозможности для 1-мерного интервального торта и 2 партнёров (см. раздел Взвешенный пропорциональный делёж статьи Задача справедливого разрезания торта).

Литература

• Stromquist W., Woodall D. R. Sets on which several measures agree // Journal of Mathematical Analysis and Applications. — 1985. — Т. 108. — doi:10.1016/0022-247x(85)90021-6.
• Gale D. Mathematical entertainments // The Mathematical Intelligencer. — 2009. — Т. 15. — doi:10.1007/BF03025257.
• Barbanel J. B., Brams S. J., Stromquist W. Cutting a Pie is Not a Piece of Cake // American Mathematical Monthly. — 2009. — Т. 116, вып. 6. — doi:10.4169/193009709X470407.
• Thomson W. Children Crying at Birthday Parties. Why? // Economic Theory. — 2006. — Т. 31, вып. 3. — doi:10.1007/s00199-006-0109-3.
• Brams S. J., Jones M. A., Klamler C. Proportional pie-cutting // International Journal of Game Theory. — 2007. — Т. 36, вып. 3–4. — doi:10.1007/s00182-007-0108-z.
• Steven J. Brams, Alan D. Taylor, William S. Zwicker. A Moving-Knife Solution to the Four-Person Envy-Free Cake Division // Proceedings of the American Mathematical Society. — 1997. — Т. 125, вып. 2. — doi:10.1090/s0002-9939-97-03614-9.
• Walter Stromquist. A pie that can't be cut fairly // Dagstuhl Seminar Proceedings 07261. — 2007.