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

Справедливое разрезание пирога (EQ) — это разновидность проблемы справедливого разрезания торта , в которой критерием справедливости является справедливость . Это распределение торта, при котором субъективная ценность всех партнеров одинакова, т. е. каждый партнер одинаково доволен своей долей. Математически это означает, что для всех партнеров $i$ и $j$ :

V_{i}(X_{i})=V_{j}(X_{j})

Где:

$X_{i}$ кусок пирога, выделенный партнеру $i$ ;
$V_{i}$ — мера ценности партнера $i$ . Это функция с действительным знаком, которая для каждого куска пирога возвращает число, обозначающее полезность партнера $i$ от этого куска. Обычно эти функции нормализуются так, что $V_{i}(\emptyset )=0$ и $V_{i}(EntireCake)=1$ для каждого $я$ .

См. страницу о справедливости , где приведены примеры и сравнение с другими критериями справедливости.

Поиск справедливого разрезания торта для двух партнеров

Один разрез - полное откровение

При наличии двух партнеров можно получить подразделение EQ одним разрезом, но для этого необходимо полное знание оценок партнеров. ^[1] Предположим, что торт — это интервал [0,1]. Для каждого $x\in [0,1]$ , рассчитать $u_{1}([0,x])$ и $u_{2}([x,1])$ и постройте их на одном графике. Обратите внимание, что первый график увеличивается от 0 до 1, а второй график уменьшается от 1 до 0, поэтому у них есть точка пересечения. Разрезание торта в этот момент приводит к справедливому разделу. Это подразделение имеет несколько дополнительных свойств:

Это EF, поскольку каждый партнер получает значение не менее 1/2.
Это не EX, так как стоимость на одного партнера может быть больше 1/2.
Оно является эффективным по Парето (PE) среди всех подразделений, использующих один разрез. Однако могут существовать более эффективные подразделения, в которых используются два или более сокращений. ^[2]
Если направление торта выбрано случайным образом (т. е. его можно перевернуть так, что 0 станет 1, а 1 станет 0), то эта процедура также слабо правдива в следующем смысле: только представив искренние меры вероятности, партнер может убедитесь, что он получил хотя бы половину торта. ^[1]

Ту же процедуру можно использовать и для разделения обязанностей (с отрицательной полезностью).

Вариант пропорционального равенства

Процедура полного раскрытия имеет вариант ^[3] который удовлетворяет более слабому виду справедливости и более сильному виду правдивости. Процедура сначала находит средние точки каждого партнера. Предположим, медианная точка партнера А равна $a$ и партнера B $b$ , с $0<a<b<1$ . Тогда А получает $[0,a]$ и Б получает $[b,1]$ . Теперь есть избыток - $[a,b]$ . Излишек делится между партнерами в равных пропорциях . Так, например, если А оценивает излишек как 0,4, а Б оценивает излишек как 0,2, то А получит в два раза больше стоимости от $[a,b]$ чем B. Таким образом, этот протокол не является справедливым, но это все равно EF. Это слабо правдиво в следующем смысле: у игрока, не склонного к риску, есть стимул сообщать о своей истинной оценке, потому что сообщение о ложной оценке может оставить его с меньшей стоимостью.

Два разреза - движущийся нож

Процедура Остина с подвижным ножом дает каждому из двух партнеров фигуру с субъективной ценностью ровно 1/2. Таким образом, разделение будет EQ, EX и EF. Он требует 2 разрезов и дает одному из партнеров две несвязные фигуры.

Много сокращений - полное откровение

Если разрешено более двух сокращений, можно добиться разделения не только EQ, но также EF и PE . Некоторые авторы называют такое деление «совершенным». ^[4]

Минимальное количество сокращений, необходимое для разделения PE-EF-EQ, зависит от оценок партнеров. В большинстве практических случаев (включая все случаи, когда оценки кусочно-линейны) число требуемых разрезов конечно. В этих случаях можно найти как оптимальное количество разрезов, так и их точное расположение. Алгоритм требует полного знания оценок партнеров. ^[4]

Время выполнения

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

Это свойство бесконечности характерно для задач деления, требующих точного результата. См. Точное деление#Невозможность .

Одно сокращение – почти равное разделение

Почти равноправный раздел — это раздел, при котором ценности партнеров различаются не более чем на $\epsilon$ , для любого заданного $\epsilon >0$ . Почти равноправный раздел между двумя партнерами может быть найден за конечное время и одним разрезом. ^[5]

Поиск справедливого раздела между тремя и более партнерами

Процедуры перемещения ножа

Процедуру Остина можно распространить на n партнеров . Он дает каждому партнеру кусок с субъективной ценностью ровно $1/n$ . Это деление EQ, но не обязательно EX, EF или PE (поскольку некоторые партнеры могут оценить долю, предоставленную другим партнерам, как более чем $1/n$ ).

Существует еще одна процедура, использующая n -1 движущихся ножей, которую можно использовать для нахождения связного справедливого распределения для любого порядка агентов. ^[6]^{: Раздел 6.2}

Соединённые части – полное откровение

Полную процедуру раскрытия Джонса можно распространить на $n$ партнеров следующим образом: ^[3]

Для каждого из $n!$ возможные заказы партнеров, напишите набор $n-1$ уравнения в $n-1$ переменные: переменные — это $n-1$ точки пересечения, и уравнения определяют справедливость для соседних партнеров. Например, если имеется 3 партнера и порядок A:B:C, то две переменные равны $x_{AB}$ (точка разделения между A и B) и $x_{BC}$ , и эти два уравнения имеют вид $V_{A}(0,x_{AB})=V_{B}(x_{AB},x_{BC})$ и $V_{B}(x_{AB},x_{BC})=V_{C}(x_{BC},1)$ . Эти уравнения имеют по крайней мере одно решение, в котором все партнеры имеют одинаковое значение.
Из всех $n!$ заказов выберите порядок, при котором (равная) стоимость всех партнеров является наибольшей.

Обратите внимание, что максимальная справедливая стоимость должна быть не менее $1/n$ , поскольку мы уже знаем, что пропорциональное деление (предоставление каждому партнеру не менее $1/n$ ) возможно.

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

Результаты невозможности

Брэмс, Джонс и Кламлер изучают деление EQ, PE и EF (они называют такое деление «идеальным»).

Сначала они доказывают, что для трех партнеров, которым необходимо собрать связанные части, разделения EQ+EF может не существовать. ^[3] Они делают это, описывая три конкретных показателя стоимости на одномерном торте, в котором каждое распределение EQ с двумя разрезами не является EF.

Затем они доказывают, что для 3 и более партнеров разделение PE+EF+EQ может не существовать даже при наличии несвязных частей. ^[2] Они делают это, описывая три конкретные меры стоимости на одномерном торте со следующими свойствами:

При использовании двух сокращений каждое распределение EQ не является ни EF, ни PE (но есть распределения, которые представляют собой EF и 2-PE или EQ и 2-PE).
При 3 сокращениях каждое распределение эквалайзера не является PE (но есть распределение EQ+EF).
При 4 сокращениях каждое распределение эквалайзера не является EF (но есть распределение EQ+PE).

Нарезка пирога

Пирог — это торт в форме одномерного круга (см. ярмарочная нарезка пирога ).

Барбанель, Брамс и Стромквист изучают существование частей пирога, которыми являются EQ и EF. Следующие результаты существования доказываются без указания конкретного алгоритма деления: ^[7]

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

Делимые товары

Скорректированная процедура победителя рассчитывает справедливое, свободное от зависти и эффективное разделение набора делимых товаров между двумя партнерами.

Сложность запроса

Справедливое распределение торта невозможно найти с использованием конечного протокола в модели запроса Робертсона-Уэбба даже для двух агентов. ^[8] Более того, для любого ε > 0:

Для связного ε-справедливого разрезания торта требуется как минимум Ω(log ε ⁻¹) запросы. ^[9] Для двух агентов O(log ε ⁻¹) протокол существует. ^[5] Для 3 или более агентов наиболее известный протокол требует O( n (log n + log ε ⁻¹)) запросы. ^[10]
Даже без связности для ε-справедливого разрезания торта требуется как минимум Ω(log ε ⁻¹ / журнал журнал е ⁻¹ ) запросы. ^[8]

Свойства правил максимально справедливого распределения

Правило максимально справедливого деления — это правило, которое выбирает среди всех справедливых распределений торта то, при котором общая ценность агентов максимальна. Имеет два варианта:

Правило абсолютной справедливости уравнивает абсолютные (не нормализованные) значения;
Правило относительной справедливости уравнивает относительные (нормализованные) значения.

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

Правило абсолютной справедливости является слабо Парето-оптимальным и монотонным по ресурсам , но не пропорциональным .
Правило относительной справедливости является слабо Парето-оптимальным и пропорциональным, но не монотонным по ресурсам. ^[6]

Сводная таблица

Имя	Тип	# партнёров	# сокращений	Характеристики
Джонс ^[1]	Процесс полного раскрытия	2	1 (оптимально)	Эквалайзер, EF, 1-PE
Брамс-Джонс-Кламлер ^[3]	Процесс полного раскрытия	н	п -1 (оптимально)	EQ, ( n −1)-PE
Остин	Процесс движущегося ножа	2	2	Эквалайзер, EF, EX
Остин	Процесс движущегося ножа	н	много	эквалайзер
^[6]^{: Раздел 6.2}	Процесс движущегося ножа	н	п -1 (оптимально)	ЭКВАЛАЛИЗАЦИЯ, ПРОП, WPE
Барбанель-Брамс ^[4]	Процесс полного раскрытия	2	много	Эквалайзер, EF, PE
Чефларова-Пилларова ^[5]	Дискретная аппроксимация	2	1 (оптимально)	почти эквалайзер

См. также

Эгалитарное разрезание пирога – распределение, максимизирующее наименьшую полезность агента. Часто эгалитарное распределение совпадает со справедливым распределением, поскольку, если полезности различны, меньшую полезность можно улучшить, отдав часть пирога от агента с большей полезностью.

Ссылки

^ Jump up to: ^а ^б ^с Джонс, Массачусетс (2002). «Справедливый, свободный от зависти и эффективный разрез торта для двух человек и его применение к делимым товарам». Журнал «Математика» . 75 (4): 275–283. дои : 10.2307/3219163 . JSTOR 3219163 .
^ Jump up to: ^а ^б Стивен Дж. Брамс; Майкл а. Джонс; Кристиан Кламлер (2013). «Разрезание торта N-человеком: идеального разделения не может быть». Американский математический ежемесячник . 120 : 35. doi : 10.4169/amer.math.monthly.120.01.035 . S2CID 7929917 .
^ Jump up to: ^а ^б ^с ^д Стивен Дж. Брэмс; Майкл А. Джонс; Кристиан Кламлер (2007). «Лучшие способы разрезать торт — еще раз» (PDF) . Уведомления АМС .
^ Jump up to: ^а ^б ^с Барбанель, Юлиус Б.; Брамс, Стивен Дж. (2014). «Разрезка торта вдвоем: оптимальное количество разрезов». Математический интеллект . 36 (3): 23. CiteSeerX 10.1.1.361.366 . дои : 10.1007/s00283-013-9442-0 . S2CID 189867346 .
^ Jump up to: ^а ^б ^с Чефларова, Катарина; Пилларова, Ева (2012). «Почти равноправный алгоритм разрезания торта для двух человек». Оптимизация . 61 (11): 1321. doi : 10.1080/02331934.2011.563306 . S2CID 120300612 .
^ Jump up to: ^а ^б ^с Сегал-Халеви, Эрель; Шиклай, Балаж Р. (01 сентября 2018 г.). «Ресурсно-монотонность и популяционно-монотонность в связанном разрезании торта» . Математические социальные науки . 95 : 19–30. arXiv : 1703.08928 . doi : 10.1016/j.mathsocsci.2018.07.001 . ISSN 0165-4896 . S2CID 16282641 .
^ Барбанель, Дж.Б.; Брамс, С.Дж.; Стромквист, В. (2009). «Разрезать пирог – непростая задача». Американский математический ежемесячник . 116 (6): 496. CiteSeerX 10.1.1.579.5005 . дои : 10.4169/193009709X470407 .
^ Jump up to: ^а ^б Прокачча, Ариэль Д.; Ван, Цзюньсин (20 июня 2017 г.). «Нижняя граница справедливого разрезания торта» . Материалы конференции ACM по экономике и вычислениям 2017 года . ЕС '17. Кембридж, Массачусетс, США: Ассоциация вычислительной техники. стр. 479–495. дои : 10.1145/3033274.3085107 . ISBN 978-1-4503-4527-9 . S2CID 9834718 .
^ Брынзей, Симина; Нисан, Ноам (13 июля 2018 г.). «Сложность запроса при разрезании торта». arXiv : 1705.02946 [ cs.GT ].
^ Чефларова, Катарина; Пилларова, Ева (1 ноября 2012 г.). «О вычислимости справедливых делений» . Дискретная оптимизация . 9 (4): 249–257. дои : 10.1016/j.disopt.2012.08.001 . ISSN 1572-5286 . {{cite journal}}: CS1 maint: несколько имен: список авторов ( ссылка )

[jones2002-1] Jump up to: ^а ^б ^с Джонс, Массачусетс (2002). «Справедливый, свободный от зависти и эффективный разрез торта для двух человек и его применение к делимым товарам». Журнал «Математика» . 75 (4): 275–283. дои : 10.2307/3219163 . JSTOR 3219163 .

[bjk2011-2] Jump up to: ^а ^б Стивен Дж. Брамс; Майкл а. Джонс; Кристиан Кламлер (2013). «Разрезание торта N-человеком: идеального разделения не может быть». Американский математический ежемесячник . 120 : 35. doi : 10.4169/amer.math.monthly.120.01.035 . S2CID 7929917 .

[bjk07-3] Jump up to: ^а ^б ^с ^д Стивен Дж. Брэмс; Майкл А. Джонс; Кристиан Кламлер (2007). «Лучшие способы разрезать торт — еще раз» (PDF) . Уведомления АМС .

[bb2014-4] Jump up to: ^а ^б ^с Барбанель, Юлиус Б.; Брамс, Стивен Дж. (2014). «Разрезка торта вдвоем: оптимальное количество разрезов». Математический интеллект . 36 (3): 23. CiteSeerX 10.1.1.361.366 . дои : 10.1007/s00283-013-9442-0 . S2CID 189867346 .

[cp11-5] Jump up to: ^а ^б ^с Чефларова, Катарина; Пилларова, Ева (2012). «Почти равноправный алгоритм разрезания торта для двух человек». Оптимизация . 61 (11): 1321. doi : 10.1080/02331934.2011.563306 . S2CID 120300612 .

[:3-6] Jump up to: ^а ^б ^с Сегал-Халеви, Эрель; Шиклай, Балаж Р. (01 сентября 2018 г.). «Ресурсно-монотонность и популяционно-монотонность в связанном разрезании торта» . Математические социальные науки . 95 : 19–30. arXiv : 1703.08928 . doi : 10.1016/j.mathsocsci.2018.07.001 . ISSN 0165-4896 . S2CID 16282641 .

[bbs09-7] Барбанель, Дж.Б.; Брамс, С.Дж.; Стромквист, В. (2009). «Разрезать пирог – непростая задача». Американский математический ежемесячник . 116 (6): 496. CiteSeerX 10.1.1.579.5005 . дои : 10.4169/193009709X470407 .

[:2-8] Jump up to: ^а ^б Прокачча, Ариэль Д.; Ван, Цзюньсин (20 июня 2017 г.). «Нижняя граница справедливого разрезания торта» . Материалы конференции ACM по экономике и вычислениям 2017 года . ЕС '17. Кембридж, Массачусетс, США: Ассоциация вычислительной техники. стр. 479–495. дои : 10.1145/3033274.3085107 . ISBN 978-1-4503-4527-9 . S2CID 9834718 .

[:0-9] Брынзей, Симина; Нисан, Ноам (13 июля 2018 г.). «Сложность запроса при разрезании торта». arXiv : 1705.02946 [ cs.GT ].

[:1-10] Чефларова, Катарина; Пилларова, Ева (1 ноября 2012 г.). «О вычислимости справедливых делений» . Дискретная оптимизация . 9 (4): 249–257. дои : 10.1016/j.disopt.2012.08.001 . ISSN 1572-5286 . {{cite journal}}: CS1 maint: несколько имен: список авторов ( ссылка )

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]