Задача справедливого разрезания торта

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

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

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

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

Предположения

Имеется торт $C$, который обычно предполагается конечным одномерным отрезком, двумерным многоугольником или конечным подмножеством многомерного евклидова пространства $\mathbb {R} ^{d}$.

Имеется $n$ человек с равными правами на $C$.

$C$ нужно разрезать на $n$ таких непересекающихся подмножеств, что каждый участник получит отдельное подмножество. Кусок, предназначенный для участника $i$, обозначается как $X_{i}$, и $C=X_{1}\sqcup \cdots \sqcup X_{n}$.

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

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

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

Пример торта

Будем использовать следующий торт в качестве иллюстрации:

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

Требования справедливости

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

$\forall {i}:\ V_{i}(X_{i})\geqslant 1/n$.

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

$\forall i:V_{i}(X_{i})\geqslant w_{i}$,

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

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

$\forall i,j:\ V_{i}(X_{i})\geqslant V_{i}(X_{j})$.

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

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

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

$\forall i,j:\ V_{i}(X_{i})=V_{j}(X_{j})$.

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

$\forall {i,j}:\ V_{i}(X_{j})=w_{j}$.

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

$\forall i,j:\ V_{i}(X_{j})=1/n$.

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

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

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

Дополнительные требования

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

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

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

Результаты

2 человека – пропорциональный и свободный от зависти делёж

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

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

Основная статья: Пропорциональное деление торта

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

• Процедура «последний уменьшивший», протокол, который может гарантировать, что $n$ кусков будут связными (то есть никто из участников не получит два или более отдельных кусков). В частности, если торт является одномерным интервалом, каждый участник получит интервал. Протокол дискретен и может быть осуществлён по раундам. Он требует $O(n^{2})$ действий.
• Процедура «Движущийся нож» Дубинса — Спеньера является непрерывной по времени версии протокола «Последний уменьшающий».
• Протокол Финка (известный также как последовательные пары или одиночный выбирающий) является дискретным протоколом, который может быть использован для разрезания в режиме онлайн — если известно пропорциональное разрезание для $n-1$ партнёров, при вступлении нового партнёра в игру протокол модифицирует существующее разрезание так, что пришедший участник и уже находящиеся в дележе участники получают по $1/n$. Недостатком протокола является то, что каждый партнёр получает большое число отдельных кусочков.
• Протокол Ивена — Паза, основанный на непрерывном делении пополам торта и группы агентов и требующий всего $O(n\log n)$ действий. Это самый быстрый возможный детерминированный протокол для пропорционального дележа и самый быстрый возможный протокол для пропорционального дележа, при котором гарантируется, чтобы все куски были связными.
• Протокол Эдмондса — Пруса является рандомизированным протоколом, который требует всего $O(n)$ действий, но гарантирует только частично пропорциональное разрезание (каждый участник получает по меньшей мере $1/an$, где $a$ — некоторая константа), и может дать каждому участнику набор «крошек» вместо связного куска.
• Протокол дележа земли Бека может дать пропорциональный делёж спорной территории среди нескольких соседствующих стран. При этом каждая страна получает долю, которая и связна, и граничит с текущей территорией страны.
• Протокол суперпропорционального дележа Вудала даёт делёж, при котором каждый участник получает строго больше $1/n$, если задано, что по меньшей мере два участника имеют разное мнение о ценности по меньшей мере одного куска.

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

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

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

Основная статья: Завистливый делёж торта

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

Для связных кусков главными результатами являются:

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

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

Для (возможно) несвязных кусков главными результатами являются:

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

Отрицательный результат в общем случае много слабее, чем в случае связности. Всё, что мы знаем — любой алгоритм разрезания без зависти должен использовать по меньшей мере $\Omega (n^{2})$ запросов. Существует большая щель между этим результатом и вычислительной сложности известных процедур.

См. статью «Завистливый делёж торта» (англ. envy-free cake-cutting) для деталей и полного списка литературы.

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

Основная статья: Эффективное разрезание торта

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

Этот процесс легко осуществить, если функции оценок кусочно постоянны, то есть торт можно поделить на куски, такие что плотности цены на каждом куске постоянна для всех участников. Когда функции оценок не кусочно постоянны, существование РП разрезаний основывается на обобщении этой процедуры для функций оценки с помощью теоремы Радона — Никодима, см. теорему 2 в статье Дубинса и Спеньера.

Когда торт одномерен и куски должны быть связными (то есть непрерывными отрезками), простой алгоритм назначения агенту куска, который наиболее значим, не работает. В этом случае задача нахождения РП разрезания является NP-трудной задачей и более того, невозможна никакая FPTAS схема, если только не P = NP. Существует 8-кратный аппроксимирующий алгоритм и алгоритм параметризованной сложности, который экспоненциален от числа игроков.

Для любого множества положительных весов взвешенное РП разбиение может быть найдено аналогичными методами. Следовательно, эффективные по Парето (ЭП, англ. Pareto efficiency, PE) разбиения всегда существуют.

Процедурная справедливость

Основная статья: Симметричное справедливое разрезание торта

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

• Анонимность требует, чтобы в случае перестановки агентов и повторения процедуры каждый агент получил в точности тот же кусок, что и при исходном дележе. Это строгое условие. В настоящее время анонимная процедура известна только для 2 агентов.
• Симметрия требует, чтобы в случае, когда агенты переставляются и процедура повторяется для переставленных агентов, каждый агент получает то же самое значение, что и в исходном дележе. Это более слабое условие, чем анонимность. На настоящий момент симметричные и пропорциональные процедуры известны для любого числа агентов и они требуют $O(n^{3})$ запросов. Симметричная и свободная от зависти процедура известна для любого числа агентов, но требует существенно более длительного выполнения — она требует $n!$ выполнений существующей свободной от зависти процедуры.
• Аристотеличность требует, чтобы, если два агента имеют идентичные меры значимости, они получат то же самое значение. Это слабее симметрии и удовлетворяется любой свободной от зависти процедурой. Более того, аристотеличные и пропорциональные процедуры известны для любого числа агентов и требуют $O(n^{3})$ запросов.

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

Эффективный справедливый делёж

Для n человек с аддитивными функциями значений всегда существует ЭПОЗ делёж.

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

Если торт является одномерной окружностью (например, интервалом, в котором две конечные точки топологически отождествлены) и каждое лицо должно получить связную дугу, то предыдущий результат не верен — ОЗ делёж не обязательно будет ЭП. Кроме того, есть пары (неаддитивных) функций оценок, для которых никакого ЭПОЗ дележа не существует. Однако, если имеется 2 агента и хотя бы один из них имеет аддитивную функцию оценки, то ЭПОЗ делёж существует.

Если торт одномерен, но любое лицо может получить разрывное подмножество его, ОЗ делёж не обязательно будет ЭП. В этом случае требуются более сложные алгоритмы для поиска ЭПОЗ дележа.

Если функции оценок аддитивны и кусочно постоянны, то существует алгоритм, который находит ЭПОЗ делёж. Если функции плотности оценок аддитивны и Липшиц-непрерывны, то они могут быть аппроксимированы кусочно константными функциями «насколько хотим близко», поэтому этот алгоритм аппроксимирует ЭПОЗ делёж «насколько хотим близко».

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

Неаддитивные процедуры

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

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

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

См. также

• Задача справедливого распределения объектов – похожая задача, где предметы дележa неделимы.

Ссылки

• A list of books about fair division
• A list of research papers about fair division