Завистливое распределение объектов

Завистливое распределение объектов (без зависти, БЗ, англ. Envy-free, EF распределение^[1]) — это задача справедливого распределения объектов, в которой критерием справедливости служит отсутствие зависти в получившемся распределении — каждый агент должен получить набор объектов, ценность которых (как он считает) не меньше долей, полученных другими агентами^[2].

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

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

Обычно для людей проще упорядочить индивидуальные объекты, чем упорядочить наборы объектов. Предположим, что все агенты имеют адаптивные предпочтения^[англ.], тогда имеется возможность поднять упорядочение объектов до частичного упорядочения наборов. Например, если объекты упорядочены w>x>y>z, отсюда следует, что {w, x}>{y, z} и {w, y}>{x, z}, но не следуют какие-либо предпочтения между {w, z} и {x, y}, между {x} и {y, z}, и так далее.

Если дано упорядочение объектов:

• Распределение заведомо не будет иметь зависть, (заведомо без зависти, ЗБЗ, англ. necessarily envy-free, NEF), если оно не имеет зависти для всех адаптивных упорядочений наборов, согласующихся с упорядочением объектов;
• Распределение возможно не имеет зависти (возможно без зависти, ВБЗ, англ. possibly envy-free, PEF), если оно не имеет зависти для по меньшей мере одного адаптивного упорядочения наборов, согласующегося с упорядочением объектов;
• Распределение является заведомо оптимальным по Парето (ЗОП, англ. necessarily Pareto-optimal, NPE), если оно оптимально по Парето для всех адаптивных упорядочений наборов, согласующихся с упорядочением объектов;
• Распределение возможно оптимально по Парето (ВОП, англ. possibly Pareto-optimal, PPE), если оно оптимально по Парето для по меньшей мере одного адаптивного упорядочения наборов, согласующегося с упорядочением объектов.

Бувре, Эндрисс и Ленг^[3] изучали алгоритмические вопросы поиска ЗБЗ/ВБЗ распределения с дополнительным условием эффективности, частичности, полноты, ЗОП или ВОП. В общем виде случай ВБЗ вычислительно более прост, а случай ЗБЗ более труден.

Пустое распределение всегда БЗ, но если мы хотим потребовать эффективность вдобавок к БЗ, решение задачи становится вычислительно сложным^[4]:

• Решение, существует ли полное БЗ распределение, является NP-полной задачей. Это верно даже когда имеется только два агента и даже когда функции полезности аддитивны и идентичны, поскольку в этом случае поиск БЗ распределения эквивалентен решению задачи разбиения множества чисел^[5].
• Решение, существует ли эффективное по Парето БЗ распределение, является более трудной задачей, чем NP — она ${\displaystyle \Sigma _{2}^{\textrm {P}}}$-полна даже с дихотомическими функциями предпочтений^[6] и даже с аддитивными функциями полезности^[7].

Некоторые процедуры находят распределение, которое не имеет зависти за исключением одного объекта (БЗ1) — для любых двух агентов A и B существует один объект, при удалении которого из набора агента B агент A уже не будет завидовать агенту B^[8].

Если все агенты имеют слабо аддитивные полезности, следующий протокол (который похож на круговое планирование) даёт полностью БЗ1 распределение:

1. Упорядочиваем агентов произвольным образом.
2. Пока есть нераспределённые объекты
   • Позволяем агентам с номерами от 1 до ${\displaystyle n}$ выбрать объект.

Доказательство^[9]: Для любого агента ${\displaystyle i}$ делим выборы, сделанные агентами на подпоследовательности — первая подпоследовательность начинается с агента 1 и заканчивается агентом ${\displaystyle i-1}$. Последняя подпоследовательность начинается с ${\displaystyle i}$ и заканчивается на ${\displaystyle i-1}$. Во второй последовательности агент ${\displaystyle i}$ выбирает первым, так что он выбирает лучший объект, а потому не завидует другому агенту. Агент ${\displaystyle i}$ может завидовать только одному из агентов ${\displaystyle 1,...,i-1}$, и любая зависть получается только из объекта, который был выбран в первой подпоследовательности. Если этот объект убрать, агент ${\displaystyle i}$ не будет завидовать.

Протокол кругового планирования требует слабой аддитивности, поскольку в нём требуется, чтобы каждый агент выбирал «лучший объект» без знания, какие объекты будут выбраны им впоследствии. Другими словами, это предполагает, что объекты являются независимыми товарами.

Процедура циклов зависти возвращает полностью БЗ1 распределение для произвольных отношений предпочтений. Единственным требованием является возможность упорядочить агентами свои наборы объектов.

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

Механизм приблизительного конкурентного равновесия при равных доходах^[англ.] (П-КРРД, англ.  Approximate Competitive Equilibrium from Equal Incomes, A-CEEI) возвращает частичное БЗ1 распределение для произвольных предпочтений. Единственным требованием является возможность агента упорядочить наборы объектов.

Небольшое число объектов может остаться нераспределённым. Распределение эффективно по Парето в отношении распределённых объектов. Более того, П-КРРД механизм является приблизительно стратегически неуязвимым, если число агентов большое.

Алгоритм максимального по Нэшу благополучия (МНБ, англ. The Maximum-Nash-Welfare, MNW) выбирает полное распределение, которое максимизирует произведение полезностей. Он требует, чтобы каждый агент обеспечил численную оценку каждого объекта, и предполагает, что полезности для агентов аддитивны. Результирующим распределением будет также БЗ1 и эффективное по Парето^[9].

Если предпочтения агентов не аддитивны, МНБ решение не обязательно БЗ1, но если предпочтения агентов по меньшей мере субмодулярны^[англ.], МНБ решение удовлетворяет более слабому свойству, называемому предельным распределением без зависти за исключением 1 объекта (ПБЗ1, англ. Marginal-Envy-Freeness except-1-item, MEF1).

Имеется альтернативный критерий, называемый Отсутствие Зависти за исключением самого Дешёвого (БЗд) — для любых двух агентов A и B. Если мы удалим из набора объектов агента B любой объект, то A не будет завидовать B. БЗд строго сильнее, чем БЗ1. Но, пока неизвестно, всегда ли существуют БЗд распределения^[9].

Если дано распределение X, определим отношение зависти i к j (EnvyRatio) как:

${\displaystyle EnvyRatio(X,i,j):=\max(1,{u_{i}(X_{j}) \over u_{i}(X_{i})})}$

так что отношение равно 1, если i не завидует j, и больше 1, если i завидует j. Определим отношение зависти распределения как:

${\displaystyle EnvyRatio(X):=\max _{i,j}(EnvyRatio(X,i,j)}$

Задача минимизации отношения зависти — это задача нахождения распределения X с наименьшим отношением зависти.

При предпочтениях общего вида любой детерминированный алгоритм, который вычисляет распределение с минимальным отношением зависти требует количество запросов, в худшем случае экспоненциально зависящее от числа объектов^[5].

При аддитивных и идентичных оценках предпочтений^[5]:

• Следующий жадный алгоритм находит распределение, отношение зависти которого не более чем в 1,4 раз превосходит минимум^[10];
  1. Упорядочиваем объекты в порядке убывания ценности;
  2. Пока имеются нераспределённые объекты, отдаём очередной объект агенту с минимальным суммарным значением;
• Существует PTAS схема минимизации отношения зависти. Более того, если число игроков постоянно, существует FPTAS схема.

При аддитивных и различных оценках предпочтений^[11]

• Если число агентов входит во входные данные, то за полиномиальное время невозможно получить коэффициент аппроксимации лучше 1,5. Если только не P=NP.
• Если число агентов постоянно, существует FPTAS схема.
• Если число агентов равно числу объектов, существует алгоритм распределения полиномиального времени.

AL-процедура находит БЗ распределение для двух агентов. Она может отбросить некоторые из объектов, но конечное распределение эффективно по Парето в том смысле, что никакое другое БЗ распределение не лучше для одного и слабо лучше для другого. AL процедура требует упорядочить по ценности отдельные объекты только от агентов. Процедура предполагает, что агенты имеют адаптивные предпочтения^[англ.], и даёт распределение, в котором заведомо отсутствует зависть (заведомо без зависти, ЗБЗ).

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

Если агенты имеют аддитивные функции полезности, которые взяты из распределений вероятности, удовлетворяющих некоторым критериям, и число объектов достаточно велико по отношению к числу агентов, то БЗ распределение существует с высокой вероятностью. В частности^[12]

• Если число объектов достаточно велико, ${\displaystyle m=\Omega (n\log n)}$, то с большой вероятностью БЗ распределение существует (то есть вероятность стремится к 1 при стремлении m к бесконечности).
• Если число объектов не достаточно велико, то есть ${\displaystyle m=n+o(n)}$, то с большой вероятностью БЗ распределение не существует.

• Любое БЗ распределение является min-max справедливым. Это следует прямо из обычных определений и не зависит от аддитивности.
• Если агенты имеют аддитивные функции полезности, то БЗ распределение является также пропорциональным и max-min-справедливым. В противном случае БЗ распределение может не быть пропорциональным и даже не быть max-min-справедливым.
• Любое распределение, обладающее конкурентным равновесием^[англ.] при равных доходах, не имеет зависти. Это верно независимо от аддитивности^[8].
• Любое оптимальное по Нэшу распределение (распределение, максимизирующее произведение полезностей) является БЗ1^[9].

См. статью Задача справедливого распределения объектов с детальным описанием и ссылками на литературу.

Ниже используются следующие обозначения:

• ${\displaystyle n}$ = число агентов, принимающих участие в дележе;
• ${\displaystyle m}$ = число предметов (объектов), которые следует распределить;
• БЗ = без зависти, БЗ1 = без зависти при исключении одного предмета (более слабое требование, чем БЗ), ПБЗ1 = предельно без зависти при исключении одного предмета (более слабое требование, чем БЗ1).
• ЭП = эффективно по Парето (PE = англ. Pareto-efficient).

Название	Число участников	Вход	Предпочтения	Число запросов	Справедливость	Эффективность	Комментарии
Подрезка[англ.]	2	Упорядоченные наборы	Строго монотонны	${\displaystyle 2^{m}}$	БЗ	Полная	Тогда и только тогда, когда полное БЗ распределение существует
AL-процедура	2	Упорядоченные объекты	Слабо аддитивны	${\displaystyle Poly(m)}$	Заведомо-БЗ	Частичная, но распределение не доминируется по Парето другой ЗБЗ
Подстраивающийся победитель	2	Оценка объектов	Аддитивны	${\displaystyle Poly(m)}$	БЗ и беспристрастно	ЭП	Может быть разделён один объект
Круговое планирование	${\displaystyle n}$	Упорядоченные объекты	Слабо аддитивны	${\displaystyle m}$	Заведомо-БЗ1	Полная
Циклы зависти	${\displaystyle n}$	Упорядоченные наборы	Монотонны	${\displaystyle O(mn^{3})}$	БЗ1	Полная
Механизм П-КРРД[англ.]	${\displaystyle n}$	Упорядоченные наборы	Любые	?	БЗ1, и ${\displaystyle (n+1)}$-максиминимизация долей	Частичная, но ЭП по отношению к распределённым объектам	Приблизительно стратегически неуязвимо, если агентов много.
Максимальное по Нэшу благополучие[9]	${\displaystyle n}$	Оценка объектов	Аддитивны	NP-трудна (но существуют в специальных случаях аппроксимации)	БЗ1 и примерно ${\displaystyle n}$-максиминимизация долей	ЭП	С субмодулярными функциями полезности распределение является ЭП и ПБЗ1.

• Максиминимизация долей — другой критерий справедливости.

• Felix Brandt, Vincent Conitzer, Ulle Endriss, Jérôme Lang, Ariel D. Procaccia. Handbook of Computational Social Choice (англ.). — Cambridge University Press, 2016. — ISBN 9781107060432.
• Sylvain Bouveret, Ulle Endriss, Jérôme Lang. Fair Division Under Ordinal Preferences: Computing Envy-Free Allocations of Indivisible Goods // ECAI 2010. — 2010. — С. 387–392.
• Bouveret S., Lang J. Efficiency and Envy-freeness in Fair Division of Indivisible Goods: Logical Representation and Complexity // JAIR. — 2008. — Т. 32. — doi:10.1613/jair.2467.
• Bart De Keijzer, Sylvain Bouveret, Tomas Klos, Yingqian Zhang. On the Complexity of Efficiency and Envy-Freeness in Fair Division of Indivisible Goods with Additive Preferences // Algorithmic Decision Theory. — 2009. — Т. 5783. — (Lecture Notes in Computer Science). — ISBN 978-3-642-04427-4. — doi:10.1007/978-3-642-04428-1_9.
• Eric Budish. The Combinatorial Assignment Problem: Approximate Competitive Equilibrium from Equal Incomes // Journal of Political Economy. — 2011. — Т. 119, вып. 6. — doi:10.1086/664613.
• Ioannis Caragiannis, David Kurokawa, Hervé Moulin, Ariel D. Procaccia, Nisarg Shah, Junxing Wang. The Unreasonable Fairness of Maximum Nash Welfare // Proceedings of the 2016 ACM Conference on Economics and Computation - EC '16. — 2016. — С. 305. — ISBN 9781450339360. — doi:10.1145/2940716.2940726.
• Lipton R. J., Markakis E., Mossel E., Saberi A. On approximately fair allocations of indivisible goods // Proceedings of the 5th ACM conference on Electronic commerce - EC '04. — 2004. — ISBN 1-58113-771-0. — doi:10.1145/988772.988792.
• Graham R. L. Bounds on Multiprocessing Timing Anomalies // SIAM Journal on Applied Mathematics. — 1969. — Т. 17, вып. 2. — doi:10.1137/0117039.
• Trung Thanh Nguyen, Jörg Rothe. Minimizing envy and maximizing average Nash social welfare in the allocation of indivisible goods // Discrete Applied Mathematics. — 2014. — Т. 179. — doi:10.1016/j.dam.2014.09.010.
• John P. Dickerson, Jonathan Goldman, Jeremy Karp, Ariel D. Procaccia, Tuomas Sandholm. The Computational Rise and Fall of Fairness // In Proceedings of the Twenty-Eighth AAAI Conference on Artificial Intelligence (2014). — 2014. ACM link