Справедливое разрезание торта

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

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

Прототипическая процедура для справедливого разрезания торта — раздели и выбери , которая упоминается в книге Бытия для разрешения конфликта Авраама и Лота . Эта процедура решает проблему справедливого раздела для двух человек. Современное изучение справедливого разрезания торта было начато во время Второй мировой войны , когда Гуго Штейнхауз попросил своих студентов Стефана Банаха и Бронислава Кнастера найти обобщение раздели и выбери для трех или более человек. Они разработали последнюю процедуру уменьшения . ^[1] Сегодня справедливое разрезание торта является предметом интенсивных исследований в области математики , компьютерных наук , экономики и политологии . ^[2]

Существует торт C , который обычно предполагается либо конечным одномерным сегментом, либо двумерным многоугольником, либо конечным подмножеством многомерной евклидовой плоскости R ^d .

Есть n человек с субъективными функциями ценности над C. Каждый человек i имеет функцию ценности V _i , которая отображает подмножества C в числа. Все функции ценности предполагаются абсолютно непрерывными относительно длины, площади или (в общем случае) меры Лебега . ^[3] Это означает, что нет «атомов» — нет особых точек, которым один или несколько агентов присваивают положительное значение, поэтому все части торта делятся. Во многих случаях функции ценности предполагаются сигма-аддитивными (значение целого равно сумме значений его частей).

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

N людей имеют равные права на C. То есть, нет спора о правах людей – все согласны, что все остальные имеют право на справедливую долю. Единственная проблема – как разделить пирог так, чтобы каждый человек получил справедливую долю .

В следующих примерах в качестве иллюстрации будет использован следующий торт.

• Торт состоит из двух частей: шоколадной и ванильной.
• Есть двое: Элис и Джордж.
• Элис оценивает шоколад в 9, а ваниль в 1.
• Джордж оценивает шоколад в 6 баллов, а ваниль в 4 балла.

Первоначальным и наиболее распространенным критерием справедливости является пропорциональность (PR). При пропорциональном разрезании торта каждый человек получает кусок, который он оценивает как минимум 1/ n от стоимости всего торта. В примере с тортом пропорциональное деление может быть достигнуто путем отдачи всей ванили и 4/9 шоколада Джорджу (стоимостью 6,66), а оставшиеся 5/9 шоколада Алисе (стоимостью 5). В символах:

${\ displaystyle \ forall {i}: \ V_ {i} (X_ {i}) \ geq 1/n}$

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

• Последний уменьшатель , протокол, который может гарантировать, что n частей связаны (т.е. ни один человек не получает набор из двух или более несвязанных частей). В частности, если торт представляет собой одномерный интервал, то каждый человек получает интервал. Этот протокол дискретен и может быть разыгран по очереди. Он требует O( n ² ) действий.
• Процедура перемещения ножа Дубинса-Спаньера представляет собой непрерывную во времени версию метода Last Reducer. ^[4]
• Протокол Финка (также известный как последовательные пары или одинокий выбирающий ) — это дискретный протокол, который можно использовать для онлайн-разделения: при пропорциональном разделении для n  − 1 партнеров, когда в партию вступает новый партнер, протокол изменяет существующее разделение так, что и новый партнер, и существующие партнеры остаются с 1/ n . Недостатком является то, что каждый партнер получает большое количество разрозненных частей.
• Протокол Even–Paz , основанный на рекурсивном делении пополам торта и группы агентов, требует только O( n  log  n ) действий. Это самый быстрый возможный детерминированный протокол для пропорционального деления и самый быстрый возможный протокол для пропорционального деления, который может гарантировать, что части связаны.
• Протокол Эдмондса–Пруха — это рандомизированный протокол, требующий только O( n ) действий, но гарантирующий лишь частично пропорциональное деление (каждый партнер получает не менее 1/ an , где a — некоторая константа), и он может дать каждому партнеру набор «крошек» вместо одного связанного куска.
• Протокол раздела земель Бека может привести к пропорциональному разделу спорной территории между несколькими соседними странами таким образом, что каждая страна получит долю, которая одновременно связана и граничит с ее нынешней территорией.
• Протокол сверхпропорционального дележа Вудолла обеспечивает дележ, при котором каждый партнер получает строго больше 1/ n , при условии, что по крайней мере два партнера имеют разные мнения о стоимости хотя бы одной части.

Более подробную информацию и полные ссылки см. в разделе «Пропорциональное разрезание торта» .

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

${\displaystyle \forall i:V_{i}(X_{i})\geq w_{i}}$

Где w _i — веса, сумма которых равна 1.

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

${\displaystyle \forall i,j:\ V_{i}(X_{i})\geq V_{i}(X_{j})}$

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

Протокол «разделяй и выбирай » находит распределение, которое всегда равно EF. Если функции ценности аддитивны, то это разделение также равно PR; в противном случае пропорциональность не гарантируется.

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

Для связанных частей основные результаты таковы:

• Процедура Стромквиста с перемещающимися ножами позволяет разделить торт на троих без зависти, выдав каждому из них нож и поручив им непрерывно перемещать ножи по торту в заранее заданной манере.
• Протокол Симмонса может производить приближение к делению без зависти для n человек с произвольной точностью. Если функции ценности аддитивны, деление также будет пропорциональным. В противном случае деление все еще будет без зависти, но не обязательно пропорциональным. Алгоритм дает быстрый и практичный способ решения некоторых задач справедливого деления. ^{[5] [6]}

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

Для возможно несвязанных частей основные результаты таковы:

• Дискретная процедура Селфриджа-Конвея обеспечивает разделение без зависти для 3 человек, используя не более 5 разрезов.
• Процедура перемещения ножей Брамса-Тейлора-Цвикера обеспечивает разделение без зависти для 4 человек, используя максимум 11 разрезов.
• Реентерабельный вариант протокола Last Diminisher находит аддитивное приближение к делению без зависти за ограниченное время. В частности, для каждой константы он возвращает деление, в котором значение каждого партнера равно по крайней мере наибольшему значению минус , за время .${\displaystyle \epsilon >0}$${\displaystyle \epsilon}$${\displaystyle O(n^{2}/\epsilon)}$
• Три различных процедуры, одна от Brams и Taylor (1995) , одна от Robertson и Webb (1998) и одна от Pikhurko (2000), производят разделение без зависти для n человек. Оба алгоритма требуют конечного, но неограниченного числа разрезов.
• Процедура Азиза и Маккензи (2016) ^[7] находит разделение без зависти для n человек в ограниченном количестве запросов.

Отрицательный результат в общем случае гораздо слабее, чем в связанном случае. Все, что мы знаем, это то, что каждый алгоритм для деления без зависти должен использовать по крайней мере Ω( n ² ) запросов. Существует большой разрыв между этим результатом и сложностью выполнения лучшей известной процедуры.

Более подробную информацию и полные ссылки см . в статье «Разрезание торта без зависти» .

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

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

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

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

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

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

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

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

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

• Слабая правдивость означает, что если партнер раскрывает алгоритму свою истинную меру ценности, он гарантированно получит свою справедливую долю (например, 1/ n от стоимости всего торта в случае пропорционального дележа), независимо от того, что делают другие партнеры. Даже если все остальные партнеры объединятся с единственным намерением навредить ему, он все равно получит свою гарантированную долю. Большинство алгоритмов разрезания торта правдивы в этом смысле. ^[1]
• Сильная правдивость означает, что ни один из партнеров не может выиграть от лжи. То есть, говорить правду — это доминирующая стратегия . Большинство протоколов разрезания торта не являются строго правдивыми, но были разработаны некоторые правдивые протоколы; см. правдивое разрезание торта .

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

• Анонимность требует, чтобы при перестановке агентов и повторном выполнении процедуры каждый агент получал точно такую ​​же часть, как и при первоначальном выполнении. Это сильное условие; в настоящее время анонимная процедура известна только для 2 агентов.
• Симметрия требует, чтобы при перестановке агентов и повторном выполнении процедуры каждый агент получал то же значение , что и при первоначальном выполнении. Это слабее анонимности; в настоящее время симметричная и пропорциональная процедура известна для любого количества агентов, и она требует O( n ³ ) запросов. Симметричная и свободная от зависти процедура известна для любого количества агентов, но она занимает гораздо больше времени — она требует n ! выполнений существующей свободной от зависти процедуры.
• Аристотелевство требует, чтобы если два агента имеют одинаковую меру ценности, то они получали бы одно и то же значение. Это слабее симметрии; оно выполняется любой процедурой без зависти. Более того, аристотелевская и пропорциональная процедура известна для любого числа агентов, и она занимает O( n ³ ) запросов.

Подробную информацию и ссылки см. в разделе «Симметричное справедливое разрезание торта» .

Третье семейство процедурных требований — монотонность : когда процедура деления применяется повторно с меньшим/большим пирогом и меньшим/большим набором агентов, полезность всех агентов должна измениться в том же направлении. Подробнее см. в ресурсной монотонности .

Помимо справедливости, принято также учитывать экономическую эффективность дележа; см. эффективное разрезание торта . Существует несколько уровней эффективности:

• Более слабое понятие — эффективность Парето . Его можно легко удовлетворить, просто отдав весь торт одному человеку; задача состоит в том, чтобы удовлетворить его в сочетании со справедливостью. См. Эффективное разделение без зависти .
• Более сильным понятием является утилитарная максимальность — максимизация суммы полезностей. (UM). Когда функции ценности аддитивны, существуют UM-разделения. Интуитивно, чтобы создать UM-разделение, мы должны отдать каждый кусок торта тому, кто ценит его больше всего. В примере с тортом UM-разделение отдало бы весь шоколад Алисе, а весь ванильный — Джорджу, достигая утилитарной ценности 9 + 4 = 13. Этот процесс легко осуществить, когда функции ценности кусочно-постоянны, т. е. торт можно разделить на части так, что плотность ценности каждого куска будет постоянной для всех людей. Когда функции ценности не кусочно-постоянны, существование UM-распределений следует из классических теорем теории меры. См. Utilitarian cake-cutting .

Для n людей с аддитивными функциями значений всегда существует разделение PEEF. Это теорема Веллера . ^[9]

Если торт представляет собой одномерный интервал и каждый человек должен получить связный интервал, то справедлив следующий общий результат: если функции ценности строго монотонны (т.е. каждый человек строго предпочитает кусок всем его собственным подмножествам), то каждое деление EF также является PE. ^[10] Следовательно, протокол Симмонса в этом случае производит деление PEEF.

Если торт представляет собой одномерный круг (т. е. интервал, две конечные точки которого топологически идентифицированы), и каждый человек должен получить связанную дугу, то предыдущий результат не выполняется: деление EF не обязательно является PE. Кроме того, существуют пары (неаддитивных) функций значений, для которых не существует деления PEEF. Однако, если есть 2 агента и хотя бы один из них имеет аддитивную функцию значений, то существует деление PEEF. ^[11]

Если торт одномерный, но каждый человек может получить его несвязное подмножество, то деление EF не обязательно является PE. В этом случае для нахождения деления PEEF требуются более сложные алгоритмы.

Если функции значений аддитивны и кусочно-постоянны, то существует алгоритм, который находит PEEF-разделение. ^[12] Если функции плотности значений аддитивны и липшицевы , то их можно аппроксимировать как кусочно-постоянные функции «настолько близко, насколько мы хотим», поэтому этот алгоритм аппроксимирует PEEF-разделение «настолько близко, насколько мы хотим». ^[12]

Разделение EF не обязательно является UM. ^{[13] [14]} Один из подходов к решению этой проблемы — найти среди всех возможных разделений EF разделение EF с наивысшей утилитарной ценностью. Эта проблема была изучена для торта, который является одномерным интервалом, каждый человек может получать несвязанные куски, а функции ценности являются аддитивными. ^[15]

Рассуждение о сложности времени выполнения алгоритмов требует модели вычислений . Несколько таких моделей распространены в литературе:

• Модель запросов Робертсона-Уэбба , в которой алгоритм может задавать каждому агенту запрос одного из двух видов: «оценить данный кусок торта» или «отметить кусок торта заданным значением».
• Модель «Движущиеся ножи» — в которой алгоритм непрерывно перемещает один или несколько ножей над тортом до тех пор, пока некоторые агенты не крикнут «стоп».
• Модель прямого раскрытия – в которой все агенты раскрывают всю свою оценку механизму. Эта модель имеет смысл только тогда, когда оценки могут быть представлены кратко, например, когда они кусочно-равномерны, кусочно-постоянны или кусочно-линейны .
• Модель одновременных отчетов – в которой агенты одновременно отправляют дискретизации своих мер-значений. Дискретизация – это последовательность точек отсечения и значений частей между этими точками отсечения (например: протокол для двух агентов может потребовать, чтобы каждый агент сообщал последовательность из трех точек отсечения (0, x ,1), где значения (0, x ) и ( x ,1) равны 1/2). ^[16]

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

• Клотье, Найман и Су ^[17] изучают деление торта без зависти двумя игроками. Для двух тортов они доказывают, что распределение EF может не существовать, когда есть 2 агента и каждый торт разрезается на 2 части. Однако распределение EF существует, когда есть 2 агента и один торт разрезается на 3 части (наименее желанный кусок отбрасывается), или когда есть 3 агента и каждый торт разрезается на 2 части (один агент игнорируется; распределение EF для оставшихся двух).
• Лебер, Менье и Карбонно ^[18] доказывают для двух тортов, что распределение EF всегда существует, когда есть 3 агента и каждый торт разрезается на 5 частей (два наименее востребованных куска в каждом торте отбрасываются).
• Найман, Су и Зербиб ^[19] доказывают для k тортов, что распределение EF всегда существует, когда имеется k ( n -1)+1 агентов и каждый торт разрезан на n частей (распределение является EF для некоторого набора из n агентов).

Две связанные проблемы:

• Многослойное разрезание торта ^[20] , при котором торты располагаются «слоями», а куски одного и того же агента не должны перекрываться (например, каждый торт представляет собой время, в течение которого определенное учреждение доступно в течение дня; агент не может использовать два учреждения одновременно).
• Справедливое разделение тортов на несколько частей, ^[21] при котором агенты не хотят получить кусок от каждого торта, а, наоборот, хотят получить кусок от как можно меньшего числа тортов.

Бэй, Лу и Суксомпонг ^[22] представляют модель, в которой вместо того, чтобы делить индивидуальный кусок пирога каждому агенту, агенты должны вместе выбрать кусок пирога, который они все разделят. Это можно рассматривать как вариант выборов комитета , где кандидаты делимы. Существует континуум кандидатов, представленный действительным интервалом [0, c ], и цель состоит в том, чтобы выбрать подмножество этого интервала с общей длиной не более k , где k и c могут быть любыми действительными числами с 0 < k < c . Они обобщают понятие обоснованного представления на эту установку. Лу, Петерс, Азиз, Бэй и Суксомпонг ^[23] расширяют эти определения на установки со смешанными делимыми и неделимыми кандидатами (см. обоснованное представление ).

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

• Список книг о справедливом разделе
• Список научных работ о справедливом дележе