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

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

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

Поиск распределения без зависти, если оно существует

Упорядочение предпочтений для наборов: отсутствие зависти

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

Упорядочение предпочтений для объектов: заведомое/возможное отсутствие зависти

Обычно для людей проще упорядочить индивидуальные объекты, чем упорядочить наборы объектов. Предположим, что все агенты имеют адаптивные предпочтения, тогда имеется возможность поднять упорядочение объектов до частичного упорядочения наборов. Например, если объекты упорядочены 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), если оно оптимально по Парето для по меньшей мере одного адаптивного упорядочения наборов, согласующегося с упорядочением объектов.

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

Существует ли БЗ распределение

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

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

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

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

Круговая процедура

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

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

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

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

Процедура циклов зависти

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

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

Приблизительная П-КРРД процедура

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

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

Максимальное по Нэшу Благополучие

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

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

БЗ1 / БЗд

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

Минимизация отношения зависти

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

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

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

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

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

Оценки общего вида

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

Аддитивные одинаковые оценки

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

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

Аддитивные различные оценки

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

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

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

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

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

Существование размещения без зависти со случайными оценками

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

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

Отсутствие зависти и другие критерии справедливости

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

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

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

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

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

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