Русская Википедия:Беспристрастный делёж
Беспристрастный делёж (БД, Шаблон:Lang-en, EQ) — это разбиение неоднородного объекта (например, торта), в результате которого субъективные значения всех участников те же самые, то есть каждый участник одинаково доволен своей долей. Математически это означает, что для всех участников Шаблон:Mvar и Шаблон:Mvar выполняется
- <math>V_i(X_i) = V_j(X_j)</math>
где
- <math>X_i</math> является куском торта, выделенного участнику Шаблон:Mvar;
- <math>V_i</math> является функцией оценки участника Шаблон:Mvar. Это вещественнозначная функция, которая для каждого куска торта возвращает число, которое представляет величину полезности для участника Шаблон:Mvar этого куска. Обычно эти функции нормализованы так, что <math>V_i(\emptyset)=0</math> и (весь торт) <math>V_i=1</math> для любого Шаблон:Mvar.
Сравнение с другими критериями
- Беспристрастность (БД) сравнивает оценки различных людей различных кусков;
- Отсутствие зависти (ОЗ, Шаблон:Lang-en, EF) сравнивает оценки одного человека различных кусков;
- Точный делёж (ТД, Шаблон:Lang-en, EX) сравнивает оценки различных людей одних и тех же кусков.
Следующая таблица показывает разницу. Во всех примерах имеется два участника, Алиса и Боб. Алиса получает левую часть, а Боб получает правую часть.
| Делёж | БД? | ОЗ? | ТД? | |||||||
|---|---|---|---|---|---|---|---|---|---|---|
|
Шаблон:Ya | Шаблон:Ya | Шаблон:Ya | |||||||
|
Шаблон:Ya | Шаблон:Ya | Шаблон:Nx (Алиса и Боб не согласны с оценкой кусков). | |||||||
|
Шаблон:Ya | Шаблон:Nx (Алиса и Боб завидуют друг другу). |
Шаблон:Nx | |||||||
|
Шаблон:Nx (Алиса больше радуется своей доле, чем Боб своей). |
Шаблон:Ya | Шаблон:Nx | |||||||
|
Шаблон:Nx | Шаблон:Nx (Боб завидует Алисе). |
Шаблон:Ya | |||||||
|
Шаблон:Nx | Шаблон:Nx | Шаблон:Nx |
Заметим, что таблица имеет всего 6 строк, поскольку 2 комбинации невозможны — делёж ТД + ОЗ должен быть БД, а делёж ТД+БД должен быть ОЗ.
Поиск беспристрастного дележа для двух участников
Один разрез – полная информация
Когда имеются два участника, можно получить беспристрастный делёж с помощью одного разреза, но для этого требуется полное знание оценок участниковШаблон:Sfn. Предположим, что торт является отрезком [0,1]. Для каждого <math>x\in[0,1]</math> вычислим <math>u_1([0,x])</math> и <math>u_2([x,1])</math> и отметим их на одном и том же графике. Заметим, что первый график возрастает с 0 до 1, а второй график убывает с 1 до 0, так что они имеют точку пересечения. Разрезание торта в этой точке даёт беспристрастный делёж. Это разрезание имеет ряд дополнительных свойств:
- Разрезание является ОЗ, поскольку каждый участник получает значение по меньшей мере 1/2.
- Разрезание не является не ТД, поскольку значение для каждого участника может быть больше 1/2.
- Разрезание эффективно по Парето (ЭП, Шаблон:Lang-en, PE) среди всех дележей, использующих единственный разрез. Тем не менее, могут существовать более эффективные разрезания, использующие два и более разрезаШаблон:Sfn.
- Если направление торта выбрано случайным образом (то есть торт может быть перевёрнут, так что 0 становится 1, а 1 становится 0), то эта процедура снова слабо верна в следующем смысле: только предоставлением честных вероятностных мер участники могут быть уверены, что получать по меньшей мере половину тортаШаблон:Sfn.
Та же самая процедура может быть применена для дележа рутинных работ (если оценку куска брать с обратным знаком).
Пропорционально беспристрастный вариант
Процедура с полной информацией имеет вариантШаблон:Sfn, который удовлетворяет более слабым видам беспристрастности и более строгим видам точности. Процедура сначала находит медиану для каждого участника. Предположим, что медианой участника A является <math>a</math>, а медианой участника B является <math>b</math>, где <math>0<a<b<1</math>. Тогда A получает <math>[0,a]</math>, а B получает <math>[b,1]</math>. Теперь имеется остаток <math>[a,b]</math>, который делится между участниками в равных пропорциях. Так, например, если A оценивает остаток в 0,4 а B оценивает его в 0,2, то A получит вдвое больше значение от <math>[a,b]</math>, чем B. Таким образом, протокол не будет беспристрастным, но остаётся ОЗ. Он слабо честен в следующем смысле: игрок, избегающий риски, имеет стимул указывать истинную оценку, поскольку указание несоответствующей истине оценки он может получить меньшее значение.
Два разреза – движущийся нож
Процедура Остина «Движущийся нож» даёт каждому из двух участников кусок с субъективным значением в точности 1/2. Таким образом, этот делёж является БД, ТД и ОЗ. Процедура требует двух разрезов и даёт одному из участников два несвязных куска.
Много разрезов – полностью открытые предпочтения
Если разрешено делать более двух разрезов, можно добиться дележа, который будет не только БД, но также ОЗ и ЭП. Некоторые авторы называют такой делёж «совершенным»Шаблон:Sfn.
Минимальное число разрезов, требуемых для ЭП-ОЗ-БД дележа, зависит от оценок участников. В большинстве практических случаев (включая случаи, когда оценки кусочно линейны) число требуемых разрезов конечно. В этих случаях можно найти как оптимальное число разрезов, так и их точное расположение. Алгоритм требует полного знания оценок участниковШаблон:Sfn.
Время работы алгоритма
Все представленные выше процедуры непрерывны — вторая процедура требует, чтобы нож двигался непрерывно, другие требуют непрерывности графиков двух мер оценок. Таким образом, эти процедуры нельзя завершить за конечное число дискретных шагов.
Это свойство бесконечности является характеристикой задач дележа, требующих точных результатов (см. статью Точный делёж: невозможность).
Один разрез – почти беспристрастный делёж
Почти беспристрастный делёж — это делёж, в котором оценки каждого игрока отличаются не более чем на <math>\epsilon</math> для любого фиксированного <math>\epsilon>0</math>. Почти беспристрастный делёж для двух игроков может быть найден за конечное время для условия единичного разрезаШаблон:Sfn.
Поиск беспристрастного дележа для трёх и более участников
Процедура «движущийся нож»
Процедура Остина может быть распространена на n участников. Процедура даёт каждому участнику с субъективной оценкой значения в точности <math>1/n</math>. Этот делёж является БД, но не обязательно ТД, ОЗ, или ЭП (поскольку некоторые участники могут оценить долю, передаваемые другим участникам больше <math>1/n</math>).
Связные куски – полностью открытые предпочтения
Процедура Джонсона с полностью открытыми предпочтениями может быть расширена на <math>n</math> участников следующим образомШаблон:Sfn:
- Для каждого из <math>n!</math> упорядочений участников выпишем множество из <math>n-1</math> уравнений с <math>n-1</math> переменными — переменными являются <math>n-1</math> точками разреза, а уравнения определяют беспристрастность для соседних участников. например, если имеется 3 участника в порядке A:B:C, то имеется две переменные <math>x_{AB}</math> (точка разреза для A и B) и <math>x_{BC}</math>, а двумя уравнениями будут <math>V_A(0,x_{AB})=V_B(x_{AB},x_{BC})</math> и <math>V_B(x_{AB},x_{BC})=V_C(x_{BC},1)</math>. Эти уравнения имеют по меньшей мере одно решение, в котором все участники имеют одно и то же значение.
- Из всех <math>n!</math> упорядочений выберем упорядочение, в котором (одинаковое) для всех участников значение было наибольшим.
Заметим, что максимальное беспристрастное значение должно быть не менее <math>1/n</math>, поскольку мы уже знаем, что возможен пропорциональный делёж (дающий каждому участнику по меньшей мере <math>1/n</math>).
Если меры оценок участников абсолютно непрерывны относительно друг друга, то любая попытка увеличить значение участника должно уменьшать значение другого участника. Это означает, что это решение обладает свойством ЭП среди всех решений со связными кусками.
Невозможность
Брамс, Джонс и Кламлер изучали делёж, который и БД, и ЭП, и ОЗ (они назвали такой делёж «совершенным»).
Сначала они доказали, что для 3 участников, если они должны получить связные куски, БД+ОЗ разрезание может не существоватьШаблон:Sfn. Они сделали это путём описания 3 конкретных мер оценок для одномерного торта, для которых любой БД делёж с 2 разрезами не будет ОЗ.
Затем они доказали, что для 3 и более участников ЭП+ОЗ+БД делёж может не существовать даже при разрешении несвязных кусковШаблон:Sfn. Они сделали это, описав 3 конкретные меры оценок для одномерного торта со следующими свойствами:
- Для 2 разрезов любое БД разрезание не будет ни ОЗ, ни ЭП (но существуют разрезания, которые ОЗ и 2-ЭП или БД и 2-ЭП).
- Для 3 разрезов любое БД разрезание не будет ЭП (но существуют разрезания БД+ОЗ).
- Для 4 разрезов любое БД разрезание не будет ОЗ (но существуют разрезания БД+ЭП).
Делёж пирога
Пирог — это торт в форме одномерной окружности (см. задачу справедливого разрезания пирога).
Барбанель, Брамс и Стромквист изучали существование разрезания пирога, которое и БД, и ОЗ. Следующие результаты были доказаны без приведения конкретного алгоритма дележаШаблон:Sfn:
- Для двух участников всегда существует беспристрастный делёж пирога, в котором отсутствует зависть. Если меры оценок предпочтений участников абсолютно непрерывны относительно друг друга (то есть любой кусок, имеющий положительную ценность для одного участника, имеет положительную ценность и для других участников), существует распределение торта без зависти, которое и беспристрастно, и недоминируемо.
- Для 3 и более участников может оказаться невозможным найти беспристрастное распределение торта, в котором отсутствует зависть. Однако всегда существует делёж, который и беспристрастен, и недоминируем.
Делёж делимых объектов
Процедура «подстраивающийся победитель» вычисляет беспристрастный свободный от зависти эффективный по Парето делёж делимых объектов между двумя участниками.
Итоговая таблица
| Название | Тип | Число участников |
число разрезов |
Свойства |
|---|---|---|---|---|
| Алгоритм ДжонсаШаблон:Sfn | Полностью открытые предпочтения |
2 | 1 (оптимально) | БД, ОЗ, 1-ЭП |
| Процедура Брамса — Джонса — КламлераШаблон:Sfn |
Полностью открытые предпочтения |
n | n−1 (оптимально) | БД, (n−1)-ЭП |
| Процедура Остина | Процедура «Движущийся нож» |
2 | 2 | БД, ОЗ, ТД |
| Процедура Остина | Процедура «Движущийся нож» |
n | много | БД |
| Процедура Барбанеля — БрамсаШаблон:Sfn |
Полностью открытые предпочтения |
2 | много | БД, ОЗ, ЭП |
| Процедура Чекларовой — ПилларовойШаблон:Sfn |
Дискретная аппроксимация |
2 | 1 (оптимально) | почти БД |
Примечания
Литература
