Равноправное разрезание торта

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

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

Где:

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

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

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

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

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

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

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

Пропорционально-справедливый вариант

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Связанные части - полное откровение

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

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

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

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

Невозможность результатов

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Смотрите также

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

Ссылки

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