Распределение предметов без зависти

Распределение элементов без зависти (EF) — это проблема справедливого распределения элементов , в которой критерием справедливости является отсутствие зависти — каждый агент должен получить набор, который, по его мнению, по крайней мере так же хорош, как набор любого другого агента. ^[1]^{: 296–297}

Поскольку элементы неделимы, присвоение EF может не существовать. Самый простой случай — когда есть один предмет и минимум два агента: если предмет закреплен за одним агентом, другой позавидует.

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

Нахождение распределения без зависти, когда оно существует

Заказ по предпочтениям в пакетах: отсутствие зависти

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

Порядок предпочтений по предметам: необходимая/возможная свобода от зависти

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

Распределение обязательно является свободным от зависти (NEF), если оно свободно от зависти согласно всем адаптивным рейтингам пакетов, соответствующим рейтингу элементов;
Распределение, возможно, является свободным от зависти (PEF), если для каждого агента i существует хотя бы один реагирующий рейтинг пакета, соответствующий рейтингу элемента i , благодаря которому я не завидую;
Распределение является слабо свободным от зависти (WPEF), если для каждой пары агентов i,j существует хотя бы один отзывчивый рейтинг пакета, соответствующий рейтингу элемента i , благодаря чему я не завидую j ;
Распределение обязательно является Парето-оптимальным (NPE), если оно Парето-оптимально в соответствии со всеми реагирующими групповыми ранжированиями, соответствующими ранжированию элементов (см. Порядковую эффективность Парето );
Распределение, возможно, является Парето-оптимальным (PPE), если оно является Парето-оптимальным согласно хотя бы одному адаптивному ранжированию пакета, согласующемуся с ранжированием элемента.

Известны следующие результаты:

Бувере, Эндрисс и Ланг ^[2] Предположим, что все агенты имеют строгие предпочтения. Они изучают алгоритмические вопросы поиска распределения NEF/PEF с дополнительным условием эффективности, в частности, полнотой или NPE или PPE. В общем, PEF прост, а NEF сложен: проверка существования выделения NEF является NP-полной , а проверка существования WPEF может быть выполнена за полиномиальное время.
Азиз, Гасперс, Маккензи и Уолш ^[3] изучите более общую ситуацию, в которой агенты могут иметь слабые предпочтения (с безразличием). В этом случае проверка существования WPEF является NP-полной. Решение о том, существует ли распределение PEF, принимается в P для строгих предпочтений или для n=2, но в целом оно является NP-полным. Остается открытым вопрос, находится ли при постоянном числе агентов решение о существовании распределения NEF в P.

Кардинальные коммунальные услуги

Пустое распределение всегда равно EF. Но если нам нужна некоторая эффективность в дополнение к EF, тогда проблема решения становится вычислительно сложной: ^[1]^{: 300–310}

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

Проблема решения может стать разрешимой, если некоторые параметры проблемы считать фиксированными небольшими константами: ^[8]

Учитывая количество объектов m в качестве параметра, существование распределения PE+EF может быть определено во времени. $O^{*}(m^{2m})$ для аддитивных или дихотомических полезностей. Если утилиты являются двоичными и/или идентичными, время выполнения падает до $O^{*}(m^{m})$ . Здесь обозначение $O^{*}$ скрывает выражения, полиномиальные по другим параметрам (например, количеству агентов).
Учитывая количество агентов n в качестве параметра, существование распределения PE+EF остается затруднительным. В случае дихотомических утилит это NP-трудно даже для n =2. ^[6] Однако теперь она находится в NP и может быть эффективно решена с помощью NP-оракула (например, решателя SAT ). С $n\geq 5$ агенты, это можно сделать с помощью $2^{n+1}$ такие оракулы, и по крайней мере $2^{n-4}$ оракулы необходимы, если только P=NP. С аддитивными полезностями это NP-трудно даже для n =2. ^[6] Более того, он W[1]-полен по количеству агентов, даже если все утилиты идентичны и закодированы в унарном формате.
Учитывая количество агентов n и наибольшую полезность V в качестве параметров, существование распределения PE+EF может быть решено во времени. $O^{*}((m\cdot V+1)^{n^{2}}\cdot mn^{2})$ для аддитивных утилит, использующих динамическое программирование .
Рассматривая как количество агентов n , так и количество уровней полезности z в качестве параметров, существование распределения PE+EF для идентичных аддитивных полезностей можно определить с помощью целочисленной линейной программы с $d=n\cdot z^{n}$ переменные; Алгоритм Ленстры позволяет решить такую ЗЛП за время. $O^{*}(d^{2.5d})$

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

Многие процедуры обнаруживают распределение, «почти» свободное от зависти, т. е. уровень зависти ограничен. Существуют различные понятия «почти» отсутствия зависти:

EF1 – без зависти максимум до одного предмета

Распределение называется EF1 , если для каждых двух агентов A и B мы удаляем не более одного элемента из набора B, то A не завидует B. ^[9] Распределение EF1 всегда существует и может быть эффективно найдено с помощью различных процедур, в частности:

Когда все агенты имеют слабо аддитивные полезности, протокол циклического перебора находит полное распределение EF1. Требуется слабая аддитивность, поскольку каждый агент должен иметь возможность выбрать в каждой ситуации «лучший элемент».
В более общем случае, когда полезности всех агентов монотонно возрастают, процедура графа зависти находит полное распределение EF1. Единственное требование состоит в том, что агенты могут ранжировать пакеты предметов. Если оценки агентов представлены кардинальной функцией полезности , то гарантия EF1 имеет дополнительную интерпретацию: числовой уровень зависти каждого агента не превышает максимальной предельной полезности — наибольшей предельной полезности одного товара для данного товара. агент.
Когда агенты имеют произвольные полезности (не обязательно аддитивные или монотонные), механизм A-CEEI возвращает частичное распределение EF1. Единственное требование состоит в том, что агенты могут ранжировать пакеты предметов. Небольшое количество элементов может остаться нераспределенным, и, возможно, потребуется добавить небольшое количество элементов. Распределение является Парето-эффективным по отношению к распределенным элементам.
Алгоритм максимального благосостояния Нэша выбирает полное распределение, которое максимизирует продукт полезностей. Он требует, чтобы каждый агент предоставил числовую оценку каждого элемента, и предполагает, что полезности агентов аддитивны. Полученное распределение является как EF1, так и эффективным по Парето . ^[10]
Различные другие алгоритмы возвращают распределения EF1, которые также являются эффективными по Парето; см. Эффективное и приблизительно справедливое распределение товаров .
Для двух агентов с произвольными монотонными оценками или трех агентов с аддитивными оценками распределение EF1 можно вычислить с помощью ряда запросов, логарифмических по числу элементов. ^[11]
Для двух агентов с произвольными функциями полезности (не обязательно монотонными) распределение EF1 может быть найдено за полиномиальное время. ^[12]
Не более чем для 4 агентов с произвольными монотонными оценками или для n агентов с одинаковыми монотонными оценками всегда существует распределение EF1, которое также является связным (когда элементы предварительно заказаны в строке, например, дома на улице). В доказательстве используется алгоритм, аналогичный протоколам Симмонса–Су . Когда имеется n > 4 агентов, неизвестно, существует ли связанное распределение EF1, но связанное распределение EF2 существует всегда. ^[13]

EFx – без зависти до любого предмета

Распределение называется EFx, если для каждых двух агентов A и B, если мы удалим какой-либо элемент из набора B, то A не завидует B. ^[14] (для A) элемент EFx строго сильнее, чем EF1: EF1 позволяет нам устранить зависть, удалив наиболее ценный из набора B; элемент EFx требует, чтобы мы устраняли зависть, удаляя наименее ценный (для A). Известно, что распределение EFx существует в некоторых особых случаях:

Когда есть два агента или когда есть n агентов с одинаковыми оценками . В этом случае оптимальное распределение лексимина является EFx и оптимальным по Парето. Однако для вычисления требуется экспоненциально много запросов. ^[15]^[12]
Когда имеется n агентов с аддитивными оценками , но существует не более двух разных стоимостей товаров. В этом случае любое распределение максимального благосостояния по Нэшу представляет собой EFx. Более того, существует эффективный алгоритм расчета распределения EFx (хотя и не обязательно максимального благосостояния по Нэшу). ^[16]
Когда имеется n агентов с аддитивными оценками , но существует не более двух разных видов оценок. ^[17]
Когда есть три агента с аддитивными оценками . В этом случае существует алгоритм с полиномиальным временем. ^[18] ^[19]

Известны некоторые приближения:

Распределение EFx с приближением 1/2 (которое также удовлетворяет другому понятию приблизительной справедливости, называемому Maximin Aware ) может быть найдено за полиномиальное время. ^[20]
Распределение EFx с приближением 0,618 (которое также является EF1 и аппроксимирует другие понятия справедливости, называемые групповой максиминной долей и парной максиминной долей ) может быть найдено за полиномиальное время. ^[21]
Всегда существует частичное распределение EFx, при котором благосостояние Нэша составляет по крайней мере половину максимально возможного благосостояния Нэша. Другими словами, после пожертвования некоторых предметов на благотворительность оставшиеся предметы можно распределить способом EFx. Эта граница является наилучшей из возможных. На крупных рынках, где оценка агента по каждому товару относительно невелика, алгоритм достигает EFx с почти оптимальным благосостоянием Нэша. ^[22] Достаточно пожертвовать n -1 предметов, и ни один агент не позавидует набору пожертвованных предметов. ^[23]

Вопрос о том, существует ли распределение EFx вообще, остается открытым. Наименьшее открытое дело — 4 агента с аддитивными оценками.

В отличие от EF1, который требует логарифмического количества запросов по количеству элементов, вычисление распределения EFx может потребовать линейного числа запросов, даже если есть два агента с одинаковыми аддитивными оценками. ^[11]

Еще одно различие между EF1 и EFx заключается в том, что количество распределений EFX может составлять всего 2 (для любого количества элементов), тогда как количество распределений EF1 всегда экспоненциально зависит от количества элементов. ^[24]

EFm — приближенное беззависимое значение для смеси делимых и неделимых предметов.

Некоторые сценарии раздела включают в себя как делимые, так и неделимые предметы, например, делимые земли и неделимые дома. Распределение называется EFm, если для каждых двух агентов A и B: ^[25]

Если набор B содержит некоторые делимые товары, то A не завидует B (как при распределении EF).
Если набор B содержит только неделимые товары, то A не завидует B после удаления не более одного предмета из набора B (как в распределении EF1).

Распределение EFm существует для любого количества агентов. Однако для его обнаружения требуется оракул для точного разделения торта. Без этого оракула распределение EFm можно вычислить за полиномиальное время в двух особых случаях: два агента с общими аддитивными оценками или любое количество агентов с кусочно-линейными оценками.

В отличие от EF1, который совместим с Парето-оптимальностью, EFm может быть с ней несовместим.

Минимизация зависти

Вместо использования наихудшего предела величины зависти можно попытаться минимизировать величину зависти в каждом конкретном случае. см. в разделе «Минимизация зависти» Подробности и ссылки .

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

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

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

Когда каждый агент может получить не более одного предмета, а оценки бинарные (каждый агент либо любит, либо не любит каждый предмет), существует алгоритм с полиномиальным временем, который без зависти находит сопоставление максимальной мощности. ^[26]

Существование распределений EF со случайной оценкой

Если агенты имеют аддитивные функции полезности, которые получены из распределений вероятностей, удовлетворяющих некоторым критериям независимости, и количество элементов достаточно велико по сравнению с числом агентов, то распределение EF существует с высокой вероятностью . Особенно:

Если количество элементов достаточно велико: $m=\Omega (n\log n/\log \log n)$ , то распределение EF существует (вероятность стремится к 1, когда m стремится к бесконечности) и может быть найдено с помощью протокола циклического перебора . ^[27]
Если $m=\Omega (n\log n)$ , то распределение EF существует и может быть найдено путем максимизации социального благосостояния. ^[28] Эта граница также является жесткой из-за связи с проблемой сборщика купонов .
Если $m\geq 2n$ и m делится на n, то если распределение EF существует и может быть найдено с помощью алгоритма, основанного на сопоставлении. ^[29]

С другой стороны, если количество элементов недостаточно велико, то с высокой вероятностью распределения EF не существует.

Если количество элементов недостаточно велико, т.е. $m=n+o(n)$ , то распределение EF не существует. ^[28]
Если $m=o(n\log n/\log \log n)$ и m не «почти делится» на n, тогда распределение EF не существует. ^[29]

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

Каждое распределение EF является min-max-fair . Это следует непосредственно из порядковых определений и не зависит от аддитивности.
Если у всех агентов есть аддитивные функции полезности, то распределение EF также будет пропорциональным и максимально-минимально-справедливым . В противном случае распределение EF может быть непропорциональным и даже не максимально-минимально-справедливым.
Любое распределение конкурентного равновесия из равных доходов также не вызывает зависти. Это верно независимо от аддитивности. ^[9]
Каждое оптимальное по Нэшу распределение (распределение, максимизирующее продукт полезностей) равно EF1. ^[14]
Групповая свобода от зависти – это усиление свободы от зависти, которое применимо как к делимым, так и к неделимым объектам.

см. в разделе «Распределение предметов ярмарки» Подробную информацию и ссылки .

Сводная таблица

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

$n$ = количество агентов, участвующих в делении;
$m$ = количество элементов, которые нужно разделить;
EF = отсутствие зависти, EF1 = отсутствие зависти, кроме одного предмета (слабее, чем EF), MEF1 = предельное отсутствие зависти, кроме одного предмета (слабее, чем EF1).
PE = Парето-эффективный.

Имя	#партнеры	Вход	Предпочтения	#запросы	Справедливость	Эффективность	Комментарии
Подрез	2	Рейтинг пакетов	Строго монотонно	$2^{m}$	ЕСЛИ	Полный	Если и только если существует полное распределение EF
АЛ	2	Рейтинг предметов	Слабо аддитивный	$Poly(m)$	Обязательно ЭФ	Частичный, но не доминируемый по Парето другой НЭФ
Скорректированный победитель	2	Оценка предметов	Добавка	$Poly(m)$	ЭФ и справедливый	НА	Могу разделить один предмет.
Круговой	$n$	Рейтинг предметов	Слабо аддитивный	$m$	Обязательно EF1	Полный
Зависть-граф	$n$	Рейтинг пакетов	монотонный	$O(mn^{3})$	EF1	Полный
A-CEEI	$n$	Рейтинг пакетов	Любой	?	EF1 и $(n+1)$ -максимин-доля	Частично, но PE относительно выделенных элементов	Также примерно безопасен для стратегии при наличии большого количества агентов.
Максимальное благосостояние Нэша ^[14]	$n$	Оценка предметов	Добавка	NP-трудно (но в особых случаях есть приближения)	EF1, и примерно $n$ -максимин-доля	НА	Для субмодульных утилит распределение — PE и MEF1.

Ссылки

^ Jump up to: ^а ^б Брандт, Феликс; Конитцер, Винсент; Эндрисс, Улле; Ланг, Жером; Прокачча, Ариэль Д. (2016). Справочник по вычислительному социальному выбору . Издательство Кембриджского университета. ISBN 9781107060432 . ( бесплатная онлайн-версия )
^ Бувере, Сильвен; Эндрисс, Улле; Ланг, Жером (4 августа 2010 г.). «Справедливое разделение при порядковых предпочтениях: расчет распределения неделимых товаров без зависти» . Материалы конференции ECAI 2010 г. 2010: 19-я Европейская конференция по искусственному интеллекту . НЛД: IOS Press: 387–392. ISBN 978-1-60750-605-8 .
^ Азиз, Харис; Гасперс, Серж; Маккензи, Саймон; Уолш, Тоби (01 октября 2015 г.). «Справедливое распределение неделимых объектов по порядковым предпочтениям» . Искусственный интеллект . 227 : 71–92. arXiv : 1312.6546 . дои : 10.1016/j.artint.2015.06.002 . ISSN 0004-3702 . S2CID 1408197 .
^ Липтон, Р.Дж.; Маркакис, Э.; Моссель, Э.; Сабери, А. (2004). «О примерно справедливом распределении неделимых благ». Материалы 5-й конференции ACM по электронной коммерции - EC '04 . п. 125. дои : 10.1145/988772.988792 . ISBN 1-58113-771-0 .
^ Плаут, Бенджамин; Рафгарден, Тим (01 января 2020 г.). «Коммуникационная сложность дискретного ярмарочного отдела» . SIAM Journal по вычислительной технике . 49 (1): 206–243. arXiv : 1711.04066 . дои : 10.1137/19M1244305 . ISSN 0097-5397 . S2CID 212667868 .
^ Jump up to: ^а ^б ^с Бувере, С.; Ланг, Дж. (2008). «Эффективность и отсутствие зависти при справедливом разделе неделимых товаров: логическое представление и сложность» . Журнал исследований искусственного интеллекта . 32 : 525–564. дои : 10.1613/jair.2467 .
^ Де Кейзер, Барт; Бувере, Сильвен; Клос, Томас; Чжан, Инцянь (2009). «О сложности эффективности и независтливости при справедливом разделе неделимых товаров с аддитивными преференциями». Алгоритмическая теория принятия решений . Конспекты лекций по информатике. Том. 5783. с. 98. дои : 10.1007/978-3-642-04428-1_9 . ISBN 978-3-642-04427-4 .
^ Блим, Бернхард; Бредерек, Роберт; Нидермайер, Рольф (9 июля 2016 г.). «Сложность эффективного и свободного от зависти распределения ресурсов: мало агентов, ресурсов или уровней полезности» . Материалы двадцать пятой Международной совместной конференции по искусственному интеллекту . IJCAI'16. Нью-Йорк, Нью-Йорк, США: AAAI Press: 102–108. ISBN 978-1-57735-770-4 .
^ Jump up to: ^а ^б Будиш, Эрик (2011). «Комбинаторная задача о назначениях: приблизительное конкурентное равновесие при равных доходах». Журнал политической экономии . 119 (6): 1061–1103. CiteSeerX 10.1.1.357.9766 . дои : 10.1086/664613 . S2CID 154703357 .
^ Караяннис, Иоаннис; Курокава, Дэвид; Мулен, Эрве; Прокачча, Ариэль Д.; Шах, Нисарг; Ван, Цзюньсин (2016). Необоснованная справедливость максимального благосостояния Нэша (PDF) . Материалы конференции ACM по экономике и вычислениям 2016 г. - EC '16. п. 305. дои : 10.1145/2940716.2940726 . ISBN 9781450339360 .
^ Jump up to: ^а ^б О, Хун; Прокачча, Ариэль Д.; Суксомпонг, Варут (17 июля 2019 г.). «Справедливое распределение большого количества товаров с помощью небольшого количества запросов» . Материалы конференции AAAI по искусственному интеллекту . 33 (1): 2141–2148. arXiv : 1807.11367 . дои : 10.1609/aaai.v33i01.33012141 . ISSN 2374-3468 . S2CID 51867780 .
^ Jump up to: ^а ^б Берчи, Кристофер; Берчи-Ковач, Эрика Р.; Борос, Эндре; Гедефа, Фекаду Толесса; Камияма, Наоюки; Кавита, Теликепалли ; Кобаяши, Юсуке; Макино, Казухиса (08.06.2020). «Релаксация без зависти для товаров, работы по дому и смешанных предметов». arXiv : 2006.04428 [ econ.TH ].
^ Било, Витторио; Караяннис, Иоаннис; Фламмини, Микеле; Игараси, Аюми; Монако, Джанпьеро; Петерс, Доминик; Винчи, Козимо; Цвикер, Уильям С. (2022). «Почти незавидное распределение со связанными связками». Игры и экономическое поведение . 131 : 197–221. arXiv : 1808.09406 . дои : 10.1016/j.geb.2021.11.006 . S2CID 52112902 .
^ Jump up to: ^а ^б ^с Караяннис, Иоаннис; Курокава, Дэвид; Мулен, Эрве; Прокачча, Ариэль Д.; Шах, Нисарг; Ван, Цзюньсин (2016). Необоснованная справедливость максимального благосостояния Нэша (PDF) . Материалы конференции ACM по экономике и вычислениям 2016 г. - EC '16. п. 305. дои : 10.1145/2940716.2940726 . ISBN 9781450339360 .
^ Плаут, Бенджамин; Рафгарден, Тим (01 января 2020 г.). «Почти независть при общих оценках» . SIAM Journal по дискретной математике . 34 (2): 1039–1068. arXiv : 1707.04769 . дои : 10.1137/19M124397X . ISSN 0895-4801 . S2CID 216283014 .
^ Аманатидис, Георгиос; Бирмпас, Георгиос; Филос-Рацикас, Арис; Холлендер, Александрос; Вудурис, Александрос А. (2021). «Максимальное благосостояние Нэша и другие истории об EFX». Теоретическая информатика . 863 : 69–85. arXiv : 2001.09838 . дои : 10.1016/j.tcs.2021.02.020 . S2CID 210920309 .
^ Махара, Рёга (20 августа 2020 г.). «Существование EFX для двух аддитивных оценок». arXiv : 2008.08798 [ cs.GT ].
^ Чаудхури, Бхаскар Рэй; Гарг, Джугал; Мельхорн, Курт (30 мая 2020 г.). «EFX существует для трех агентов». arXiv : 2002.05119 [ cs.GT ].
^ {{cite arXiv:2205.07638 [cs.GT]}}
^ Чан, Хау; Чен, Цзин; Ли, Бо; У, Сяовэй (25 октября 2019 г.). «Максимин-ориентированное распределение неделимых благ». arXiv : 1905.09969 [ cs.GT ].
^ Аманатидис, Георгиос; Нтокос, Апостол; Маркакис, Евангелос (2020). «Несколько зайцев одним выстрелом: победа над 1/2 для EFX и GMMS посредством устранения цикла зависти». Теоретическая информатика . 841 : 94–109. arXiv : 1909.07650 . дои : 10.1016/j.tcs.2020.07.006 . S2CID 222070124 .
^ Караяннис, Иоаннис; Гравин, Ник; Хуан, Синь (17 июня 2019 г.). «Независимость от зависти к любому предмету с высоким благосостоянием Нэша: ценность пожертвования предметов» . Материалы конференции ACM по экономике и вычислениям 2019 года . ЕС '19. Финикс, Аризона, США: Ассоциация вычислительной техники. стр. 527–545. arXiv : 1902.04319 . дои : 10.1145/3328526.3329574 . ISBN 978-1-4503-6792-9 . S2CID 60441171 .
^ Чаудхури, Бхаскар Рэй; Кавита, Теликепалли ; Мельхорн, Курт; Сгурица, Алкмини (23 декабря 2019 г.), «Небольшая благотворительность гарантирует почти отсутствие зависти» , Труды симпозиума ACM-SIAM 2020 года по дискретным алгоритмам , Труды Общества промышленной и прикладной математики, стр. 2658–2672, arXiv : 1907.04596 , doi : 10.1137/1.9781611975994.162 , ISBN 978-1-61197-599-4 , S2CID 195874127 , получено 2 октября 2020 г.
^ Суксомпонг, Варут (30 сентября 2020 г.). «По количеству практически беззавидных ассигнований» . Дискретная прикладная математика . 284 : 606–610. arXiv : 2006.00178 . дои : 10.1016/j.dam.2020.03.039 . ISSN 0166-218X . S2CID 215715272 .
^ Бэй, Сяохуэй; Лю, Цзиньань; Лю, Синьхан (2021). интеллект . 293 : 103436. arXiv : 10.1016 . j Искусственный / .artint.2020.103436 .S2CID 231719223 .
^ Айгнер-Хорев, Элад; Сегал-Халеви, Эрель (2022). «Сопоставления без зависти в двудольных графах и их приложения к справедливому дележу». Информационные науки . 587 : 164–187. arXiv : 1901.09527 . дои : 10.1016/j.ins.2021.11.059 . S2CID 170079201 .
^ Мануранси, Пасин; Суксомпонг, Варут (08 апреля 2021 г.). «Закрытие пробелов в асимптотическом справедливом делении» . SIAM Journal по дискретной математике . 35 (2): 668–706. arXiv : 2004.05563 . дои : 10.1137/20M1353381 . S2CID 215744823 .
^ Jump up to: ^а ^б Джон П. Дикерсон; Джонатан Голдман; Джереми Карп; Ариэль Д. Прокачча; Туомас Сандхольм (2014). Вычислительный взлет и падение справедливости . В материалах двадцать восьмой конференции AAAI по искусственному интеллекту (2014). стр. 1405–1411. CiteSeerX 10.1.1.703.8413 . ссылка ACM
^ Jump up to: ^а ^б Мануранси, Пасин; Суксомпонг, Варут (2 июля 2020 г.). «Когда существуют распределения без зависти?» . SIAM Journal по дискретной математике . 34 (3): 1505–1521. arXiv : 1811.01630 . дои : 10.1137/19M1279125 . S2CID 220363902 .

[comsoc-1] Jump up to: ^а ^б Брандт, Феликс; Конитцер, Винсент; Эндрисс, Улле; Ланг, Жером; Прокачча, Ариэль Д. (2016). Справочник по вычислительному социальному выбору . Издательство Кембриджского университета. ISBN 9781107060432 . ( бесплатная онлайн-версия )

[2] Бувере, Сильвен; Эндрисс, Улле; Ланг, Жером (4 августа 2010 г.). «Справедливое разделение при порядковых предпочтениях: расчет распределения неделимых товаров без зависти» . Материалы конференции ECAI 2010 г. 2010: 19-я Европейская конференция по искусственному интеллекту . НЛД: IOS Press: 387–392. ISBN 978-1-60750-605-8 .

[3] Азиз, Харис; Гасперс, Серж; Маккензи, Саймон; Уолш, Тоби (01 октября 2015 г.). «Справедливое распределение неделимых объектов по порядковым предпочтениям» . Искусственный интеллект . 227 : 71–92. arXiv : 1312.6546 . дои : 10.1016/j.artint.2015.06.002 . ISSN 0004-3702 . S2CID 1408197 .

[lmms04-4] Липтон, Р.Дж.; Маркакис, Э.; Моссель, Э.; Сабери, А. (2004). «О примерно справедливом распределении неделимых благ». Материалы 5-й конференции ACM по электронной коммерции - EC '04 . п. 125. дои : 10.1145/988772.988792 . ISBN 1-58113-771-0 .

[5] Плаут, Бенджамин; Рафгарден, Тим (01 января 2020 г.). «Коммуникационная сложность дискретного ярмарочного отдела» . SIAM Journal по вычислительной технике . 49 (1): 206–243. arXiv : 1711.04066 . дои : 10.1137/19M1244305 . ISSN 0097-5397 . S2CID 212667868 .

[bl08-6] Jump up to: ^а ^б ^с Бувере, С.; Ланг, Дж. (2008). «Эффективность и отсутствие зависти при справедливом разделе неделимых товаров: логическое представление и сложность» . Журнал исследований искусственного интеллекта . 32 : 525–564. дои : 10.1613/jair.2467 .

[kbkz09-7] Де Кейзер, Барт; Бувере, Сильвен; Клос, Томас; Чжан, Инцянь (2009). «О сложности эффективности и независтливости при справедливом разделе неделимых товаров с аддитивными преференциями». Алгоритмическая теория принятия решений . Конспекты лекций по информатике. Том. 5783. с. 98. дои : 10.1007/978-3-642-04428-1_9 . ISBN 978-3-642-04427-4 .

[8] Блим, Бернхард; Бредерек, Роберт; Нидермайер, Рольф (9 июля 2016 г.). «Сложность эффективного и свободного от зависти распределения ресурсов: мало агентов, ресурсов или уровней полезности» . Материалы двадцать пятой Международной совместной конференции по искусственному интеллекту . IJCAI'16. Нью-Йорк, Нью-Йорк, США: AAAI Press: 102–108. ISBN 978-1-57735-770-4 .

[b11-9] Jump up to: ^а ^б Будиш, Эрик (2011). «Комбинаторная задача о назначениях: приблизительное конкурентное равновесие при равных доходах». Журнал политической экономии . 119 (6): 1061–1103. CiteSeerX 10.1.1.357.9766 . дои : 10.1086/664613 . S2CID 154703357 .

[ckmpsw162-10] Караяннис, Иоаннис; Курокава, Дэвид; Мулен, Эрве; Прокачча, Ариэль Д.; Шах, Нисарг; Ван, Цзюньсин (2016). Необоснованная справедливость максимального благосостояния Нэша (PDF) . Материалы конференции ACM по экономике и вычислениям 2016 г. - EC '16. п. 305. дои : 10.1145/2940716.2940726 . ISBN 9781450339360 .

[:0-11] Jump up to: ^а ^б О, Хун; Прокачча, Ариэль Д.; Суксомпонг, Варут (17 июля 2019 г.). «Справедливое распределение большого количества товаров с помощью небольшого количества запросов» . Материалы конференции AAAI по искусственному интеллекту . 33 (1): 2141–2148. arXiv : 1807.11367 . дои : 10.1609/aaai.v33i01.33012141 . ISSN 2374-3468 . S2CID 51867780 .

[:1-12] Jump up to: ^а ^б Берчи, Кристофер; Берчи-Ковач, Эрика Р.; Борос, Эндре; Гедефа, Фекаду Толесса; Камияма, Наоюки; Кавита, Теликепалли ; Кобаяши, Юсуке; Макино, Казухиса (08.06.2020). «Релаксация без зависти для товаров, работы по дому и смешанных предметов». arXiv : 2006.04428 [ econ.TH ].

[13] Било, Витторио; Караяннис, Иоаннис; Фламмини, Микеле; Игараси, Аюми; Монако, Джанпьеро; Петерс, Доминик; Винчи, Козимо; Цвикер, Уильям С. (2022). «Почти незавидное распределение со связанными связками». Игры и экономическое поведение . 131 : 197–221. arXiv : 1808.09406 . дои : 10.1016/j.geb.2021.11.006 . S2CID 52112902 .

[ckmpsw16-14] Jump up to: ^а ^б ^с Караяннис, Иоаннис; Курокава, Дэвид; Мулен, Эрве; Прокачча, Ариэль Д.; Шах, Нисарг; Ван, Цзюньсин (2016). Необоснованная справедливость максимального благосостояния Нэша (PDF) . Материалы конференции ACM по экономике и вычислениям 2016 г. - EC '16. п. 305. дои : 10.1145/2940716.2940726 . ISBN 9781450339360 .

[15] Плаут, Бенджамин; Рафгарден, Тим (01 января 2020 г.). «Почти независть при общих оценках» . SIAM Journal по дискретной математике . 34 (2): 1039–1068. arXiv : 1707.04769 . дои : 10.1137/19M124397X . ISSN 0895-4801 . S2CID 216283014 .

[16] Аманатидис, Георгиос; Бирмпас, Георгиос; Филос-Рацикас, Арис; Холлендер, Александрос; Вудурис, Александрос А. (2021). «Максимальное благосостояние Нэша и другие истории об EFX». Теоретическая информатика . 863 : 69–85. arXiv : 2001.09838 . дои : 10.1016/j.tcs.2021.02.020 . S2CID 210920309 .

[17] Махара, Рёга (20 августа 2020 г.). «Существование EFX для двух аддитивных оценок». arXiv : 2008.08798 [ cs.GT ].

[18] Чаудхури, Бхаскар Рэй; Гарг, Джугал; Мельхорн, Курт (30 мая 2020 г.). «EFX существует для трех агентов». arXiv : 2002.05119 [ cs.GT ].

[19] {{cite arXiv:2205.07638 [cs.GT]}}

[20] Чан, Хау; Чен, Цзин; Ли, Бо; У, Сяовэй (25 октября 2019 г.). «Максимин-ориентированное распределение неделимых благ». arXiv : 1905.09969 [ cs.GT ].

[21] Аманатидис, Георгиос; Нтокос, Апостол; Маркакис, Евангелос (2020). «Несколько зайцев одним выстрелом: победа над 1/2 для EFX и GMMS посредством устранения цикла зависти». Теоретическая информатика . 841 : 94–109. arXiv : 1909.07650 . дои : 10.1016/j.tcs.2020.07.006 . S2CID 222070124 .

[22] Караяннис, Иоаннис; Гравин, Ник; Хуан, Синь (17 июня 2019 г.). «Независимость от зависти к любому предмету с высоким благосостоянием Нэша: ценность пожертвования предметов» . Материалы конференции ACM по экономике и вычислениям 2019 года . ЕС '19. Финикс, Аризона, США: Ассоциация вычислительной техники. стр. 527–545. arXiv : 1902.04319 . дои : 10.1145/3328526.3329574 . ISBN 978-1-4503-6792-9 . S2CID 60441171 .

[23] Чаудхури, Бхаскар Рэй; Кавита, Теликепалли ; Мельхорн, Курт; Сгурица, Алкмини (23 декабря 2019 г.), «Небольшая благотворительность гарантирует почти отсутствие зависти» , Труды симпозиума ACM-SIAM 2020 года по дискретным алгоритмам , Труды Общества промышленной и прикладной математики, стр. 2658–2672, arXiv : 1907.04596 , doi : 10.1137/1.9781611975994.162 , ISBN 978-1-61197-599-4 , S2CID 195874127 , получено 2 октября 2020 г.

[24] Суксомпонг, Варут (30 сентября 2020 г.). «По количеству практически беззавидных ассигнований» . Дискретная прикладная математика . 284 : 606–610. arXiv : 2006.00178 . дои : 10.1016/j.dam.2020.03.039 . ISSN 0166-218X . S2CID 215715272 .

[25] Бэй, Сяохуэй; Лю, Цзиньань; Лю, Синьхан (2021). интеллект . 293 : 103436. arXiv : 10.1016 . j Искусственный / .artint.2020.103436 .S2CID 231719223 .

[26] Айгнер-Хорев, Элад; Сегал-Халеви, Эрель (2022). «Сопоставления без зависти в двудольных графах и их приложения к справедливому дележу». Информационные науки . 587 : 164–187. arXiv : 1901.09527 . дои : 10.1016/j.ins.2021.11.059 . S2CID 170079201 .

[27] Мануранси, Пасин; Суксомпонг, Варут (08 апреля 2021 г.). «Закрытие пробелов в асимптотическом справедливом делении» . SIAM Journal по дискретной математике . 35 (2): 668–706. arXiv : 2004.05563 . дои : 10.1137/20M1353381 . S2CID 215744823 .

[dgkps14-28] Jump up to: ^а ^б Джон П. Дикерсон; Джонатан Голдман; Джереми Карп; Ариэль Д. Прокачча; Туомас Сандхольм (2014). Вычислительный взлет и падение справедливости . В материалах двадцать восьмой конференции AAAI по искусственному интеллекту (2014). стр. 1405–1411. CiteSeerX 10.1.1.703.8413 . ссылка ACM

[ms20-29] Jump up to: ^а ^б Мануранси, Пасин; Суксомпонг, Варут (2 июля 2020 г.). «Когда существуют распределения без зависти?» . SIAM Journal по дискретной математике . 34 (3): 1505–1521. arXiv : 1811.01630 . дои : 10.1137/19M1279125 . S2CID 220363902 .

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

[16]

[17]

[18]

[19]

[20]

[21]

[22]

[23]

[24]

[25]

[26]

[27]

[28]

[29]