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

Последний уменьшающий является самой ранней процедурой пропорционального дележа, разработанной для 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 {\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 ресурса (то есть знак неравенства в другую сторону).

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