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

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

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

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

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

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

Каждый участник должен получить кусок со «справедливой» ценностью. Справедливость определяется на основе cубъективных функций ценности. Каждое лицо имеет субъективную функцию ценности , которая отображает подмножества в числа.

Функции предполагаются абсолютно непрерывными от длины, площади или (в общем случае) меры Лебега. Это означает, что нет «атомов», то есть особых точек, которым назначается одним или несколькими агентами положительное значение. Таким образом, все части торта делимы.

Кроме того, в некоторых случаях функции оценки предполагаются сигма-аддитивными.

Пример торта Следующий набор данностей будет использоваться в качестве иллюстрации: Торт состоит из двух частей — шоколадной и ванильной. Имеется двое участников — Алиса и Джордж. Алиса оценивает шоколадную часть в 9 единиц, а ванильную в 1 единицу. Джордж оценивает шоколадную часть в 6 единиц, а ванильную в 4.

Требования справедливости Оригинальным и наиболее общим критерием справедливости является пропорциональность (ПР, , PR). При пропорциональном делении торта каждый участник получает кусок, ценность которого он оценивает по меньшей мере в полной ценности всего торта. В примере выше пропорциональный делёж может быть получен передачей всей ванильной части и 4/9 шоколадной части Джорджу (с полной оценкой 6.66), а оставшаяся 5/9 шоколадная часть отдаётся Алисе (с полной оценкой 5). Символьно:

.

Критерий пропорциональности можно обобщить на ситуации, в которых права людей не равны. Например, при торт принадлежит пайщикам, так что один из них владеет 20%, а другой 80% торта. Это приводит к критерию взвешенной пропорциональности:

,

где wi являются весами, сумма которых равна 1.

Другим типичным критерием является отсутствие зависти (ОЗ, , EF). При завистливом дележе каждое лицо получает кусок, ценность которого по оценке этого лица не меньше ценности остальных кусков. Формальным языком:

.

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

Агенты Оценки из ОЗ следует ПР? из ПР следует ОЗ?2 аддитивные2 общие 3+аддитивные3+общие

Третьим, менее используемым критерием, является беспристрастность (, EQ). При беспристрастном дележе каждое лицо лакомится куском в точности с тем же значением оценки. В примере торта беспристрастное разрезание может быть получено путём передачи каждому участнику половины шоколадной и половины ванильной частей, так что каждый участник наслаждается значением 5. Символически:

.

Четвёртым критерием является точность. Если доля каждого партнёра i равна wi, то точный делёж — это делёж, в котором:

.

Если все веса равны (1/n), то разрезание называется совершенным и

.

Геометрические требования

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

Дополнительные требования В юриспруденции часто рассматривается экономическая эффективность разбиения. См. статью «Эффективное разрезание торта».

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

Результаты

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

Пропорциональный делёж

Для n человек с аддитивными оценками всегда существует пропорциональное разрезание. Наиболее используемые протоколы:

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

См. статью «» для описания деталей и полного списка литературы.

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

Завистливый делёж

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

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

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

Для (возможно) несвязных кусков главными результатами являются: Дискретная процедура Селфриджа — Конвея даёт разрезание без зависти для троих участников за не более чем 5 разрезов. Процедура «Движущийся нож» Брамса — Тейлора — Цвикера даёт разрезание без зависти для четверых участников за не более чем 11 разрезов. Вариант протокола «Последний уменьшивший» с повторным использованием находит аддитивную аппроксимацию разрезанию без зависти за ограниченное время. Конкретно, для любой константы протокол даёт разрезание, в котором значение для каждого участника по меньшей мере больше наибольшего значения минус за время . Три различные процедуры, одна Брамса и Тейлора (1995), другая Робертсона и Уэбба (1998) и ещё одна, процедура Пикурко (2000) дают свободное от зависти разрезание для человек. Оба алгоритма требуют конечного, но неограниченного числа разрезов. Процедура Азиза и Маккензи (2016) находит разрезание без зависти для человек за ограниченное число запросов.

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

См. статью «Завистливый делёж торта»Часто переводится «делёж без зависти» (калька с английского), хотя как раз присутствие зависти играет основную роль в этом дележе. () для деталей и полного списка литературы.

Эффективный делёж

Когда функции оценок аддитивны, существует (РП, , UM). Интуитивно, чтобы создать РП разрезание, нам нужно дать каждому участнику кусок торта со значением, которое для него максимально. В примере торта РП разрезание отдаст весь шоколад Алисе и всю ванильную часть Джорджу, достигая полезности .