Справедливое деление - Equitable division

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

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

Где:

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

Сравнение с другими критериями

• Equitability (EQ) сравнивает значения разные люди, чтобы разные шт;
• Свобода от зависти (EF) сравнивает значения одинаковый человек к разные шт;
• Точное деление (EX) сравнивает значения разные люди, чтобы одинаковый шт.

Следующая таблица иллюстрирует разницу. Во всех примерах есть два партнера, Алиса и Боб. Алиса получает левую часть, а Боб - правую.

Разделение		EQ?	EF?	БЫВШИЙ?
А: 50% 50% B: 50% 50%
А: 60% 40% B: 40% 60%				(Алиса и Боб не согласны в оценке фигур).
А: 40% 60% B: 60% 40%			(Алиса и Боб завидуют доле друг друга).
А: 70% 30% B: 40% 60%		(Алиса получает больше удовольствия от своей доли, чем Боба).
А: 60% 40% B: 60% 40%			(Боб завидует Алисе).
А: 60% 40% B: 70% 30%

Обратите внимание, что в таблице всего 6 строк, потому что две комбинации невозможны: разделение EX + EF должно быть EQ, а разделение EX + EQ должно быть EF.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

• Для каждого из ${\displaystyle n!}$ возможные заказы партнеров, напишите набор ${\displaystyle n-1}$ уравнения в ${\displaystyle n-1}$ переменные: переменные ${\displaystyle n-1}$ точки отсечения, а уравнения определяют равноправие соседних партнеров. Например, если есть 3 партнера и порядок A: B: C, то две переменные ${\displaystyle x_{AB}}$ (точка разделения между A и B) и ${\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}$) возможно.

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

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

Брамс, Джонс и Кламлер изучают разделение 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. Следующие результаты существования доказаны без указания конкретного алгоритма деления:^[6]

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

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

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

Таблица результатов

Имя	Тип	# партнер	# разрезов	Характеристики
Джонс[1]	Процесс полного откровения	2	1 (оптимальный)	Эквалайзер, EF, 1-PE
Брамс-Джонс-Кламлер[3]	Процесс полного откровения	п	п−1 (оптимальный)	Эквалайзер, (п-1) -ПЭ
Остин	Движущийся нож	2	2	Эквалайзер, EF, EX
Остин	Движущийся нож	п	много	Эквалайзер
Барбанель-Брамс[4]	Процесс полного откровения	2	много	EQ, EF, PE
Cechlárová-Pillárová[5]	Процесс дискретного приближения	2	1 (оптимальный)	близкий к эквалайзеру

^[5]

Рекомендации

1. Джонс, М.А. (2002). «Справедливое, свободное от зависти и эффективное разделение торта для двух людей и его применение к делимым товарам». Математический журнал. 75 (4): 275–283. Дои:10.2307/3219163. JSTOR  3219163.
2. Стивен Дж. Брамс; Майкл а. Джонс; Кристиан Кламлер (2013). «Резка торта на N человек: идеального разделения быть не может». Американский математический ежемесячник. 120: 35. Дои:10.4169 / amer.math.monthly.120.01.035.
3. Стивен Дж. Брамс; Майкл А. Джонс; Кристиан Кламлер (2007). «Лучшие способы разрезать торт - еще раз» (PDF). Уведомления AMS.
4. Barbanel, Julius B .; Брамс, Стивен Дж. (2014). «Резка торта вдвоем: оптимальное количество разрезов». Математический интеллект. 36 (3): 23. CiteSeerX  10.1.1.361.366. Дои:10.1007 / s00283-013-9442-0.
5. Кехларова, Катарина; Пилларова, Ева (2012). «Практически равноправный алгоритм резки торта на двоих». Оптимизация. 61 (11): 1321. Дои:10.1080/02331934.2011.563306.
6. Barbanel, J. B .; Brams, S.J .; Стромквист, W. (2009). «Нарезать пирог - это не кусок торта». Американский математический ежемесячник. 116 (6): 496. CiteSeerX  10.1.1.579.5005. Дои:10.4169 / 193009709X470407.