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

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

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

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

Простые процедуры Последний уменьшающий является самой ранней процедурой пропорционального дележа, разработанной для n человек: Одного из участников просят выделить кусок, который он оценивает в 1/n. Другие участники в свою очередь имеют возможность возразить и объявить, что кусок больше 1/n. В этом случае его просят уменьшить кусок так, чтобы по его оценке оставшаяся часть куска составляла 1/n. Последний участник, уменьшивший кусок, его получает. Оставшиеся участники делят оставшуюся часть торта тем же способом среди оставшихся человек. По индукции можно доказать, что каждый участник, придерживающийся правил, гарантированно получит 1/n торта независимо от действий других участников. Это дискретная процедура, которую можно осуществлять по раундам. В худшем случае потребуется действий — по одному действию на каждого участника в каждом раунде. Однако большинство этих действий могут быть сделаны на бумаге. Только разрезов действительно нужны. Следовательно, если торт связен, то можно гарантировать, каждый кусок будет связен.

Процедура «Движущийся нож» Дубинса — Спеньера является непрерывной версией «Последнего уменьшающего». Нож передвигается по торту параллельно от одного конца к другому. Участник говорит «стоп», когда он считает, что слева от ножа достигли значения . Кусок торта отрезается и отдаётся сказавшему участнику. Эта процедура повторяется с остатком торта и оставшимися участниками. Последний участник получает остаток торта.

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

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

См. также:.

Рекурсивное деление пополам

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

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

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

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

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

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

В качестве простого примера процедуры выбора представим себе торт в виде одномерного отрезка и каждый участник хочет получить отдельный связный отрезок. Используем следующий протокол: Каждый участник делит приватно торт на n интервалов, которые он считает равными по ценности, назовём эти куски кандидатами. Протокол упорядочивает кандидатов по порядку их восточных границ (с запада на восток) и выбирает отрезок с наиболее западным восточным концом. Этот отрезок называется финальным куском. Протокол даёт конечный кусок его владельцу и удаляет всех кандидатов с ним пересекающихся. Шаг № 2 затем повторяется для оставшихся отрезков остальных участников. Правило выбора на шаге № 2 гарантирует, что на каждой итерации максимум один отрезок каждого участника удаляется. Следовательно, после каждой итерации число отрезков на участника остаётся равным числу участников и процесс может продолжаться пока все участники не получат по отрезку.

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

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

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

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

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

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

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

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

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

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

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

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

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

Пропорцио-нальность(полная/частичная) Куски(связные/несвязные) Тип протокола(детерми-нированный/рандоми-зированный) Запросы(точные/ приближённые) Числозапросовполнаясвязные детерминированный точные полнаясвязные детерминированный приближённые полнаясвязные рандомизированный точные полнаясвязные рандомизированный приближённые полнаянесвязные детерминированный точные полнаянесвязные детерминированный приближённые полнаянесвязные рандомизированный точные полнаянесвязные рандомизированный приближённые частичнаясвязные детерминированный точные частичнаясвязные детерминированный приближённые частичнаясвязные рандомизированный точные частичнаясвязные рандомизированный приближённые частичнаянесвязные детерминированный точные частичнаянесвязные детерминированный приближённые частичнаянесвязные рандомизированный точные O(n) частичнаянесвязные рандомизированный слабоприближённые (не зависящие от ошибкиоценки)O(n)частичнаянесвязные рандомизированный приближённые

Варианты

Различные причитающиеся доли