Беспристрастный делёж

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

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

где

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

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

Беспристрастность (БД) сравнивает оценки различных людей различных кусков;
Отсутствие зависти (ОЗ, англ. Envy-freeness, EF) сравнивает оценки одного человека различных кусков;
Точный делёж (ТД, англ. Exact division, EX) сравнивает оценки различных людей одних и тех же кусков.

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

Делёж

БД?

ОЗ?

ТД?

A:	50%	50%
B:	50%	50%

A:	60%	40%
B:	40%	60%

(Алиса и Боб не согласны с оценкой кусков).

A:	40%	60%
B:	60%	40%

(Алиса и Боб завидуют друг другу).

A:	70%	30%
B:	40%	60%

(Алиса больше радуется своей доле, чем Боб своей).

A:	60%	40%
B:	60%	40%

(Боб завидует Алисе).

A:	60%	40%
B:	70%	30%

Заметим, что таблица имеет всего 6 строк, поскольку 2 комбинации невозможны — делёж ТД + ОЗ должен быть БД, а делёж ТД+БД должен быть ОЗ.

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

Один разрез – полная информация

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

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

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

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

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

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

Процедура Остина «Движущийся нож» даёт каждому из двух участников кусок с субъективным значением в точности 1/2. Таким образом, этот делёж является БД, ТД и ОЗ. Процедура требует двух разрезов и даёт одному из участников два несвязных куска.

Много разрезов – полностью открытые предпочтения

Если разрешено делать более двух разрезов, можно добиться дележа, который будет не только БД, но также ОЗ и ЭП. Некоторые авторы называют такой делёж «совершенным»^[4].

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

Время работы алгоритма

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

Это свойство бесконечности является характеристикой задач дележа, требующих точных результатов (см. статью Точный делёж: невозможность).

Один разрез – почти беспристрастный делёж

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

Поиск беспристрастного дележа для трёх и более участников

Процедура «движущийся нож»

Процедура Остина может быть распространена на n участников. Процедура даёт каждому участнику с субъективной оценкой значения в точности $1/n$ . Этот делёж является БД, но не обязательно ТД, ОЗ, или ЭП (поскольку некоторые участники могут оценить долю, передаваемые другим участникам больше $1/n$ ).

Связные куски – полностью открытые предпочтения

Процедура Джонсона с полностью открытыми предпочтениями может быть расширена на $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$ ).

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

Невозможность

Брамс, Джонс и Кламлер изучали делёж, который и БД, и ЭП, и ОЗ (они назвали такой делёж «совершенным»).

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

Затем они доказали, что для 3 и более участников ЭП+ОЗ+БД делёж может не существовать даже при разрешении несвязных кусков^[2]. Они сделали это, описав 3 конкретные меры оценок для одномерного торта со следующими свойствами:

Для 2 разрезов любое БД разрезание не будет ни ОЗ, ни ЭП (но существуют разрезания, которые ОЗ и 2-ЭП или БД и 2-ЭП).
Для 3 разрезов любое БД разрезание не будет ЭП (но существуют разрезания БД+ОЗ).
Для 4 разрезов любое БД разрезание не будет ОЗ (но существуют разрезания БД+ЭП).

Делёж пирога

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

Барбанель, Брамс и Стромквист изучали существование разрезания пирога, которое и БД, и ОЗ. Следующие результаты были доказаны без приведения конкретного алгоритма дележа^[6]:

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

Делёж делимых объектов

Процедура «подстраивающийся победитель» вычисляет беспристрастный свободный от зависти эффективный по Парето делёж делимых объектов между двумя участниками.

Итоговая таблица

Название	Тип	Число участников	число разрезов	Свойства
Алгоритм Джонса^[1]	Полностью открытые предпочтения	2	1 (оптимально)	БД, ОЗ, 1-ЭП
Процедура Брамса — Джонса — Кламлера^[3]	Полностью открытые предпочтения	n	n−1 (оптимально)	БД, (n−1)-ЭП
Процедура Остина	Процедура «Движущийся нож»	2	2	БД, ОЗ, ТД
Процедура Остина	Процедура «Движущийся нож»	n	много	БД
Процедура Барбанеля — Брамса^[4]	Полностью открытые предпочтения	2	много	БД, ОЗ, ЭП
Процедура Чекларовой — Пилларовой^[5]	Дискретная аппроксимация	2	1 (оптимально)	почти БД

Примечания

↑ ¹ ² ³ Jones, 2002, с. 275–283.
↑ ¹ ² Brams, Jones, Klamler, 2013, с. 35.
↑ ¹ ² ³ ⁴ Brams, Jones, Klamler, 2007.
↑ ¹ ² ³ Barbanel, Brams, 2014, с. 23.
↑ ¹ ² Cechlárová, Pillárová, 2012, с. 1321.
↑ Barbanel, Brams, Stromquist, 2009, с. 496.

Литература

Jones M. A. Equitable, Envy-Free, and Efficient Cake Cutting for Two People and Its Application to Divisible Goods // Mathematics Magazine. — 2002. — Т. 75, вып. 4. — С. 275–283. — doi:10.2307/3219163. — JSTOR 3219163.
Steven J. Brams, Michael A. Jones, Christian Klamler. Better Ways to Cut a Cake – Revisited // Notices of the AMS. — 2007.
Julius B. Barbanel, Steven J. Brams. Two-Person Cake Cutting: The Optimal Number of Cuts // The Mathematical Intelligencer. — 2014. — Т. 36, вып. 3. — doi:10.1007/s00283-013-9442-0.
Katarína Cechlárová, Eva Pillárová. A near equitable 2-person cake cutting algorithm // Optimization. — 2012. — Т. 61, вып. 11. — doi:10.1080/02331934.2011.563306.
Barbanel J. B., Brams S. J., Stromquist W. Cutting a Pie is Not a Piece of Cake // American Mathematical Monthly. — 2009. — Т. 116, вып. 6. — doi:10.4169/193009709X470407.
Steven J. Brams, Michael A. Jones, Christian Klamler. N-Person Cake-Cutting: There May Be No Perfect Division // The American Mathematical Monthly. — 2013. — Т. 120. — doi:10.4169/amer.math.monthly.120.01.035.

[_d40787f199eaa164-1] ¹ ² ³ Jones, 2002, с. 275–283.

[_8a5afc8a9f33ef5b-2] ¹ ² Brams, Jones, Klamler, 2013, с. 35.

[_b0c5fa46cfe801a0-3] ¹ ² ³ ⁴ Brams, Jones, Klamler, 2007.

[_22a153fa950b6589-4] ¹ ² ³ Barbanel, Brams, 2014, с. 23.

[_2e27f7fe471ea309-5] ¹ ² Cechlárová, Pillárová, 2012, с. 1321.

[_d7d89a11799c6542-6] Barbanel, Brams, Stromquist, 2009, с. 496.

[1]

[2]

[3]

[4]

[5]

[6]