Отсутствие зависти

Критерий справедливого деления

Свобода от зависти , также известная как отсутствие зависти , является критерием справедливого распределения . Он гласит, что когда ресурсы распределяются между людьми с равными правами, каждый человек должен получить долю, которая, по его мнению, по крайней мере так же хороша, как доля, полученная любым другим агентом. Другими словами, ни один человек не должен испытывать зависть .

Общие определения

Предположим, что определенный ресурс разделен между несколькими агентами, так что каждый агент получает долю . Каждый агент имеет личное отношение предпочтения по различным возможным долям. Раздел называется свободным от зависти ( EF ), если для всех и : ${\displaystyle i}$ ${\displaystyle X_{i}}$ ${\displaystyle i}$ ${\displaystyle \succeq _{i}}$ ${\displaystyle i}$ ${\displaystyle j}$

${\displaystyle X_{i}\succeq _{i}X_{j}}$

Другой термин для обозначения отсутствия зависти — отсутствие зависти ( НЗ ).

Если предпочтения агентов представлены функциями ценности , то это определение эквивалентно: ${\displaystyle V_{i}}$

${\displaystyle V_{i}(X_{i})\geq V_{i}(X_{j})}$

Другими словами: мы говорим, что агент завидует агенту, если он предпочитает часть другого своему собственному, то есть: ${\displaystyle i}$ ${\displaystyle j}$ ${\displaystyle i}$ ${\displaystyle j}$

${\displaystyle X_{i}\prec _{i}X_{j}}$

${\displaystyle V_{i}(X_{i})<V_{i}(X_{j})}$

Разделение называется свободным от зависти, если ни один агент не завидует другому агенту.

Особые случаи

Понятие отсутствия зависти было введено Джорджем Гамовым и Марвином Стерном в 1958 году. ^[1] Они задались вопросом, всегда ли возможно разделить торт (гетерогенный ресурс) между n детьми с разными вкусами так, чтобы ни один ребенок не завидовал другому. Для n = 2 детей это можно сделать с помощью алгоритма «Разделить и выбрать» , но для n > 2 задача становится намного сложнее. См. разделение торта без зависти .

В дележе торта EF означает, что каждый ребенок считает, что его доля по крайней мере такая же большая , как и любая другая доля; в распределении домашних дел EF означает, что каждый агент считает, что его доля по крайней мере такая же маленькая , как и любая другая доля (главным вопросом в обоих случаях является то, что ни один агент не захочет обмениваться своей долей с любым другим агентом). См. раздел домашних дел .

Свобода от зависти была введена в экономическую проблему распределения ресурсов Дунканом Фоли в 1967 году. ^[2] В этой проблеме вместо одного гетерогенного ресурса есть несколько однородных ресурсов. Свобода от зависти сама по себе легко достигается, просто давая каждому человеку 1/ n каждого ресурса. Задача, с экономической точки зрения, состоит в том, чтобы объединить ее с эффективностью по Парето. Задача была впервые определена Дэвидом Шмейдлером и Менахемом Яари . ^[3] См. Эффективное разделение без зависти .

Когда ресурсы для деления дискретны (неделимы), свобода от зависти может быть недостижима даже при наличии одного ресурса и двух людей. Существуют различные способы справиться с этой проблемой:

• Перевод денег между участниками с целью компенсации тем, кто получает менее ценные вещи. Это решение используется, например, в задаче о гармонии аренды и в ценообразовании без зависти .
• Разделение небольшого количества предметов. Это делается, например, в скорректированной процедуре победителя .
• Нахождение приблизительно справедливых распределений; см. распределение предметов без зависти .
• Поиск максимально возможных частичных распределений без зависти; см. сопоставление без зависти .
• Использование рандомизации для поиска распределений, которые не вызывают зависти в ожиданиях («ex-ante»); см. справедливое случайное распределение .

Варианты

Сильная свобода от зависти требует, чтобы каждый агент строго предпочитал свой набор другим наборам. ^[4]

Супер-свобода от зависти требует, чтобы каждый агент строго предпочитал свой набор 1/ n от общей стоимости и строго предпочитал 1/ n каждому из других наборов. ^{[4] [5]} Очевидно, что супер-свобода от зависти подразумевает сильную свободу от зависти, которая подразумевает свободу от зависти.

Групповая свобода от зависти ( коалиционная свобода от зависти ) — это усиление свободы от зависти, требующее, чтобы каждая группа участников чувствовала, что их распределенная доля по крайней мере так же хороша, как доля любой другой группы того же размера. Более слабое требование заключается в том, чтобы каждый отдельный агент не завидовал никакой коалиции других агентов; это иногда называют строгой свободой от зависти . ^[6]

Свобода от зависти стохастического доминирования (SD-свобода от зависти, также называемая необходимой свободой от зависти ) — это усиление свободы от зависти для обстановки, в которой агенты сообщают о порядковых рангах по элементам. Она требует, чтобы свобода от зависти сохранялась по отношению ко всем аддитивным оценкам, которые совместимы с порядковым рангом. Другими словами, каждый агент должен верить, что его/ее набор по крайней мере так же хорош, как набор любого другого агента, в соответствии с расширением набора ответов его/ее порядкового ранга элементов. Приблизительный вариант SD-EF, называемый SD-EF1 (SD-EF до одного элемента), может быть достигнут с помощью процедуры распределения элементов по круговой системе .

Отсутствие оправданной зависти является ослаблением отсутствия зависти для двусторонних рынков, на которых и агенты, и «предметы» имеют предпочтения по отношению к противоположной стороне, например, рынок подбора учеников для школ. Ученик А испытывает оправданную зависть к ученику Б, если А предпочитает школу, назначенную Б, и в то же время школа, назначенная Б, предпочитает А.

Ex-ante envy-freeness — это ослабление envy-freeness, используемое в условиях справедливого случайного распределения . В этих условиях каждый агент получает лотерею по предметам; распределение лотерей называется ex-ante envy-free, если ни один агент не предпочитает лотерею другого агента, т. е. ни один агент не назначает более высокую ожидаемую полезность лотерее другого агента. Распределение называется ex-post envy-free, если каждый результат свободен от зависти. Очевидно, что ex-post envy-free подразумевает ex-ante envy-free, но обратное может быть неверным.

Локальная свобода от зависти ^{[7] [8]} (также называемая: сетевая свобода от зависти ^[9] или социальная свобода от зависти ^{[10] [11]} ) — это ослабление свободы от зависти, основанное на социальной сети . Она предполагает, что люди знают только о распределении своих соседей в сети, и поэтому они могут завидовать только своим соседям. Стандартная свобода от зависти — это особый случай социальной свободы от зависти, в которой сеть представляет собой полный граф .

Мета-отсутствие зависти требует, чтобы агенты не завидовали друг другу не только в отношении окончательного распределения, но и в отношении своих целей в протоколе. ^[12] См. Симметричное справедливое разрезание торта .

Минимизация зависти — это задача оптимизации, в которой целью является минимизация количества зависти (которое может быть определено различными способами), даже в случаях, когда отсутствие зависти невозможно. Для приблизительных вариантов отсутствия зависти, используемых при распределении неделимых объектов, см. распределение элементов без зависти .

Связь с другими критериями справедливости

Последствия между пропорциональностью и отсутствием зависти

Пропорциональность (PR) и отсутствие зависти (EF) — два независимых свойства, но в некоторых случаях одно из них может подразумевать другое.

Когда все оценки являются аддитивными функциями множества и весь пирог делится, имеют место следующие последствия:

• При наличии двух партнеров PR и EF эквивалентны;
• При наличии трех и более партнеров EF подразумевает PR, но не наоборот. Например, возможно, что каждый из трех партнеров получает 1/3 по своему субъективному мнению, но по мнению Алисы доля Боба стоит 2/3.

Когда оценки только субаддитивны , EF все еще подразумевает PR, но PR больше не подразумевает EF даже с двумя партнерами: возможно, что доля Алисы стоит 1/2 в ее глазах, но доля Боба стоит еще больше. Напротив, когда оценки только супераддитивны , PR все еще подразумевает EF с двумя партнерами, но EF больше не подразумевает PR даже с двумя партнерами: возможно, что доля Алисы стоит 1/4 в ее глазах, но доля Боба стоит еще меньше. Аналогично, когда не весь торт разделен, EF больше не подразумевает PR. Последствия суммированы в следующей таблице:

Смотрите также

• Неприятие неравенства
• Эксперименты по справедливому разделу , изучающие относительную важность отсутствия зависти по сравнению с другими критериями справедливости.

Ссылки

1. Гамов, Джордж; Стерн, Марвин (1958). Математическая головоломка. Viking Press. ISBN 0670583359.
2. Фоли, Дункан (1967). «Распределение ресурсов и государственный сектор». Yale Econ Essays . 7 (1): 45–98.
3. Дэвид Шмейдлер и Менахем Яари (1971). «Справедливое распределение». Mimeo.
4. Barbanel, Julius B. (1996-01-01). "Суперсвободное от зависти разделение тортов и независимость мер". Журнал математического анализа и приложений . 197 (1): 54–60. doi : 10.1006/S0022-247X(96)90006-2 . ISSN  0022-247X.
5. Вебб, Уильям А. (1 ноября 1999 г.). «Алгоритм для суперсвободного от зависти деления торта». Журнал математического анализа и приложений . 239 (1): 175–179. doi : 10.1006/jmaa.1999.6581 . ISSN  0022-247X.
6. Чжоу, Линь (1992-06-01). «Строго справедливые распределения в крупных обменных экономиках». Журнал экономической теории . 57 (1): 158–175. doi : 10.1016/S0022-0531(05)80046-8 . ISSN  0022-0531.
7. Абебе, Редиет; Кляйнберг, Джон; Паркс, Дэвид К. (2017-05-08). «Справедливое разделение через социальное сравнение». Труды 16-й конференции по автономным агентам и многоагентным системам . AAMAS '17. Сан-Паулу, Бразилия: Международный фонд автономных агентов и многоагентных систем: 281–289. arXiv : 1611.06589 .
8. Бенье, Орели; Шевалейр, Янн; Гурвес, Лоран; Арутюнян, Арарат; Леска, Жюльен; Моде, Николя; Вильчински, Анаэль (01 сентября 2019 г.). «Местная свобода от зависти в вопросах распределения жилья». Автономные агенты и мультиагентные системы . 33 (5): 591–627. дои : 10.1007/s10458-019-09417-x. ISSN  1573-7454. S2CID  51869987.
9. Бэй, Сяохуэй; Цяо, Юмин; Чжан, Шэнъюй (07 июля 2017 г.). «Сетевая справедливость в разрезании торта». arXiv : 1707.02033 [cs.DS].
10. Фламмини, Микеле; Мауро, Мануэль; Тонелли, Маттео (01 апреля 2019 г.). «О свободе от социальной зависти на многоквартирных рынках». Искусственный интеллект . 269 : 1–26. дои : 10.1016/j.artint.2018.12.003 . ISSN  0004-3702. S2CID  19205358.
11. Бредерек, Роберт; Качмарчик, Анджей; Нидермайер, Рольф (23 ноября 2020 г.). «Распределения без зависти с уважением к социальным сетям». arXiv : 2011.11596 [cs.GT].
12. Manabe, Yoshifumi; Okamoto, Tatsuaki (2010). Hliněný, Petr; Kučera, Antonín (ред.). "Meta-Envy-Free Cake-Cutting Protocols". Математические основы компьютерных наук 2010. Lecture Notes in Computer Science. 6281. Berlin, Heidelberg: Springer: 501–512. Bibcode : 2010LNCS.6281..501M. doi : 10.1007/978-3-642-15155-2_44. ISBN 978-3-642-15155-2.