Протокол Эдмондса — Пруса

Протокол Эдмондса – Пруса — это протокол справедливого разрезания торта. Его целью является получение частично пропорционального дележа разнородного ресурса среди n людей, так что каждый участник получает подмножество торта (кусок), который каждый участник оценивает по меньшей мере в 1/an от полной оценки, где $a\geqslant 10$ является некоторой достаточно большой константой. Алгоритм является вероятностным со временем работы O(n) с вероятностью успеха, близкой к 1. Протокол разработали Джефф Эдмонд и Кирк Прус, которые они же позднее улучшили вместе с Джайсингхом Соланки.

Мотивация

Пропорциональный делёж торта может быть получен с помощью алгоритма рекурсивного деления пополам за время $O(n\log n)$. Некоторые результаты о сложности показывают, что это время работы оптимально в широком диапазоне предположений. В частности, рекурсивное деление пополам является самым быстрым алгоритмом для получения полной пропорциональности, когда куски должны быть связны, и оно является самым быстрым из возможных детерминированных алгоритмов для достижения даже частичной пропорциональности и даже если разрешается резать на несвязные куски. Есть случай, который не покрыт результатами сложности, это случай вероятностных алгоритмов, гарантирующих лишь частичную пропорциональность и возможность несвязности кусков. Протокол Эдмондса — Пруса нацелен на обеспечения времени работы O(n) как раз для этого случая.

Протокол

Общая схема, следуя Эдмундсу и Прусу, следующая:

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

Алгоритм гарантирует, что с большой вероятностью каждый участник получает по меньшей мере половину от его куска-кандидата, откуда следует (если функции предпочтений аддитивны), что значение будет не менее ${\tfrac {an}{2}}$.

Имеется O(n) кусков-кандидатов и O(n) дополнительных разрезов на шаге #5, которые берут время O(1). Следовательно, полное время работы алгоритма равно O(n).

Главной задачей в этой схеме является выбор финальных кусков на шаге #4:

Начнём с создания графа пересечений, графа, вершинами которого являются полуфинальные куски, а дуга из куска I участника i в кусок J участника j существует, если кусок I пересекается с J куском участника j (следовательно, если мы выбираем кусок I и хотим избежать пересечений, мы должны выбрать и кусок J также).

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

Сначала рассмотрим специальный случай, в котором все участники имеют те же самые функции предпочтений (а следовательно, одинаковые наборы кусков-кандидатов). В этом случае вероятность парного пути легко вычислить, поскольку вероятность каждой дуги равна 1/an, а все рёбра независимы, так что вероятность конкретного парного пути длины k равна ${\tfrac {1}{(an)^{k}}}$, а вероятность какого-либо парного пути не превосходит:

$\sum _{k}{\frac {(2dn)!}{(2dn-k)!(an)^{k}}}=O\left({\frac {1}{a^{2}}}\right)$

При выборе d=1 и достаточно большого a можно сделать эту вероятность произвольно малой. Это верно, даже если мы опустим фазу выбора полуфиналистов (#3) и будем считать всех четвертьфиналистов полуфиналистами.

Заметим, что этот случай аналогичен модели шаров в урнах. Это доказывает, что если d урн выбраны произвольно для каждого шара, то можно выбрать одну урну для каждого шара так, что все урны будут различны (максимальное число шаров равно 1).

В общей модели торта, когда функции предпочтений различны, вероятности рёбер в графе пересечений зависимы, но благодаря фазе выбора полуфиналистов мы можем показать, что вероятность того, что граф пересечений содержит парный путь длины по меньшей мере 3, не превосходит ${\frac {32d^{5}}{a^{2}\cdot (a-4d^{2})}}$.

Остаётся рассмотреть парные пути длиной 2. К сожалению, вероятность получить такой парный путь в графе пересечений не будет ничтожной. Однако, с большой вероятностью, можно разбить участников на две группы, в каждой из которых нет парных путей длины 2. Следовательно, мы можем прогнать алгоритм выбора финальных кусков дважды по одному разу для каждой группы. Пересечение может встретиться только между финальными кусками различных групп, следовательно, перекрытие в каждой точке торта не превосходит 2. Вероятность, что такое 2-разбиение невозможно, не превосходит ${\frac {16d^{3}}{a^{3}}}+{\frac {8d^{2}}{a^{2}}}$.

После суммирования двух выражений выше и принятия d = 2 мы получим, что вероятность неудачи остаётся $O\left({\frac {1}{a^{2}}}\right)$. Напомним, что a является отношением пропорциональности — чем большее значение мы желаем гарантировать каждому участнику, тем более вероятно, что делёж будет неудачным и должен быть начат с шага №1.

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

Высокодостоверный протокол

Можно далее уменьшить вероятность неудачи, используя следующую схему:

• Дважды прогоняем исходный протокол.
• На каждом прогоне удаляем всех участников, оказавшихся в начале парного пути, и распределяем финальные куски только среди оставшихся участников, как в исходном алгоритме.
• Если каждый участник не был удалён ни при одном прогоне, мы получили нужное, поскольку каждый участник теперь обладает одним финальным куском.

Вероятность удаления конкретного участника в каждом проходе равна $O\left({\frac {1}{n}}\right)$. Вероятность удаления конкретного участника в обоих прогонах равна $O\left({\frac {1}{n^{2}}}\right)$. Следовательно, вероятность неудачи равна $O\left({\frac {n}{n^{2}}}\right)=O\left({\frac {1}{n}}\right)$, и она стремится к 0 по мере увеличения n, даже если отношение частичной пропорциональности a сохраняется постоянной.

Связанные проблемы

Модель торта можно рассматривать как обобщение модели задачи о шарах. Эта модель находит широкое приложение в таких областях, как балансировка нагрузки. В этих ситуациях шар представляет работу, которую можно назначить различным машинам (в нашей терминологии – урнам). Грубо говоря, распределение нагрузки одинаковых машин — это шары и урны, а распределение нагрузки неодинаковых машин — это разрезание торта. Следовательно, вполне понятно, что модель торта и протокол Эдмондса – Пруса должны иметь интересные приложения в условиях распределения нагрузки на неодинаковых машинах.