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

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

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

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

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

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

Предпочтения-упорядочения в пакетах: свобода от зависти

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

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

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

• Распределение обязательно является свободным от зависти (NEF), если оно свободно от зависти согласно всем отзывчивым ранжированиям наборов, соответствующим ранжированию элементов;
• Распределение, возможно, является свободным от зависти (PEF), если для каждого агента i существует по крайней мере один отзывчивый ранжирование пакетов, соответствующий ранжированию элементов i , которому i не завидует;
• Распределение является слабо возможно свободным от зависти (WPEF), если для каждой пары агентов i, j существует по крайней мере один отзывчивый ранжирование пакетов, согласующийся с ранжированием элементов i , согласно которому 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: оно является -полным даже при дихотомических полезностях ^[6] и даже при аддитивных полезностях ^[7] ( - это класс задач, которые могут быть решены за недетерминированное время при наличии оракула, который может решить любую задачу из NP). ${\displaystyle \Sigma _{2}^{\textrm {P}}}$ ${\displaystyle \Sigma _{2}^{\textrm {P}}}$

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

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

Нахождение распределения с ограниченным уровнем зависти

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

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

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

• Когда все агенты имеют слабо аддитивные полезности, протокол циклического перебора находит полное распределение EF1. Слабая аддитивность необходима, поскольку каждый агент должен иметь возможность выбрать в каждой ситуации «лучший элемент».
• В более общем случае, когда все агенты имеют монотонно возрастающие полезности, процедура envy-graph находит полное распределение 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] EFx строго сильнее EF1: EF1 позволяет нам устранить зависть, удалив наиболее ценный элемент (для A) из набора B; EFx требует, чтобы мы устранили зависть, удалив наименее ценный элемент (для A). Известно, что распределение EFx существует в некоторых особых случаях:

• Когда есть два агента, или когда есть n агентов с одинаковыми оценками . В этом случае лексимин -оптимальное распределение является EFx и Парето-оптимальным. Однако для вычисления требуется экспоненциально много запросов. ^{[15] [12]}
• Когда есть n агентов с аддитивными оценками , но есть максимум два различных значения для товаров. В этом случае любое распределение max-Nash-welfare есть EFx. Более того, существует эффективный алгоритм для расчета распределения EFx (хотя и не обязательно max-Nash-welfare). ^[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).

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

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

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

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

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

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

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

Свобода от зависти против других критериев справедливости

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

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

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

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

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

Ссылки

1. Брандт, Феликс; Конитцер, Винсент; Эндрисс, Улле; Ланг, Жером; Прокачча, Ариэль Д. (2016). Справочник по вычислительному социальному выбору. Cambridge University Press. ISBN 9781107060432.(бесплатная онлайн-версия)
2. Бувере, Сильвен; Эндрисс, Улле; Ланг, Жером (2010-08-04). «Справедливое разделение при порядковых предпочтениях: вычисление свободного от зависти распределения неделимых благ». Труды конференции 2010 года по ECAI 2010: 19-я Европейская конференция по искусственному интеллекту . NLD: IOS Press: 387–392. ISBN 978-1-60750-605-8.
3. Азиз, Харис; Гасперс, Серж; Маккензи, Саймон; Уолш, Тоби (2015-10-01). «Справедливое назначение неделимых объектов при порядковых предпочтениях». Искусственный интеллект . 227 : 71–92. arXiv : 1312.6546 . doi : 10.1016/j.artint.2015.06.002 . ISSN  0004-3702. S2CID  1408197.
4. Липтон, Р. Дж.; Маркакис, Э.; Моссел, Э.; Сабери, А. (2004). «О приблизительно справедливом распределении неделимых товаров». Труды 5-й конференции ACM по электронной коммерции — EC '04 . стр. 125. doi :10.1145/988772.988792. ISBN 1-58113-771-0.
5. Plaut, Benjamin; Roughgarden, Tim (2020-01-01). «Сложность связи дискретного справедливого деления». SIAM Journal on Computing . 49 (1): 206–243. arXiv : 1711.04066 . doi : 10.1137/19M1244305. ISSN  0097-5397. S2CID  212667868.
6. Бувере, С.; Ланг, Дж. (2008). «Эффективность и свобода от зависти при справедливом разделении неделимых благ: логическое представление и сложность». Журнал исследований искусственного интеллекта . 32 : 525–564. doi : 10.1613/jair.2467 .
7. Де Кейзер, Барт; Бувере, Сильвен; Клос, Томас; Чжан, Инцянь (2009). «О сложности эффективности и свободе от зависти при справедливом разделении неделимых благ с дополнительными предпочтениями». Алгоритмическая теория принятия решений . Конспект лекций по информатике. Том 5783. стр. 98. doi :10.1007/978-3-642-04428-1_9. ISBN 978-3-642-04427-4.
8. Bliem, Bernhard; Bredereck, Robert; Niedermeier, Rolf (2016-07-09). «Сложность эффективного и свободного от зависти распределения ресурсов: несколько агентов, ресурсов или уровней полезности». Труды Двадцать пятой Международной совместной конференции по искусственному интеллекту . IJCAI'16. Нью-Йорк, Нью-Йорк, США: AAAI Press: 102–108. ISBN 978-1-57735-770-4.
9. Budish, Eric (2011). «Комбинаторная задача о назначениях: приблизительное конкурентное равновесие из равных доходов». Журнал политической экономии . 119 (6): 1061–1103. CiteSeerX 10.1.1.357.9766 . doi :10.1086/664613. S2CID  154703357. 
10. Caragiannis, Ioannis; Kurokawa, David; Moulin, Hervé; Procaccia, Ariel D.; Shah, Nisarg; Wang, Junxing (2016). Необоснованная справедливость максимального благосостояния Нэша (PDF) . Труды конференции ACM 2016 года по экономике и вычислениям - EC '16. стр. 305. doi :10.1145/2940716.2940726. ISBN 9781450339360.
11. Oh, Hoon; Procaccia, Ariel D.; Suksompong, Warut (2019-07-17). «Справедливое распределение многих товаров с небольшим количеством запросов». Труды конференции AAAI по искусственному интеллекту . 33 (1): 2141–2148. arXiv : 1807.11367 . doi : 10.1609/aaai.v33i01.33012141 . ISSN  2374-3468. S2CID  51867780.
12. Берчи, Кристоф; Берчи-Ковач, Эрика Р.; Борос, Эндре; Гедефа, Фекаду Толесса; Камияма, Наоюки; Кавита, Теликепалли ; Кобаяши, Юсуке; Макино, Казухиса (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.
14. Caragiannis, Ioannis; Kurokawa, David; Moulin, Hervé; Procaccia, Ariel D.; Shah, Nisarg; Wang, Junxing (2016). Необоснованная справедливость максимального благосостояния Нэша (PDF) . Труды конференции ACM 2016 года по экономике и вычислениям - EC '16. стр. 305. doi :10.1145/2940716.2940726. ISBN 9781450339360.
15. Plaut, Benjamin; Roughgarden, Tim (2020-01-01). «Почти свобода от зависти с общими оценками». SIAM Journal on Discrete Mathematics . 34 (2): 1039–1068. arXiv : 1707.04769 . doi : 10.1137/19M124397X. ISSN  0895-4801. S2CID  216283014.
16. Аманатидис, Георгиос; Бирмпас, Георгиос; Филос-Ратсикас, Арис; Холлендер, Александрос; Вудурис, Александрос А. (2021). «Максимальное благосостояние Нэша и другие истории об EFX». Теоретическая информатика . 863 : 69–85. arXiv : 2001.09838 . doi : 10.1016/j.tcs.2021.02.020. S2CID  210920309.
17. Махара, Рёга (2020-08-20). «Существование EFX для двух аддитивных оценок». arXiv : 2008.08798 [cs.GT].
18. Чаудхури, Бхаскар Рэй; Гарг, Джугал; Мельхорн, Курт (30.05.2020). «EFX существует для трех агентов». arXiv : 2002.05119 [cs.GT].
19. {{цитировать arXiv:2205.07638 [cs.GT]}}
20. Чан, Хау; Чен, Цзин; Ли, Бо; У, Сяовэй (25 октября 2019 г.). «Максимин-ориентированное распределение неделимых благ». arXiv : 1905.09969 [cs.GT].
21. Аманатидис, Георгиос; Нтокос, Апостолос; Маркакис, Евангелос (2020). «Несколько зайцев одним выстрелом: победа над EFX и GMMS с помощью устранения цикла зависти». Теоретическая информатика . 841 : 94–109. arXiv : 1909.07650 . doi : 10.1016/j.tcs.2020.07.006. S2CID  222070124.
22. Caragiannis, Ioannis; Gravin, Nick; Huang, Xin (2019-06-17). «Свобода от зависти к любому предмету с высоким благосостоянием Нэша: добродетель пожертвований предметов». Труды конференции ACM 2019 года по экономике и вычислениям . EC '19. Phoenix, AZ, USA: Association for Computing Machinery. стр. 527–545. arXiv : 1902.04319 . doi : 10.1145/3328526.3329574. ISBN 978-1-4503-6792-9. S2CID  60441171.
23. Чаудхури, Бхаскар Рэй; Кавита, Теликепалл ; Мельхорн, Курт; Сгурица, Алкмини (2019-12-23), «Немного благотворительности гарантирует почти свободу от зависти», Труды симпозиума ACM-SIAM 2020 года по дискретным алгоритмам , Труды, Общество промышленной и прикладной математики, стр. 2658–2672, arXiv : 1907.04596 , doi : 10.1137/1.9781611975994.162, ISBN 978-1-61197-599-4, S2CID  195874127 , получено 2020-10-02
24. Суксомпонг, Варут (30.09.2020). «О числе почти свободных от зависти распределений». Дискретная прикладная математика . 284 : 606–610. arXiv : 2006.00178 . doi : 10.1016/j.dam.2020.03.039. ISSN  0166-218X. S2CID  215715272.
25. Бэй, Сяохуэй; Ли, Цзыхао; Лю, Цзиньянь; Лю, Шэнсинь; Лу, Синьхан (2021). «Справедливое разделение смешанных делимых и неделимых товаров». Искусственный интеллект . 293 : 103436. arXiv : 1911.07048 . doi : 10.1016/j.artint.2020.103436. S2CID  231719223.
26. Айгнер-Хорев, Элад; Сегал-Халеви, Эрель (2022). «Сочетания без зависти в двудольных графах и их применение к справедливому делению». Информационные науки . 587 : 164–187. arXiv : 1901.09527 . doi : 10.1016/j.ins.2021.11.059. S2CID  170079201.
27. Манурангси, Пасин; Суксомпонг, Варут (2021-04-08). «Закрытие пробелов в асимптотическом справедливом делении». Журнал SIAM по дискретной математике . 35 (2): 668–706. arXiv : 2004.05563 . doi : 10.1137/20M1353381. S2CID  215744823.
28. Джон П. Дикерсон; Джонатан Голдман; Джереми Карп; Ариэль Д. Прокачча; Туомас Сандхолм (2014). Вычислительный взлет и падение справедливости . В трудах Двадцать восьмой конференции AAAI по искусственному интеллекту (2014). стр. 1405–1411. CiteSeerX 10.1.1.703.8413 . Ссылка ACM
29. Manurangsi, Pasin; Suksompong, Warut (2020-07-02). «Когда существуют распределения без зависти?». SIAM Journal on Discrete Mathematics . 34 (3): 1505–1521. arXiv : 1811.01630 . doi : 10.1137/19M1279125. S2CID  220363902.