Эгалитарное распределение предметов

Эгалитарное распределение предметов , также называемое максимально-минимальным распределением предметов, представляет собой проблему справедливого распределения предметов , в которой критерий справедливости следует эгалитарному правилу . Цель состоит в том, чтобы максимизировать минимальную ценность агента. То есть среди всех возможных распределений цель состоит в том, чтобы найти распределение, в котором наименьшее значение агента будет как можно большим. В случае, если имеется два или более распределений с одинаковым наименьшим значением, то цель состоит в том, чтобы выбрать среди этих распределений то, в котором второе наименьшее значение является максимально большим, и так далее (по порядку лексиминов ). . Поэтому эгалитарное распределение элементов иногда называют распределением лексиминовых элементов .

Особый случай, в котором ценность каждого предмета j для каждого агента равна либо 0, либо некоторой константе v _j, называется проблемой Санта-Клауса : Санта-Клаус имеет фиксированный набор подарков и хочет распределить их между детьми так, чтобы наименее счастливый ребенок настолько счастлив, насколько это возможно.

Некоторые связанные с этим проблемы:

Многостороннее разделение чисел с целью макс-мин соответствует особому случаю, в котором все агенты имеют одинаковые оценки. Еще более частным случаем является проблема разделения , которая соответствует случаю двух агентов. Даже этот частный случай NP-труден . вообще
несвязанных машин — это двойная задача, цель которой — минимизировать максимальное Планирование значение.
Распределение элементов акций Maximin — это другая проблема, цель которой состоит не в достижении оптимального решения, а в поиске любого решения, в котором каждый агент получает значение, превышающее определенный порог.

Нормализация

Есть два варианта эгалитарного правления: ^{[ 1 ]}

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

Эти два правила эквивалентны, когда оценки агентов уже нормализованы, то есть все агенты присваивают одно и то же значение множеству всех элементов. Однако они могут отличаться при ненормализованных оценках. Например, если есть четыре предмета, Алиса оценивает их как 1,1,1,1, а Джордж оценивает их как 3,3,3,3, то правило абсолютного лексимина даст три предмета Алисе и один предмет Джорджу. , поскольку профиль полезности в этом случае равен (3,3), что является оптимальным. Напротив, правило относительного лексимина даст два элемента каждому агенту, поскольку нормализованный профиль полезности в этом случае, когда общая ценность обоих агентов нормализована до 1, равен (0,5,0,5), что является оптимальным.

Точные алгоритмы

Хотя общая проблема является NP-сложной, небольшие случаи могут быть решены именно с помощью методов программирования в ограничениях .

Бувере и Леметр представляют пять различных алгоритмов для поиска лексимин -оптимальных решений задач дискретного удовлетворения ограничений. ^{[ 2 ]} Они представляют максимальное и минимальное распределение элементов как особый случай.
Далл'Альо и Моска ^{[ 3 ]} дал точный алгоритм ветвей и границ для двух агентов, основанный на адаптации процедуры скорректированного победителя .

Рандомизированные алгоритмы

Демко и Хилл ^{[ 4 ]} представить рандомизированный алгоритм, который обеспечивает ожидаемое эгалитарное распределение предметов.

Алгоритмы аппроксимации

Ниже n — количество агентов, а m — количество элементов.

Для частного случая проблемы Санта-Клауса:

Bansal and Sviridenko ^{[ 5 ]} дал $O(\log {\log {n}}/\log {\log {\log {n}}})$ -Алгоритм аппроксимации, основанный на округлении линейной программы .
Файги ^{[ 6 ]} доказал, что существует алгоритм аппроксимации с постоянным коэффициентом полиномиального времени, но доказательство использовало локальную лемму Ловаса и было неконструктивным.
Асадпур, Файги и Сабери ^{[ 7 ]} дал реальный алгоритм аппроксимации с постоянным коэффициентом, используя сопоставление гиперграфов . Они не смогли доказать, что оно сходится за конечное число шагов.
Аннамалай, Калаитцис и Свенссон ^{[ 8 ]} дал алгоритм 13-аппроксимации с полиномиальным временем.
Дэвис, Ротвосс и Чжан ^{[ 9 ]} улучшил коэффициент аппроксимации до 4, введя ограничения матроида в базовую линейную программу .

В общем случае для агентов с аддитивными оценками :

Безакова и Дэни ^{[ 10 ]} представил два алгоритма. Первый дает $(m-n+1)$ -факторное приближение к оптимальному эгалитарному значению. Второй находит распределение, которое является эгалитарным до одного блага, то есть каждый агент получает свою ценность при оптимальном эгалитарном распределении минус не более одного товара. Их алгоритм основан на предыдущем алгоритме Ленстры, Шмойса и Тардоса. ^{[ 11 ]} который, по сути, находит эгалитарное распределение - до одной работы . Оба алгоритма основаны на схожей идее. Они находят базовое осуществимое решение линейной программы для нахождения дробного эгалитарного распределения и округляют его так, чтобы каждый агент терял не более одного товара или получал не более одной работы.
Асадпур и Сабери ^{[ 12 ]} дал $O({\sqrt {n}}\cdot \log ^{3}n)$ -Алгоритм аппроксимации. Их алгоритм использует итерационный метод округления дробного сопоставления на дереве . Они также обеспечивают лучшие границы, когда разрешено исключить небольшую часть людей из проблемы.

Чакрабарти, Чузой и Ханна ^{[ 13 ]} дал $O(m^{\varepsilon })$ -алгоритм аппроксимации со временем выполнения $O(m^{1/\varepsilon })$ , для любого $\varepsilon \in \Omega \left({\frac {\log \log m}{\log m}}\right)$ . Для особого случая, когда каждый предмет имеет ненулевую полезность не более чем для двух агентов, они предложили алгоритм двухфакторной аппроксимации и доказали, что его трудно приблизить к какому-либо лучшему коэффициенту.
Головин ^{[ 14 ]} дал алгоритм, по которому для любого целого числа $k$ , а $(1-1/k)$ часть агентов получает полезность не менее $OPT/k$ . Этот результат получается в результате округления подходящей релаксации задачи линейного программирования и является наилучшим возможным результатом для этой линейной программы. Он также дал $O({\sqrt {n}})$ -Алгоритм аппроксимации для частного случая с двумя классами товаров.
Когда количество агентов постоянно, существует FPTAS с использованием метода Вёгингера . ^{[ 15 ]}

Для агентов с субмодульными функциями полезности :

Головин ^{[ 14 ]} дал $(m-n+1)$ -алгоритм аппроксимации и некоторые результаты о неаппроксимируемости общих функций полезности.
Гоеманс, Харви, Ивата и Мирркони ^{[ 16 ]} дать $O({\sqrt {m}}\cdot n^{1/4}\cdot \log n\cdot \log ^{3/2}m)$ -алгоритм аппроксимации
Нгуен, Роос и Роте ^{[ 17 ]}^{[ 18 ]} представить некоторые более сильные результаты твердости.

Обычно эгалитарное распределение

Стандартное эгалитарное правило требует, чтобы каждый агент присваивал числовое значение каждому объекту. Часто у агентов есть только порядковые утилиты . Есть два обобщения эгалитарного правила на порядковые условия.

1. Предположим, что агенты имеют порядковый номер в множестве пакетов . При любом дискретном распределении для любого агента i определите r ( i ) как ранг набора агента i, так что r(i)=1, если я получил его лучший набор, r(i)=2, если я получил его второй набор . лучший пакет и т. д. Этот r — вектор размера n (количество агентов). Обычно -эгалитарное распределение — это распределение, которое минимизирует наибольший элемент в r. Процедура уменьшения спроса находит обыкновенно-эгалитарное распределение для любого числа агентов с любым порядком наборов.

2. Предположим, что агенты имеют порядковый номер в множестве элементов . При любом дискретном или дробном распределении для любого агента i и положительного целого числа k определите t ( i , k ) как общую долю, которую агент i получает от своих k самых верхних классов безразличия. Это t — вектор размера не более n * m , где n — количество агентов, а m — количество элементов. Порядково -эгалитарное распределение — это распределение, которое максимизирует вектор t в порядке лексиминов. Алгоритм одновременного приема пищи с равными скоростями приема пищи — это уникальное правило, которое возвращает ординально-эгалитарное распределение. ^{[ 19 ]}

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

Пропорциональность

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

Свобода от зависти

1. Когда все агенты имеют одинаковые оценки с ненулевой предельной полезностью, любое распределение относительного лексимина будет PO и EFX .

Улучшение лексимина, называемое лексимин++, гарантирует EFX (но не PO) с общими идентичными оценками. ^{[ 20 ]}

2. Для двух агентов с аддитивными оценками любое распределение относительного лексимина равно EF1. ^{[ 20 ]}^{: Thm.5.5} Однако:

Распределение абсолютного лексимина может не соответствовать EF1 даже для двух агентов с аддитивными оценками. Например, предположим, что есть четыре товара и два агента, которые оценивают их в {0,1,1,1} и {3,3,3,3}. Уникальное распределение абсолютного лексимина дает {1,1,1} первому агенту и {3} второму агенту, но затем второй агент завидует. ^{[ 21 ]}^: 32
Относительное распределение лексиминов может отличаться от EF1 для трех или более агентов. Например, предположим, что есть четыре товара и три агента, которые оценивают их в {30,0,0,0} {20,5,5,0} и {0,12,12,6}. Обратите внимание, что оценки нормализованы (общее значение равно 30). При распределении лексиминов первый товар должен быть передан агенту 1. Затем второй и третий товары должны быть переданы агенту 2, а товар остается агенту 3. Но тогда агент 3 завидует агенту 2 даже после удаления предмета. ^{[ 22 ]}^: 22

3. Когда все агенты имеют оценки, которые являются матроидными ранговыми функциями (т. е. субмодулярными с двоичными маргиналами), набор абсолютных лексиминовых распределений эквивалентен множеству распределений максимального продукта; все такие распределения имеют максимальную сумму и EF1. ^{[ 21 ]}

4. В контексте неделимого распределения работ (предметов с отрицательной полезностью) с 3 или 4 агентами с аддитивными оценками любое лексимин-оптимальное распределение — это PROP1 и PO; с n агентами с общими одинаковыми оценками любое оптимальное с точки зрения лексимина распределение является EFX. ^{[ 23 ]}

Максимин доля

Когда все агенты имеют одинаковые оценки, эгалитарное распределение по определению дает каждому агенту, по крайней мере, его/ее максиминную долю.

Однако когда агенты имеют разные оценки, проблемы другие. Распределение максимин-доли представляет собой проблему удовлетворения: цель состоит в том, чтобы гарантировать, что каждый агент получит стоимость, превышающую порог идентичных оценок. Напротив, эгалитарное распределение представляет собой проблему оптимизации: цель состоит в том, чтобы придать каждому агенту как можно более высокую ценность. В некоторых случаях итоговое распределение может сильно отличаться. Например, предположим, что есть четыре товара и три агента, которые оценивают их в {3,0,0,0}, {3-2 ε,ε,ε ,0} и {1-2 ε ,1,1,2 ε. } (где ε — малая положительная константа). Обратите внимание, что оценки нормализованы (общее значение равно 3), поэтому абсолютный лексимин и относительный лексимин эквивалентны.

Распределение лексиминов дает профиль полезности (3, 2ε, 2ε ): первый элемент должен перейти к агенту 1 — в противном случае наименьшая полезность равна 0. Затем второй и третий элементы должны перейти к агенту 2 — в противном случае следующая наименьшая полезность составляет ε или меньше; поэтому агент 3 получает только последний элемент.
Значения максимин-доли агентов равны 0, ε , 1. Следовательно, распределение максимин-доли должно дать агенту 3 один из первых трех элементов; некоторыми возможными профилями полезности в этом случае являются (0, 2ε , 1) или (3, ε , 1+ 2ε ).

Пример можно расширить до MMS с 1 из k для любого k >3. Имеется k +1 товаров и три агента, которые оценивают их в { k , 0, ..., 0}, { k -( k -1) ε , ε, ..., ε , 0} и {1- kε. , 1, 1, ..., k ε }. Профиль полезности лексимина должен быть ( k , kε, kε «1 из k» ), а MMS агента 3 равен 1.

Реальное приложение

Правило лексимина использовалось для справедливого распределения неиспользуемых классов в государственных школах между чартерными школами. ^{[ 24 ]}

Ссылки

^ Сегал-Халеви, Эрель; Шиклай, Балаж Р. (01 сентября 2019 г.). «Монотонность и конкурентное равновесие в разрезании тортов» . Экономическая теория . 68 (2): 363–401. arXiv : 1510.05229 . дои : 10.1007/s00199-018-1128-6 . ISSN 1432-0479 . S2CID 179618 .
^ Бувере, Сильвен; Леметр, Мишель (01 февраля 2009 г.). «Вычисление лексимин-оптимальных решений в сетях ограничений» . Искусственный интеллект . 173 (2): 343–364. дои : 10.1016/j.artint.2008.10.010 . ISSN 0004-3702 .
^ Далл'Альо, Марко; Моска, Рафаэле (2007). «Как справедливо распределить леденцы». Математические социальные науки . 54 (3): 218. CiteSeerX 10.1.1.330.2617 . doi : 10.1016/j.mathsocsci.2007.04.008 .
^ Демко, Стивен; Хилл, Теодор П. (1 октября 1988 г.). «Справедливое распределение неделимых объектов» . Математические социальные науки . 16 (2): 145–158. дои : 10.1016/0165-4896(88)90047-9 . ISSN 0165-4896 .
^ Бансал, Нихил; Свириденко, Максим (2006). «Проблема Деда Мороза». Материалы тридцать восьмого ежегодного симпозиума ACM по теории вычислений - STOC '06 . п. 31. дои : 10.1145/1132516.1132522 . ISBN 1595931341 .
^ Файги, Уриэль (20 января 2008 г.). «О распределении, обеспечивающем максимальную справедливость» . Материалы девятнадцатого ежегодного симпозиума ACM-SIAM по дискретным алгоритмам . СОДА '08. Сан-Франциско, Калифорния: Общество промышленной и прикладной математики: 287–293.
^ Асадпур, Араш; Файги, Уриэль; Сабери, Амин (2008). «Санта-Клаус встречает совпадения гиперграфов» . В Гоэле — Ашиш; Янсен, Клаус; Ролим, Хосе ДП; Рубинфельд, Ронитт (ред.). Аппроксимация, рандомизация и комбинаторная оптимизация. Алгоритмы и методы . Конспекты лекций по информатике. Том. 5171. Берлин, Гейдельберг: Springer. стр. 10–20. дои : 10.1007/978-3-540-85363-3_2 . ISBN 978-3-540-85363-3 .
^ Аннамалай, Чидамбарам; Калаитцис, Христос; Свенссон, Ола (26 мая 2017 г.). «Комбинаторный алгоритм ограниченного справедливого распределения по максимуму и минимуму» . Транзакции ACM на алгоритмах . 13 (3): 37:1–37:28. arXiv : 1409.0607 . дои : 10.1145/3070694 . ISSN 1549-6325 . S2CID 14749011 .
^ Дэвис, Сами; Ротвосс, Томас; Чжан, Ихао (18 июля 2018 г.). Сказка о Деде Морозе, гиперграфах и матроидах . Материалы четырнадцатого ежегодного симпозиума ACM-SIAM по дискретным алгоритмам. Общество промышленной и прикладной математики, 2020. стр. 2748–2757. дои : 10.1137/1.9781611975994 .
^ Безакова, Ивона; Дэни, Варша (2005). «Распределение неделимых благ». Биржи ACM SIGecom . 5 (3): 11. CiteSeerX 10.1.1.436.18 . дои : 10.1145/1120680.1120683 . S2CID 1176760 .
^ Ленстра, Ян Карел; Шмойс, Дэвид Б.; Тардос, Ева (1 января 1990 г.). «Аппроксимационные алгоритмы планирования несвязанных параллельных машин» . Математическое программирование . 46 (1): 259–271. дои : 10.1007/BF01585745 . ISSN 1436-4646 . S2CID 52867171 .
^ Асадпур, Араш; Сабери, Амин (1 января 2010 г.). «Аппроксимационный алгоритм максим-минимного справедливого распределения неделимых товаров» . SIAM Journal по вычислительной технике . 39 (7): 2970–2989. дои : 10.1137/080723491 . ISSN 0097-5397 .
^ Чакрабарти, Д.; Чужой Ж.; Ханна, С. (1 октября 2009 г.). «О распределении благ с целью обеспечения максимальной справедливости» . 2009 50-й ежегодный симпозиум IEEE по основам информатики . стр. 107–116. arXiv : 0901.0205 . дои : 10.1109/FOCS.2009.51 . ISBN 978-1-4244-5116-6 . S2CID 165160 .
^ Перейти обратно: ^а ^б Головин, Даниил (2005). «Макс-мин справедливое распределение неделимых благ» . КМУ . Проверено 27 августа 2016 г.
^ Вегингер, Герхард Дж. (1 февраля 2000 г.). «Когда формулировка динамического программирования гарантирует существование полностью полиномиальной схемы аппроксимации времени (FPTAS)?» . ИНФОРМС Журнал по вычислительной технике . 12 (1): 57–74. дои : 10.1287/ijoc.12.1.57.11901 . ISSN 1091-9856 .
^ Гоеманс, Мишель X.; Харви, Николас Дж.А.; Ивата, Сатору; Миррокни, Вахаб (04 января 2009 г.), «Приближение субмодулярных функций повсюду» , Труды ежегодного симпозиума ACM-SIAM по дискретным алгоритмам 2009 г. , Труды Общества промышленной и прикладной математики, стр. 535–544, doi : 10.1137/1.9781611973068.59 , hdl : 1721.1/60671 , ISBN 978-0-89871-680-1 , S2CID 14308006 , получено 22 ноября 2020 г.
^ Нгуен, Чунг Тхань; Роос, Магнус; Роте, Йорг (2013). «Обзор результатов аппроксимации и неаппроксимируемости для оптимизации социального обеспечения при многоагентном распределении ресурсов». Анналы математики и искусственного интеллекта . 68 (1–3): 65–90. CiteSeerX 10.1.1.671.3497 . дои : 10.1007/s10472-012-9328-4 . S2CID 6864410 .
^ Нгуен, Нхан-Там; Нгуен, Чунг Тхань; Роос, Магнус; Роте, Йорг (2013). «Вычислительная сложность и аппроксимируемость оптимизации социального обеспечения при многоагентном распределении ресурсов». Автономные агенты и мультиагентные системы . 28 (2): 256. doi : 10.1007/s10458-013-9224-2 . S2CID 442666 .
^ Богомолная, Анна (01.07.2015). «Случайное задание: новое определение серийного правила» . Журнал экономической теории . 158 : 308–318. дои : 10.1016/j.jet.2015.04.008 . ISSN 0022-0531 .
^ Перейти обратно: ^а ^б Плаут, Бенджамин; Рафгарден, Тим (01 января 2020 г.). «Почти независть при общих оценках» . SIAM Journal по дискретной математике . 34 (2): 1039–1068. arXiv : 1707.04769 . дои : 10.1137/19M124397X . ISSN 0895-4801 . S2CID 216283014 .
^ Перейти обратно: ^а ^б Бенаббу, Наваль; Чакраборти, Митхун; Игараси, Аюми; Зик, Яир (2020). «Нахождение справедливого и эффективного распределения, когда оценки не сходятся». Алгоритмическая теория игр . Конспекты лекций по информатике. Том. 12283. стр. 32–46. arXiv : 2003.07060 . дои : 10.1007/978-3-030-57980-7_3 . ISBN 978-3-030-57979-1 . S2CID 208328700 .
^ Караяннис, Иоаннис; Курокава, Дэвид; Мулен, Эрве; Прокачча, Ариэль Д.; Шах, Нисарг; Ван, Цзюньсин (24 сентября 2019 г.). «Необоснованная справедливость максимального благосостояния Нэша» . Транзакции ACM по экономике и вычислениям . 7 (3): 12:1–12:32. дои : 10.1145/3355902 . ISSN 2167-8375 . S2CID 202729326 .
^ Чен, Синъюй; Лю, Цзыцзе (11 мая 2020 г.). «Справедливость лексимина при распределении неделимых обязанностей». arXiv : 2005.04864 [ cs.GT ].
^ Курокава, Дэвид; Прокачча, Ариэль Д.; Шах, Нисарг (15 июня 2015 г.). «Распределение лексиминов в реальном мире» . Материалы шестнадцатой конференции ACM по экономике и вычислениям . ЕС '15. Портленд, Орегон, США: Ассоциация вычислительной техники. стр. 345–362. дои : 10.1145/2764468.2764490 . ISBN 978-1-4503-3410-5 . S2CID 1060279 .

[1] Сегал-Халеви, Эрель; Шиклай, Балаж Р. (01 сентября 2019 г.). «Монотонность и конкурентное равновесие в разрезании тортов» . Экономическая теория . 68 (2): 363–401. arXiv : 1510.05229 . дои : 10.1007/s00199-018-1128-6 . ISSN 1432-0479 . S2CID 179618 .

[:7-2] Бувере, Сильвен; Леметр, Мишель (01 февраля 2009 г.). «Вычисление лексимин-оптимальных решений в сетях ограничений» . Искусственный интеллект . 173 (2): 343–364. дои : 10.1016/j.artint.2008.10.010 . ISSN 0004-3702 .

[dm07-3] Далл'Альо, Марко; Моска, Рафаэле (2007). «Как справедливо распределить леденцы». Математические социальные науки . 54 (3): 218. CiteSeerX 10.1.1.330.2617 . doi : 10.1016/j.mathsocsci.2007.04.008 .

[4] Демко, Стивен; Хилл, Теодор П. (1 октября 1988 г.). «Справедливое распределение неделимых объектов» . Математические социальные науки . 16 (2): 145–158. дои : 10.1016/0165-4896(88)90047-9 . ISSN 0165-4896 .

[bs06-5] Бансал, Нихил; Свириденко, Максим (2006). «Проблема Деда Мороза». Материалы тридцать восьмого ежегодного симпозиума ACM по теории вычислений - STOC '06 . п. 31. дои : 10.1145/1132516.1132522 . ISBN 1595931341 .

[6] Файги, Уриэль (20 января 2008 г.). «О распределении, обеспечивающем максимальную справедливость» . Материалы девятнадцатого ежегодного симпозиума ACM-SIAM по дискретным алгоритмам . СОДА '08. Сан-Франциско, Калифорния: Общество промышленной и прикладной математики: 287–293.

[7] Асадпур, Араш; Файги, Уриэль; Сабери, Амин (2008). «Санта-Клаус встречает совпадения гиперграфов» . В Гоэле — Ашиш; Янсен, Клаус; Ролим, Хосе ДП; Рубинфельд, Ронитт (ред.). Аппроксимация, рандомизация и комбинаторная оптимизация. Алгоритмы и методы . Конспекты лекций по информатике. Том. 5171. Берлин, Гейдельберг: Springer. стр. 10–20. дои : 10.1007/978-3-540-85363-3_2 . ISBN 978-3-540-85363-3 .

[8] Аннамалай, Чидамбарам; Калаитцис, Христос; Свенссон, Ола (26 мая 2017 г.). «Комбинаторный алгоритм ограниченного справедливого распределения по максимуму и минимуму» . Транзакции ACM на алгоритмах . 13 (3): 37:1–37:28. arXiv : 1409.0607 . дои : 10.1145/3070694 . ISSN 1549-6325 . S2CID 14749011 .

[9] Дэвис, Сами; Ротвосс, Томас; Чжан, Ихао (18 июля 2018 г.). Сказка о Деде Морозе, гиперграфах и матроидах . Материалы четырнадцатого ежегодного симпозиума ACM-SIAM по дискретным алгоритмам. Общество промышленной и прикладной математики, 2020. стр. 2748–2757. дои : 10.1137/1.9781611975994 .

[bd05-10] Безакова, Ивона; Дэни, Варша (2005). «Распределение неделимых благ». Биржи ACM SIGecom . 5 (3): 11. CiteSeerX 10.1.1.436.18 . дои : 10.1145/1120680.1120683 . S2CID 1176760 .

[11] Ленстра, Ян Карел; Шмойс, Дэвид Б.; Тардос, Ева (1 января 1990 г.). «Аппроксимационные алгоритмы планирования несвязанных параллельных машин» . Математическое программирование . 46 (1): 259–271. дои : 10.1007/BF01585745 . ISSN 1436-4646 . S2CID 52867171 .

[12] Асадпур, Араш; Сабери, Амин (1 января 2010 г.). «Аппроксимационный алгоритм максим-минимного справедливого распределения неделимых товаров» . SIAM Journal по вычислительной технике . 39 (7): 2970–2989. дои : 10.1137/080723491 . ISSN 0097-5397 .

[13] Чакрабарти, Д.; Чужой Ж.; Ханна, С. (1 октября 2009 г.). «О распределении благ с целью обеспечения максимальной справедливости» . 2009 50-й ежегодный симпозиум IEEE по основам информатики . стр. 107–116. arXiv : 0901.0205 . дои : 10.1109/FOCS.2009.51 . ISBN 978-1-4244-5116-6 . S2CID 165160 .

[g05-14] Перейти обратно: ^а ^б Головин, Даниил (2005). «Макс-мин справедливое распределение неделимых благ» . КМУ . Проверено 27 августа 2016 г.

[:2-15] Вегингер, Герхард Дж. (1 февраля 2000 г.). «Когда формулировка динамического программирования гарантирует существование полностью полиномиальной схемы аппроксимации времени (FPTAS)?» . ИНФОРМС Журнал по вычислительной технике . 12 (1): 57–74. дои : 10.1287/ijoc.12.1.57.11901 . ISSN 1091-9856 .

[16] Гоеманс, Мишель X.; Харви, Николас Дж.А.; Ивата, Сатору; Миррокни, Вахаб (04 января 2009 г.), «Приближение субмодулярных функций повсюду» , Труды ежегодного симпозиума ACM-SIAM по дискретным алгоритмам 2009 г. , Труды Общества промышленной и прикладной математики, стр. 535–544, doi : 10.1137/1.9781611973068.59 , hdl : 1721.1/60671 , ISBN 978-0-89871-680-1 , S2CID 14308006 , получено 22 ноября 2020 г.

[nrr13-17] Нгуен, Чунг Тхань; Роос, Магнус; Роте, Йорг (2013). «Обзор результатов аппроксимации и неаппроксимируемости для оптимизации социального обеспечения при многоагентном распределении ресурсов». Анналы математики и искусственного интеллекта . 68 (1–3): 65–90. CiteSeerX 10.1.1.671.3497 . дои : 10.1007/s10472-012-9328-4 . S2CID 6864410 .

[nnrr14-18] Нгуен, Нхан-Там; Нгуен, Чунг Тхань; Роос, Магнус; Роте, Йорг (2013). «Вычислительная сложность и аппроксимируемость оптимизации социального обеспечения при многоагентном распределении ресурсов». Автономные агенты и мультиагентные системы . 28 (2): 256. doi : 10.1007/s10458-013-9224-2 . S2CID 442666 .

[19] Богомолная, Анна (01.07.2015). «Случайное задание: новое определение серийного правила» . Журнал экономической теории . 158 : 308–318. дои : 10.1016/j.jet.2015.04.008 . ISSN 0022-0531 .

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

[:1-21] Перейти обратно: ^а ^б Бенаббу, Наваль; Чакраборти, Митхун; Игараси, Аюми; Зик, Яир (2020). «Нахождение справедливого и эффективного распределения, когда оценки не сходятся». Алгоритмическая теория игр . Конспекты лекций по информатике. Том. 12283. стр. 32–46. arXiv : 2003.07060 . дои : 10.1007/978-3-030-57980-7_3 . ISBN 978-3-030-57979-1 . S2CID 208328700 .

[22] Караяннис, Иоаннис; Курокава, Дэвид; Мулен, Эрве; Прокачча, Ариэль Д.; Шах, Нисарг; Ван, Цзюньсин (24 сентября 2019 г.). «Необоснованная справедливость максимального благосостояния Нэша» . Транзакции ACM по экономике и вычислениям . 7 (3): 12:1–12:32. дои : 10.1145/3355902 . ISSN 2167-8375 . S2CID 202729326 .

[23] Чен, Синъюй; Лю, Цзыцзе (11 мая 2020 г.). «Справедливость лексимина при распределении неделимых обязанностей». arXiv : 2005.04864 [ cs.GT ].

[24] Курокава, Дэвид; Прокачча, Ариэль Д.; Шах, Нисарг (15 июня 2015 г.). «Распределение лексиминов в реальном мире» . Материалы шестнадцатой конференции ACM по экономике и вычислениям . ЕС '15. Портленд, Орегон, США: Ассоциация вычислительной техники. стр. 345–362. дои : 10.1145/2764468.2764490 . ISBN 978-1-4503-3410-5 . S2CID 1060279 .

[ 1 ]

[ 2 ]

[ 3 ]

[ 4 ]

[ 5 ]

[ 6 ]

[ 7 ]

[ 8 ]

[ 9 ]

[ 10 ]

[ 11 ]

[ 12 ]

[ 13 ]

[ 14 ]

[ 15 ]

[ 16 ]

[ 17 ]

[ 18 ]

[ 19 ]

[ 20 ]

[ 21 ]

[ 22 ]

[ 23 ]

[ 24 ]