Задача пропорционального разрезания торта

Задача пропорционального разрезания торта — это вид задачи справедливого разрезания торта. Это разбиение неоднородного ресурса («торта»), которое удовлетворяет критерию пропорциональности, а именно, что любой участник считает, что выделенная ему часть торта не хуже 1/n полной оценки торта.

Когда обсуждается пропорциональность, обычно делается два допущения:

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

Для двух человек процедура «Дели-и-выбирай» является классическим решением. Один человек делит ресурс на две половинки, которые он считает равными, а другой человек выбирает «половину», которая ему больше понравилась. Предположение неатомарности гарантирует, что разрезающий может разрезать (как он считает) на две равные части. Предположение аддитивности гарантирует, что оценки обоих участников будут для их кусков не менее 1/2.

Существует много способов распространить эту процедуру на более чем 2 человек. Каждый из этих способов имеет собственные преимущества и недостатки.

Последний уменьшающий является самой ранней процедурой пропорционального дележа, разработанной для n человек:

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

По индукции можно доказать, что каждый участник, придерживающийся правил, гарантированно получит 1/n торта независимо от действий других участников. Это дискретная процедура, которую можно осуществлять по раундам. В худшем случае потребуется ${\displaystyle n\times (n-1)/2=O(n^{2})}$ действий — по одному действию на каждого участника в каждом раунде. Однако большинство этих действий могут быть сделаны на бумаге. Только ${\displaystyle n-1}$ разрезов действительно нужны. Следовательно, если торт связен, то можно гарантировать, каждый кусок будет связен.

Процедура «Движущийся нож»^[англ.] Дубинса — Спеньера является непрерывной версией «Последнего уменьшающего»^[1].

• Нож передвигается по торту параллельно от одного конца к другому.
• Участник говорит «стоп», когда он считает, что слева от ножа достигли значения ${\displaystyle {\tfrac {1}{n}}}$. Кусок торта отрезается и отдаётся сказавшему участнику.
• Эта процедура повторяется с остатком торта и оставшимися участниками. Последний участник получает остаток торта.

Протокол Финка — это алгоритм, который продолжает деление на достаточно мелкие «равные» порции.

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

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

Одиночный делящий^[англ.] — это процедура, основанная на разбиении поровну, осуществлённом единственным агентом. Преимущество процедуры в том, что её можно обобщить для cимметричного справедливого разрезания торта.

См. также:^[2].

Используя стратегию разделяй и властвуй можно достичь пропорциональный делёж за время ${\displaystyle O(n\log n)}$^[3]. Для простоты описанная здесь процедура приведена для чётного числа участников, но её можно легко приспособить на любое число участников:

• Каждого участника просят провести линию, делящую торт на два куска, которые он считает равноценными. Требуется, чтобы разрезы не пересекались. Самый простой путь это гарантировать — позволить только горизонтальные прямые или только вертикальные.
• Алгоритм сортирует n линий в возрастающем порядке и разрезает торт в медиане линий. Например, если имеется 4 участника, которые проводят линии в точках ${\displaystyle x=1,x=3,x=5}$ и ${\displaystyle x=9}$, алгоритм режет торт вертикально в точке ${\displaystyle x=4}$.
• Алгоритм назначает каждой из двух половинок n/2 участников — партнёров, чьи линии находятся внутри половинки. Например, участники, которые нарисовали линии в точках ${\displaystyle x=1}$ и ${\displaystyle x=3}$ назначаются западной половине, а оставшиеся участники назначаются восточной половинке. Каждая половинка делится рекурсивно среди n/2 участников, назначенных этой половинке.

Можно показать по индукции, что любому участнику, играющему по правилам, гарантирован кусок с оценкой не менее 1/n независимо от того, как ведут себя остальные участники.

Благодаря стратегии разделяй и властвуй число итераций будет лишь O(log n), в отличие от значения O(n) в процедуре «Последний уменьшающий». На каждой итерации каждому участнику вменяется сделать одну пометку. Следовательно, общее число пометок будет равно ${\displaystyle O(n\log n)}$.

Алгоритм имеет рандомизированную версию, которая может быть использована для сокращения числа отметок. См. статью «Алгоритм Ивена — Паса».

Другой подход к разрезанию торта заключается в позволении каждому участнику извлечь некоторое число кусков, зависящее от числа участников, p(n), и дать каждому участнику один из его выбранных кусков так, чтобы куски не перекрывались.

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

1. Каждый участник делит приватно торт на n интервалов, которые он считает равными по ценности, назовём эти куски кандидатами.
2. Протокол упорядочивает ${\displaystyle n^{2}}$ кандидатов по порядку их восточных границ (с запада на восток) и выбирает отрезок с наиболее западным восточным концом. Этот отрезок называется финальным куском.
3. Протокол даёт конечный кусок его владельцу и удаляет всех кандидатов с ним пересекающихся. Шаг № 2 затем повторяется для оставшихся отрезков остальных ${\displaystyle n-1}$ участников.

Правило выбора на шаге № 2 гарантирует, что на каждой итерации максимум один отрезок каждого участника удаляется. Следовательно, после каждой итерации число отрезков на участника остаётся равным числу участников и процесс может продолжаться пока все участники не получат по отрезку^[4].

Этот протокол требует от каждого участника ответить на n запросов, так что сложность по запросам равна ${\displaystyle O(n^{2})}$, аналогично процедуре «Последний уменьшающий».

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

Мы можем разрезать торт с помощью O(n) запросов, если мы пойдём на компромисс:

• Вместо гарантии полной пропорциональности мы гарантируем частичную пропорциональность, то есть каждый участник получает определённую постоянную долю f(n) от полного значения, где ${\displaystyle f(n)<{\tfrac {1}{n}}}$.
• Вместо передачи каждому участнику отдельного связного куска мы передаём участнику объединение одного и более непересекающихся кусков.

Общая схема следующая^[5]:

1. Каждый участник приватно делит торт на равных an кусков согласно его субъективной оценке. Эти ${\displaystyle n\cdot an}$ кусков назовём кандидатами.
2. Каждый участник выбирает 2d кандидатов равномерно-случайно с возвратом. Кандидаты группируются в d пар, о которых участник докладывает алгоритму. Эти ${\displaystyle n\cdot d}$ пар назовём четвертьфинальными наборами.
3. Из каждого четвертьфинального набора алгоритм выбирает единственный кусок — тот, который пересекает наименьшее число других кандидатов. Эти ${\displaystyle n\cdot d}$ кусков назовём полуфинальными.
4. Для каждого участника алгоритм выбирает единственный кусок, назовём его финальным. Финальные куски отбираются так, что каждая точка торта была покрыта максимум двумя финальными кусками (см. ниже). Если это сделать удаётся, переходим к шагу № 5. Если не удаётся, возвращаемся к шагу № 1.
5. Каждый кусок торта, который принадлежит только одному финальному куску, отдаём владельцу этого куска. Каждая часть торта, которая принадлежит двум финальным кускам, делится пропорционально любым алгоритмом детерминистического пропорционального дележа.

Алгоритм гарантирует, что с вероятностью ${\displaystyle O(1a^{2})}$ каждый участник получит по меньшей мере половину от одного из его кусков-кандидатов, откуда следует (если оценки аддитивны), что оценка не будет меньше 1/2an. Имеется O(n) кусков-кандидатов и O(n) дополнительных делений на шаге № 5, каждый из которых занимает время O(1). Следовательно, полное время работы алгоритма равно O(n).

Основная проблема в этой схеме — выбор окончательных кусков на шаге № 4. Для подробностей см. Протокол Эдмондса — Пруса.

Результаты по сложности формулируются в терминах «стандартной модели Робертсона — Уэбба», то есть они относятся к процедурам, использующим два типа действий: «Оценка» и «Разрез».

Любая процедура детерминированного пропорционального дележа для ${\displaystyle n\geqslant 3}$ участников должна использовать по меньшей мере n действий, даже если все функции оценок идентичны^[3].

Более того, любая детерминированная или рандомизированная (вероятностная) процедура пропорционального дележа, назначающего каждому участнику связный кусок, должна использовать ${\displaystyle \Omega (n\log n)}$ действий^[6].

Более того, любая процедура детерминированного пропорционального дележа должна осуществить ${\displaystyle \Omega (n\log n)}$ действий, даже если процедуре разрешается назначать каждому участнику кусок, являющийся объединением отрезков, и даже если процедуре разрешено гарантировать лишь приблизительную справедливость. Доказательство основывается на ограничении снизу сложности нахождения для отдельных игроков куска торта, который имеет большое значение и тонка по ширине^[7][8].

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

Если игроки способны отрезать лишь с конечной точностью, то нижняя граница ${\displaystyle \Omega (n\log n)}$ также включает рандомизированные протоколы^[7][8].

Следующая таблица содержит известные результаты^[5]:

Пропорцио- нальность (полная/ частичная)	Куски (связные/ несвязные)	Тип протокола (детерми- нированный/ рандоми- зированный)	Запросы (точные/ приближённые)	Число запросов
полная	связные	детерминированный	точные	${\displaystyle O(n\log n)}$ [3] ${\displaystyle \Omega (n\log n)}$[6]
полная	связные	детерминированный	приближённые	${\displaystyle \Omega (n\log n)}$[6]
полная	связные	рандомизированный	точные	${\displaystyle O(n\log n)}$ [3] ${\displaystyle \Omega (n\log n)}$[6]
полная	связные	рандомизированный	приближённые	${\displaystyle \Omega (n\log n)}$[6]
полная	несвязные	детерминированный	точные	${\displaystyle O(n\log n)}$[3] ${\displaystyle \Omega (n\log n)}$[7][8]
полная	несвязные	детерминированный	приближённые	${\displaystyle \Omega (n\log n)}$[7][8]
полная	несвязные	рандомизированный	точные	${\displaystyle O(n\log n)}$[3]
полная	несвязные	рандомизированный	приближённые	${\displaystyle \Omega (n\log n)}$[7][8]
частичная	связные	детерминированный	точные	${\displaystyle \Omega (n\log n)}$[3] ${\displaystyle \Omega (n\log n)}$[7][8]
частичная	связные	детерминированный	приближённые	${\displaystyle \Omega (n\log n)}$[7][8]
частичная	связные	рандомизированный	точные	${\displaystyle \Omega (n\log n)}$[3]
частичная	связные	рандомизированный	приближённые	${\displaystyle \Omega (n\log n)}$[7][8]
частичная	несвязные	детерминированный	точные	${\displaystyle O(n\log n)}$ [3] ${\displaystyle \Omega (n\log n)}$[7][8]
частичная	несвязные	детерминированный	приближённые	${\displaystyle \Omega (n\log n)}$[7][8]
частичная	несвязные	рандомизированный	точные	O(n) [5]
частичная	несвязные	рандомизированный	слабо приближённые (не зависящие от ошибки оценки)	O(n)[5]
частичная	несвязные	рандомизированный	приближённые	${\displaystyle \Omega (n\log n)}$[7][8]

Критерий пропорциональности может быть обобщён до ситуации, в которой причитающиеся доли^[англ.] участников не равны. Например, ресурс может принадлежать двум держателям акций, Алисе принадлежит ${\displaystyle {\tfrac {8}{13}}}$ акций, а Джорджу принадлежит ${\displaystyle {\tfrac {5}{13}}}$. Это приводит к критерию взвешенной пропорциональности (англ. weighted proportionality, WPR) — есть некоторые веса w_i, сумма которых равна 1, а любой участник i должен получить по меньшей мере долю w_i ресурса по его собственной оценке. Некоторые алгоритмы могут быть использованы для нахождения WPR разбиения. Главная проблема в том, что число разрезов может быть велико, даже если имеется всего два участника. См. Пропорциональное разрезание торта с разными причитающимися долями^[англ.].

Суперпропорциональный делёж является дележом, а котором каждый участник получает строго больше 1/n ресурса по его собственной субъективной оценке.

Конечно, такое разбиение не всегда существует — если все участники имеют в точности те же самые функции оценок, лучшее, что мы можем сделать, это дать каждому в точности 1/n. Таким образом, необходимым условием существования суперпропорционального дележа является требование, чтобы не все партнёры имели одну и ту же меру оценок.

Удивительно, но если функции оценок аддитивны и не атомарны, это условие также достаточно. То есть, если имеется по меньшей мере два участника, функции оценок которых лишь слегка отличаются, то существует суперпропорциональный делёж, в котором все участники получают более 1/n. См. Суперпропорциональный делёж для подробностей.

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

Когда «торт» делится в двумерном пространстве (плоскости), например, при делении участков земли или рекламного пространства в печати или электронных медиа, часто требуется, чтобы куски удовлетворяли некоторым геометрическим ограничениям вдобавок к связности. Например, может требоваться, чтобы каждый кусок был квадратом, толстым прямоугольником (то есть длина и ширина не отличаются в несколько раз) или толстой фигурой^[англ.] общего вида. При наличии таких ограничений на фигуры пропорциональный делёж обычно не существует, но обычно существует частично пропорциональный делёж и его можно найти с помощью эффективных алгоритмов^[9].

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

Например, рассмотрим торт, содержащий 500 грамм шоколадной части и 500 грамм ванильной, который делят два участника, один из которых хочет только шоколадные части, а другой предпочитает ванильные. Многие протоколы разрезания торта дадут каждому агенту 250 грамм шоколадной части и 250 грамм ванильной. Это деление пропорционально, поскольку каждый участник получает 0,5 полного значения, так что нормализованная общая польза равна 1. Однако этот делёж будет очень неэффективным, поскольку мы можем отдать всю шоколадную часть первому участнику, а всю ванильную часть другому участнику, получив нормализованную общую пользу 2.

Задача оптимального пропорционального дележа — это задача поиска пропорционального разбиения, которое максимизирует общую пользу среди всех возможных пропорциональных распределений. В настоящее время задача имеет решение только для очень специальных тортов, когда он является одномерным отрезком и функции плотности полезности линейны (то есть, ${\displaystyle u(x)=Ax+B}$). В общем случае задача NP-трудна. Если функции полезности не нормализованы (то есть, мы позволяем каждому участнику иметь различные оценки полной значимости торта), задача NP-трудна даже для аппроксимации со множителем ${\displaystyle {\tfrac {1}{\sqrt {n}}}}$^[10].

Честность не является свойством дележа, а, скорее, свойством протокола. Все протоколы пропорционального дележа слабо честны в том смысле, что любой участник, действующий согласно его истинной оценке, гарантированно получает по меньшей мере 1/n (или 1/an в случае частично пропорционального протокола) независимо от того, как себя ведут остальные участники. Даже если другие участники образуют коалицию только с целью навредить ему, он всё равно получит свою гарантированную пропорцию^[11].

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

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

Эти механизмы можно расширить для получения cуперпропорционального дележа, если он существует^[12]:

1. Просим каждого участника предоставить полную меру оценки.
2. Выбираем случайное разбиение (см. статью Мосселя и Тамуза^[12] для подробностей).
3. Если случайное разбиение оказывается суперпропорциональным согласно сообщённым мерам, осуществляем его. В противном случае используем честный механизм обеспечения совершенного дележа.

Если суперпропорциональный делёж существует, есть положительный шанс, что он будет получен на шаге 2. Следовательно, ожидаемое значение для любого честного участника строго больше 1/n. Чтобы понять, что механизм честен, рассмотрим три случая: (a) Если выбранное разбиение действительно суперпропорционально, то единственным возможным результатом лжи будет ввести в заблуждение механизм, чтобы он считал, что разбиение не суперпропорционально. Это заставит механизм применить совершенный делёж, который хуже для всех участников, включая и лжеца. (b) Если выбранное разбиение не является суперпропорциональным только ввиду указания лжецом значения 1/n и меньше, единственным эффектом лжи будет заставить механизм думать, что разбиение является суперпропорциональным и использовать его, что навредит только самому лжецу. (c) Если выбранное разбиение действительно не суперпропорционально, это даёт другому участнику значение 1/n или менее, то ложь не приведёт ни к какому эффекту, поскольку разбиение не будет использоваться вообще.

Если ресурс, требующий разделения, нежелателен (подобно дележу обязанностей), пропорциональный делёж определяется как делёж, дающий каждому лицу не более 1/n ресурса (то есть знак неравенства в другую сторону).

Большинство алгоритмов пропорционального дележа можно приспособить для дележа обязанностей без затруднений.

• Точный делёж. Там же смотрите «Совершенный делёж»

• Обзор пропорционального и других дележей появился в статье:
• Austin A. K. Sharing a Cake // The Mathematical Gazette. — 1982. — Т. 66, вып. 437. — С. 212–215. — doi:10.2307/3616548. — JSTOR 3616548.
• Lester Eli Dubins, Edwin Henry Spanier. How to Cut a Cake Fairly // The American Mathematical Monthly. — 1961. — Т. 68, вып. 1. — doi:10.2307/2311357. — JSTOR 2311357.
• Even S., Paz A. A note on cake cutting // Discrete Applied Mathematics. — 1984. — Т. 7, вып. 3. — doi:10.1016/0166-218x(84)90005-2.
• Jeff Edmonds, Kirk Pruhs. Balanced Allocations of Cake // 2006 47th Annual IEEE Symposium on Foundations of Computer Science (FOCS'06). — 2006. — ISBN 978-0-7695-2720-8. — doi:10.1109/focs.2006.17.
• Gerhard J. Woeginger. On the complexity of cake cutting // Discrete Optimization. — 2007. — Т. 4, вып. 2. — doi:10.1016/j.disopt.2006.07.003.
• Jeff Edmonds. Cake cutting really is not a piece of cake // Proceedings of the Seventeenth Annual ACM-SIAM Symposium on Discrete Algorithm - SODA '06. — 2006. — ISBN 978-0898716054. — doi:10.1145/1109557.1109588.
• Jeff Edmonds. Cake cutting really is not a piece of cake // ACM Transactions on Algorithms. — 2011. — Т. 7, вып. 4. — doi:10.1145/2000807.2000819.
• Erel Segal-Halevi, Shmuel Nitzan, Avinatan Hassidim, Yonatan Aumann. Fair and square: Cake-cutting in two dimensions // Journal of Mathematical Economics. — 2017. — Т. 70. — doi:10.1016/j.jmateco.2017.01.007. — arXiv:1409.4511.
• Xiaohui Bei, Ning Chen, Xia Hua, Biaoshuai Tao, Endong Yang. Optimal Proportional Cake Cutting with Connected Pieces // AAAI Conference Proceedings. — 2012.
• Hugo Steinhaus. The problem of fair division // Econometrica. — 1948. — Т. 16, вып. 1. — JSTOR 1914289.
• Elchanan Mossel, Omer Tamuz. Truthful Fair Division // . — 2010. — Т. 6386. — (Lecture Notes in Computer Science). — ISBN 978-3-642-16169-8. — doi:10.1007/978-3-642-16170-4_25.