Завистливое распределение объектов (без зависти, БЗ, англ. Envy-free, EF распределение) — это задача справедливого распределения объектов, в которой критерием справедливости служит отсутствие зависти в получившемся распределении — каждый агент должен получить набор объектов, ценность которых (как он считает) не меньше долей, полученных другими агентами.
Поскольку объекты неделимы, БЗ распределение может не существовать. Простейшим случаем такого дележа является один объект, который следует распределить между хотя бы двумя агентами: если объект достанется одному агенту, второй будет ему завидовать. Таким образом, процедуры дележа предполагают различные виды ослабления требования отсутствия зависти.
Процедура подрезки находит полное распределение БЗ для двух агентов тогда и только тогда, когда такое распределение существует. Процедура требует от агентов ранжировать наборы объектов, но не требует информацию о количественной полезности. Алгоритм работает, если предпочтения агентов строго монотонны и нет необходимости предполагать, что они являются адаптивными предпочтениями. В худшем случае агенты могут иметь ряд возможных наборов, так что время работы может экспоненциально зависеть от числа объектов.
Обычно для людей проще упорядочить индивидуальные объекты, чем упорядочить наборы объектов. Предположим, что все агенты имеют адаптивные предпочтения, тогда имеется возможность поднять упорядочение объектов до частичного упорядочения наборов. Например, если объекты упорядочены w>x>y>z, отсюда следует, что {w, x}>{y, z} и {w, y}>{x, z}, но не следуют какие-либо предпочтения между {w, z} и {x, y}, между {x} и {y, z}, и так далее.
Если дано упорядочение объектов:
Бувре, Эндрисс и Ленг изучали алгоритмические вопросы поиска ЗБЗ/ВБЗ распределения с дополнительным условием эффективности, частичности, полноты, ЗОП или ВОП. В общем виде случай ВБЗ вычислительно более прост, а случай ЗБЗ более труден.
Пустое распределение всегда БЗ, но если мы хотим потребовать эффективность вдобавок к БЗ, решение задачи становится вычислительно сложным:
Некоторые процедуры находят распределение, которое не имеет зависти за исключением одного объекта (БЗ1) — для любых двух агентов A и B существует один объект, при удалении которого из набора агента B агент A уже не будет завидовать агенту B.
Если все агенты имеют слабо аддитивные полезности, следующий протокол (который похож на круговое планирование) даёт полностью БЗ1 распределение:
Протокол кругового планирования требует слабой аддитивности, поскольку в нём требуется, чтобы каждый агент выбирал «лучший объект» без знания, какие объекты будут выбраны им впоследствии. Другими словами, это предполагает, что объекты являются независимыми товарами.
Процедура циклов зависти возвращает полностью БЗ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).
Имеется альтернативный критерий, называемый Отсутствие Зависти за исключением самого Дешёвого (БЗд) — для любых двух агентов A и B. Если мы удалим из набора объектов агента B любой объект, то A не будет завидовать B. БЗд строго сильнее, чем БЗ1. Но, пока неизвестно, всегда ли существуют БЗд распределения.
Если дано распределение X, определим отношение зависти i к j (EnvyRatio) как:
E n v y R a t i o ( X , i , j ) := max ( 1 , u i ( X j ) u i ( X i ) ) {displaystyle EnvyRatio(X,i,j):=max(1,{u_{i}(X_{j}) over u_{i}(X_{i})})}так что отношение равно 1, если i не завидует j, и больше 1, если i завидует j. Определим отношение зависти распределения как:
E n v y R a t i o ( X ) := max i , j ( E n v y R a t i o ( X , i , j ) {displaystyle EnvyRatio(X):=max _{i,j}(EnvyRatio(X,i,j)}Задача минимизации отношения зависти — это задача нахождения распределения X с наименьшим отношением зависти.
При предпочтениях общего вида любой детерминированный алгоритм, который вычисляет распределение с минимальным отношением зависти требует количество запросов, в худшем случае экспоненциально зависящее от числа объектов.
При аддитивных и идентичных оценках предпочтений:
При аддитивных и различных оценках предпочтений
AL-процедура находит БЗ распределение для двух агентов. Она может отбросить некоторые из объектов, но конечное распределение эффективно по Парето в том смысле, что никакое другое БЗ распределение не лучше для одного и слабо лучше для другого. AL процедура требует упорядочить по ценности отдельные объекты только от агентов. Процедура предполагает, что агенты имеют адаптивные предпочтения, и даёт распределение, в котором заведомо отсутствует зависть (заведомо без зависти, ЗБЗ).
Процедура «подстраивающийся победитель» возвращает полное и эффективное БЗ распределения для двух агентов, но может потребовать разрезания одного из объектов (или один из объектов остаётся в общем пользовании). Процедура требует, чтобы каждый агент сообщил о численном значении полезности для каждого объекта, и предполагает, что агенты имеют аддитивные функции полезности.
Если агенты имеют аддитивные функции полезности, которые взяты из распределений вероятности, удовлетворяющих некоторым критериям, и число объектов достаточно велико по отношению к числу агентов, то БЗ распределение существует с высокой вероятностью. В частности
См. статью Задача справедливого распределения объектов с детальным описанием и ссылками на литературу.
Ниже используются следующие обозначения: