Завистливое распределение объектовЗавистливое распределение объектов (без зависти, БЗ, англ. Envy-free, EF распределение[1]) — это задача справедливого распределения объектов, в которой критерием справедливости служит отсутствие зависти в получившемся распределении — каждый агент должен получить набор объектов, ценность которых (как он считает) не меньше долей, полученных другими агентами[2]. Поскольку объекты неделимы, БЗ распределение может не существовать. Простейшим случаем такого дележа является один объект, который следует распределить между хотя бы двумя агентами: если объект достанется одному агенту, второй будет ему завидовать. Таким образом, процедуры дележа предполагают различные виды ослабления требования отсутствия зависти. Поиск распределения без зависти, если оно существуетУпорядочение предпочтений для наборов: отсутствие завистиПроцедура подрезки[англ.] находит полное распределение БЗ для двух агентов тогда и только тогда, когда такое распределение существует. Процедура требует от агентов ранжировать наборы объектов, но не требует информацию о количественной полезности. Алгоритм работает, если предпочтения агентов строго монотонны и нет необходимости предполагать, что они являются адаптивными предпочтениями[англ.]. В худшем случае агенты могут иметь ряд возможных наборов, так что время работы может экспоненциально зависеть от числа объектов. Упорядочение предпочтений для объектов: заведомое/возможное отсутствие завистиОбычно для людей проще упорядочить индивидуальные объекты, чем упорядочить наборы объектов. Предположим, что все агенты имеют адаптивные предпочтения[англ.], тогда имеется возможность поднять упорядочение объектов до частичного упорядочения наборов. Например, если объекты упорядочены w>x>y>z, отсюда следует, что {w, x}>{y, z} и {w, y}>{x, z}, но не следуют какие-либо предпочтения между {w, z} и {x, y}, между {x} и {y, z}, и так далее. Если дано упорядочение объектов:
Бувре, Эндрисс и Ленг[3] изучали алгоритмические вопросы поиска ЗБЗ/ВБЗ распределения с дополнительным условием эффективности, частичности, полноты, ЗОП или ВОП. В общем виде случай ВБЗ вычислительно более прост, а случай ЗБЗ более труден. Существует ли БЗ распределениеПустое распределение всегда БЗ, но если мы хотим потребовать эффективность вдобавок к БЗ, решение задачи становится вычислительно сложным[4]:
Поиск распределения с ограниченным уровнем завистиНекоторые процедуры находят распределение, которое не имеет зависти за исключением одного объекта (БЗ1) — для любых двух агентов A и B существует один объект, при удалении которого из набора агента B агент A уже не будет завидовать агенту B[8]. Круговая процедураЕсли все агенты имеют слабо аддитивные полезности, следующий протокол (который похож на круговое планирование) даёт полностью БЗ1 распределение:
Протокол кругового планирования требует слабой аддитивности, поскольку в нём требуется, чтобы каждый агент выбирал «лучший объект» без знания, какие объекты будут выбраны им впоследствии. Другими словами, это предполагает, что объекты являются независимыми товарами. Процедура циклов завистиПроцедура циклов зависти возвращает полностью БЗ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). БЗ1 / БЗдИмеется альтернативный критерий, называемый Отсутствие Зависти за исключением самого Дешёвого (БЗд) — для любых двух агентов A и B. Если мы удалим из набора объектов агента B любой объект, то A не будет завидовать B. БЗд строго сильнее, чем БЗ1. Но, пока неизвестно, всегда ли существуют БЗд распределения[9]. Минимизация отношения завистиЕсли дано распределение X, определим отношение зависти i к j (EnvyRatio) как: так что отношение равно 1, если i не завидует j, и больше 1, если i завидует j. Определим отношение зависти распределения как: Задача минимизации отношения зависти — это задача нахождения распределения X с наименьшим отношением зависти. Оценки общего видаПри предпочтениях общего вида любой детерминированный алгоритм, который вычисляет распределение с минимальным отношением зависти требует количество запросов, в худшем случае экспоненциально зависящее от числа объектов[5]. Аддитивные одинаковые оценкиПри аддитивных и идентичных оценках предпочтений[5]:
Аддитивные различные оценкиПри аддитивных и различных оценках предпочтений[11]
Поиск частичного распределения без завистиAL-процедура находит БЗ распределение для двух агентов. Она может отбросить некоторые из объектов, но конечное распределение эффективно по Парето в том смысле, что никакое другое БЗ распределение не лучше для одного и слабо лучше для другого. AL процедура требует упорядочить по ценности отдельные объекты только от агентов. Процедура предполагает, что агенты имеют адаптивные предпочтения[англ.], и даёт распределение, в котором заведомо отсутствует зависть (заведомо без зависти, ЗБЗ). Процедура «подстраивающийся победитель» возвращает полное и эффективное БЗ распределения для двух агентов, но может потребовать разрезания одного из объектов (или один из объектов остаётся в общем пользовании). Процедура требует, чтобы каждый агент сообщил о численном значении полезности для каждого объекта, и предполагает, что агенты имеют аддитивные функции полезности. Существование размещения без зависти со случайными оценкамиЕсли агенты имеют аддитивные функции полезности, которые взяты из распределений вероятности, удовлетворяющих некоторым критериям, и число объектов достаточно велико по отношению к числу агентов, то БЗ распределение существует с высокой вероятностью. В частности[12]
Отсутствие зависти и другие критерии справедливости
См. статью Задача справедливого распределения объектов с детальным описанием и ссылками на литературу. Итоговая таблицаНиже используются следующие обозначения:
См. также
Примечания
Литература
Information related to Завистливое распределение объектов |