Дробная эффективность Парето

В экономике и информатике используемый дробная эффективность Парето или дробная оптимальность Парето (fPO) — это вариант эффективности Парето, в условиях справедливого распределения дискретных объектов . Распределение объектов называется дискретным , если каждый элемент полностью принадлежит одному агенту; он называется дробным , если некоторые объекты разделены между двумя или более агентами. Дискретное распределение называется Парето-эффективным (PO), если в нем не доминирует по Парето какое-либо дискретное распределение; он называется дробно-эффективным по Парето (fPO), если в нем не доминирует Парето какое-либо дискретное или дробное распределение. ^[1] Таким образом, fPO является более строгим требованием, чем PO: каждое распределение fPO является PO, но не каждое распределение PO является fPO.

Формальные определения

Имеется набор из n агентов и набор из m объектов. Распределение , определяется матрицей m n x , z размером где каждый элемент z [ i i o ] является действительным числом от 0 до 1. Он представляет долю, которую агент получает от объекта o . Для каждого объекта o сумма всех элементов в столбце o равна 1, поскольку выделен весь объект.

Распределение называется дискретным или целым, если все его элементы z [ i , o ] равны 0 или 1; то есть каждый объект полностью принадлежит одному агенту.

Распределение y называется улучшением Парето распределения z , если полезность всех агентов в y не менее велика, чем в z , а полезность некоторых агентов в y строго больше, чем в z . В этом случае мы также говорим, что y доминирует по Парето над z .

Если распределение z не является преобладающим по Парето каким-либо дискретным распределением, то оно называется дискретным Парето-эффективным или просто Парето-эффективным (обычно сокращенно PO ).

Если z вообще не доминирует по Парето при каком-либо распределении - будь то дискретное или дробное - тогда оно называется дробно-эффективным по Парето (обычно сокращенно fPO ).

Примеры

ПО не подразумевает fPO

Предположим, есть два агента и два предмета. Алиса оценивает предметы по 3, 2, а Джордж оценивает их по 4, 1. Пусть z — распределение, при котором первый предмет достается Алисе, а второй — Джорджу. Профиль полезности z равен (3,1).

z является (дискретным) эффективным по Парето. Чтобы убедиться в этом, рассмотрим другие возможные дискретные распределения: их профили полезности — (7,0), (0,3) или (2,4). В любом случае полезность хотя бы одного агента меньше, поэтому никакое дискретное распределение не доминирует над z .
Однако z не является дробно-парето-эффективным. Доминирует распределение y Алисе 1/2 первого предмета и всего второго предмета, а другую 1/2 первого предмета Джорджу; профиль полезности y равен (3,5, 2), поэтому он дает более высокую полезность обоим агентам.

Цена ФПО

Следующий пример ^[1] показывает «цену» fPO. Интегральное распределение, максимизирующее продукт полезностей (также называемое благосостоянием Нэша), — это PE, но не fPO. При этом произведение коммунальных услуг при любом распределении fPO составляет не более 1/3 максимального продукта. Имеется пять товаров {h ₁ ,h ₂ ,g ₁ ,g ₂ ,g ₃ } и 3 агента со следующими значениями (где C — большая константа, а d — малая положительная константа):

Агенты ↓ Товары ⇒	час ₁	час ₂	г ₁	г ₂	г ₃
А ₁	С	С	1	1- д	1- д
A_А2	С	С	1- д	1	1- д
A_А3	С	С	1- д	1- д	1

Распределение интеграла максимального продукта — это {h ₁ }, {h ₂ }, {g ₁ ,g ₂ ,g ₃ }, с произведением $C^{2}\cdot (3-2d)$ . Это не fPO, поскольку в нем преобладает дробное распределение: агент 3 может отдать g ₁ агенту 1 (теряя полезность 1- d ) в обмен на долю h ₁ , которую оба агента оценивают как 1- d /2. Эта сделка строго улучшает благосостояние обоих агентов. Более того, при любом интегральном распределении fPO существует агент A _i , который получает только (максимум) товар g _i - в противном случае можно совершить аналогичную сделку. Следовательно, распределение fPO с максимальным продуктом равно {g ₁ ,h ₁ },{g ₂ ,h ₂ },{g ₃ }, с продуктом $(C+1)^{2}$ . Когда C достаточно велико, а d достаточно мало, соотношение продуктов приближается к 1/3.

Никакое распределение fPO не является почти справедливым

Следующий пример ^[2]^{: Раздел 6.6} показывает, что fPO несовместимо с понятием справедливости, известным как EQx – справедливостью во имя любого блага. Имеется три товара {g ₁ ,g ₂ ,g ₃ } и два агента со следующими значениями (где e — малая положительная константа):

Агенты ↓ Товары ⇒	г ₁	г ₂	г ₃
А ₁	1+ и	( 1+е ) ¹⁰	1
A_А2	1	( 1+е ) ¹⁰	1+ и

Только два дискретных распределения являются EQx:

Агент 1 получает { g ₂ }, а агент 2 получает {g ₁ ,g ₃ }; профиль полезности (( 1+e ) ¹⁰, 2+ д ). Это распределение является PO, но не fPO, поскольку в нем преобладает дробное распределение, дающее агенту 1 пакет {g ₁ , (1-(1+ e ) ⁻⁹) дробь g ₂ } и агенту 2 пучок {g ₃ , (1+ e ) ⁻⁹ доля g ₂ }, в которой профиль полезности равен (( 1+e ) ¹⁰, 2+2е ) .
Агент 1 получает {g ₁ ,g ₃ }, а агент 2 получает { g ₂ }; профиль полезности равен (2+ e , ( 1+e ) ¹⁰). Это распределение является PO, но не fPO, поскольку в нем преобладает дробное распределение, дающее агенту 2 пакет {g ₁ , (1-(1+ e ) ⁻⁹) дробь g ₂ } и агенту 1 пучок {g ₃ , (1+ e ) ⁻⁹ доля g ₂ }, в которой профиль полезности равен (2+2 e, ( 1+e ) ¹⁰).

Тот же пример показывает, что fPO несовместимо с понятием справедливости, известным как EFx – отсутствие зависти ни к чему хорошему. ^[2]^{: Рем.5}

Характеристика

Максимизация взвешенной суммы полезностей

Распределение является fPO тогда и только тогда, когда оно максимизирует взвешенную сумму полезностей агентов. Формально, пусть будет вектором размера n , присваивающим вес wi _i каждому агенту w . Мы говорим, что распределение z является w -максимальным, если выполняется одно из следующих (эквивалентных) свойств:

Каждый объект o назначается только тем агентам i, для которых продукт $w_{i}\cdot v_{i,o}$ является максимальным.
$z_{i,o}>0$ подразумевает $w_{i}v_{i,o}\geq w_{j}v_{j,o}$ для всех агентов i , j и объектов o .
Взвешенная сумма полезностей, $\sum _{i}w_{i}\cdot u_{i}(\mathbf {z} )$ , является максимальным среди всех распределений, где $u_{i}(\mathbf {z} ):=\sum _{o}v_{i,o}\cdot z_{i,o}=$ полезность агента i в распределении z .

Распределение является fPO тогда и только тогда, когда оно w- максимально для некоторого вектора w строго положительных весов. Эту эквивалентность для товаров доказал Негиши. ^[3] и Вариан . ^[4] Доказательство на бэды распространили Бранзей и Сандомирский. ^[5] Позже Сандомирский и Сегал-Халеви распространили его на общие оценки (смеси добра и зла). ^[6]^{: Лем.2.3, Приложение.А}

Нет циклов улучшений на графике потребления

Распределение является fPO тогда и только тогда, когда его направленный граф потребления не содержит циклов с произведением меньше 1. Граф направленного потребления распределения z представляет собой двудольный граф , в котором узлы на одной стороне являются агентами, узлы на другой стороне находятся объекты, а направленные ребра представляют собой обмены: ребро, входящее в агент i, представляет объекты, которые агент i хотел бы принять (товары, которыми он не владеет, или плохие, которыми он владеет); ребро, исходящее от агента i, представляет объекты, которыми агент i может расплатиться (товары, которыми он владеет, или товары, которыми он не владеет). Вес ребра i -> o равен | v _i,o |, Вес ребра i -> o равен | в _я,о | и вес ребра o -> i равен 1/| v _{я, о} |.

Распределение называется злонамеренным , если некоторый объект o потребляется некоторым агентом i с vi _,o ≤ 0, даже если существует другой агент j с vj _,o > 0; или некоторый объект o потребляется некоторым агентом i с vi _,o < 0, даже если существует другой агент j с v _j,o ≥ 0. Очевидно, что каждое злонамеренное распределение можно улучшить по Парето, переместив объект o от агента i к агенту j . Поэтому незлонамеренность является необходимым условием ФПО.

Распределение является fPO тогда и только тогда, когда оно не является злонамеренным, а его направленный график потребления представляет собой ненаправленный цикл, в котором произведение весов меньше 1. Эта эквивалентность была доказана для товаров в контексте разрезания торта. от Барбанеля. ^[7] За бэды его продлили Бранзей и Сандомирский. ^[5] Позже Сандомирский и Сегал-Халеви распространили его на общие оценки (смеси добра и зла). ^[6]^{: Лем.2.1, Приложение.А}

Связь с рыночным равновесием

На рынке Фишера , когда все агенты имеют линейную полезность, любое рыночное равновесие является fPO. Это первая теорема благосостояния . ^[8]

Алгоритмы

Решение о том, является ли данное распределение fPO

Следующий алгоритм можно использовать, чтобы решить, является ли данное распределение z fPO:

Вычислите направленный график потребления z ;
Замените каждый вес его логарифмом;
Используйте алгоритм поиска отрицательного цикла, например алгоритм Беллмана-Форда .
Согласно приведенной выше характеристике, z представляет собой fPO тогда и только тогда, когда отрицательный цикл не обнаружен.

Время выполнения алгоритма составляет O(| V || E |). Здесь, | V |= m + n и | E |≤ mn , где m — количество объектов, а n — количество агентов. Следовательно, fPO можно определить за время O( mn ( m + n )). ^[6]^{: Лем.2.2, Приложение.А}

Альтернативный алгоритм состоит в том, чтобы найти вектор w такой, что данное распределение является w -максимизирующим. Это можно сделать, решив линейную программу . Время выполнения является слабополиномиальным.

Напротив, решение о том, является ли данное дискретное распределение PO, является ко-NP-полным . ^[9] Следовательно, если делитель утверждает, что распределение является fPO, агенты могут эффективно проверить это утверждение; но если делитель утверждает, что распределение является PO, эффективно проверить это утверждение может оказаться невозможным. ^[10]

Нахождение доминирующего распределения fPO

Найти распределение fPO легко. Например, его можно обнаружить с помощью серийной диктатуры : агент 1 забирает все объекты, для которых он имеет положительную ценность; затем агент 2 забирает все оставшиеся объекты, для которых он имеет положительную ценность; и так далее.

Более интересная задача: учитывая начальное распределение z (которое может быть дробным, а не fPO), найти распределение fPO z* , которое является улучшением z по Парето . Эту задачу можно решить для n агентов и m объектов со смешанными (положительными и отрицательными) оценками за сильно полиномиальное время, используя O( n ² м ² ( n + m )) операций. Более того, в вычисленном распределении имеется не более n -1 совместного использования. ^[6]^{: Лем.2.5, Приложение.А}

Если первоначальное распределение z является равным, то окончательное распределение z* является пропорциональным. Следовательно, из приведенной выше леммы следует эффективный алгоритм поиска дробного распределения PROP+fPO с не более чем n -1 общим доступом. Аналогично, если z — неравное разделение, то z* является взвешенно-пропорциональным (пропорциональным для агентов с разными правами). Это подразумевает эффективный алгоритм поиска дробного распределения WPROP+fPO с не более чем n -1 совместным использованием.

Объединение приведенной выше леммы с более продвинутыми алгоритмами может привести за строго полиномиальное время к распределениям, которые являются fPO и свободными от зависти, с не более чем n -1 разделением. ^[6]^{: Кор.2.6}

Перечисление распределений fPO

Существует алгоритм, который перечисляет все графики потребления, соответствующие распределениям fPO. ^[6]^{: Предложение 3.7} Время работы алгоритма $O(3^{{\frac {(n-1)n}{2}}\cdot D}\cdot m^{{\frac {(n-1)n}{2}}+2})$ , где D — степень вырождения экземпляра ( D = m -1 для одинаковых оценок; D = 0 для невырожденных оценок, где для каждых двух агентов отношения ценностей всех m объектов различны). В частности, когда n постоянно и D = 0, время выполнения алгоритма является строго полиномиальным.

Поиск справедливого распределения и распределения fPO

В нескольких недавних работах рассматривалось существование и вычисление дискретного распределения, которое одновременно является fPO и удовлетворяет определенному понятию справедливости .

Бармен и Кришнамурти ^[11] докажите, что дискретное fPO+PROP1 распределение товаров может быть вычислено за сильно полиномиальное время. Они показывают аналогичный результат для дискретного распределения fPO+EF11 , где EF11 означает «без зависти вплоть до добавления одного товара и удаления другого товара».
Aziz, Moulin and Sandomirskiy ^[12] представить алгоритм, который вычисляет дробное распределение fPO+WPROP смешанных объектов (товаров и работ). Он использует линейную программу , которая максимизирует сумму полезностей с учетом пропорциональности. Если базовое допустимое решение найдено (например, с использованием симплексного алгоритма ), то граф потребления полученного распределения является ациклическим. Альтернативно, из полученного графика потребления можно удалить циклы за полиномиальное время. Они также представляют алгоритм, который преобразует дробное распределение fPO+WPROP в дискретное распределение fPO+WPROP1 за строго полиномиальное время.
Бармен, Кришнамурти и Вайш ^[1] докажите, что всегда существует дискретное распределение товаров fPO+EF1 .
Мурхекар и Гарг ^[13] докажите, что дискретное распределение товаров fPO+EF1 может быть найдено за псевдополиномиальное время. Они также доказывают, что, когда все значения положительны, дискретное распределение fPO+EQ1 может существовать и может быть найдено за псевдополиномиальное время. Для k -арных экземпляров (каждый агент имеет не более k различных значений товаров) два приведенных выше результата могут быть вычислены за полиномиальное время. Аналогично, когда количество агентов является постоянным, два приведенных выше результата можно вычислить за полиномиальное время.
Гарг и Мурхекар ^[10] докажите, что, когда матрица оценки содержит только два разных (положительных) значения, дискретное fPO + EFx распределение товаров всегда существует и может быть вычислено за полиномиальное время. Это усиливает предыдущие результаты, которые показали аналогичные результаты для двоичных (0,1) оценок, ^[14]^[15] и для PO+EFx. ^[16] Они показывают аналогичные результаты для PO+EQx .
Гарг, Мурхекар и Цинь ^[17] докажите, что, когда матрица оценки содержит только два разных (отрицательных) значения, дискретное fPO + EF1 распределение работ всегда существует и может быть вычислено за полиномиальное время. Также доказано, что в этом случае дробное распределение fPO+EF (делимых) работ можно вычислить за полиномиальное время.
Фриман, Сикдар, Вайш и Ся ^[2] представить алгоритм с полиномиальным временем для вычисления дискретного распределения, которое является fPO+approximately-EQ1 , для случаев, в которых все оценки являются степенями (1+ e ) для некоторой константы e >0. Они доказывают, что даже в таких случаях (когда имеется как минимум 3 разные оценки) не может быть дискретного распределения fPO+EQx и дискретного распределения fPO+EFx .
Бай и Гольц ^[18] представить алгоритм вычисления весового вектора w, такой, что, когда полезности ui _что каждого агента i выбираются случайным образом и независимо от распределения (которое может быть различным для разных агентов), каждый агент i имеет равную вероятность того, w _i u _i больше, чем w _j u _j всех других агентов. Они показывают, используя лемму Спернера , что вектор уравнивающих весов всегда существует. Когда w — вектор выравнивающих весов, w -максимальное распределение с высокой вероятностью не вызывает зависти . Это означает, что с высокой вероятностью (при подходящих условиях распределения полезности) существует дискретное распределение fPO+EF .

Ссылки

^ Перейти обратно: ^а ^б ^с Барман С., Кришнамурти С.К. и Вайш Р., «Нахождение справедливого и эффективного распределения» , EC '18: Материалы конференции ACM 2018 по экономике и вычислениям , июнь 2018 г.
^ Перейти обратно: ^а ^б ^с Фриман, Руперт; Сикдар, Суджой; Вайш, Рохит; Ся, Лижун (10 августа 2019 г.). «Справедливое распределение неделимых благ» . Материалы 28-й Международной совместной конференции по искусственному интеллекту . IJCAI'19. Макао, Китай: AAAI Press: 280–286. arXiv : 1905.10656 . ISBN 978-0-9992411-4-1 .
^ Негиси, Такаши (1 июня 1960 г.). «Экономика благосостояния и существование равновесия для конкурентоспособной экономики» . Метроэкономика . 12 (2–3): 92–97. дои : 10.1111/j.1467-999X.1960.tb00275.x . ISSN 0026-1386 .
^ Вариан, Хэл Р. (1 апреля 1976 г.). «Две проблемы теории справедливости» . Журнал общественной экономики . 5 (3): 249–260. дои : 10.1016/0047-2727(76)90018-9 . hdl : 1721.1/64180 . ISSN 0047-2727 .
^ Перейти обратно: ^а ^б Брынзей, Симина; Сандомирский, Федор (03.07.2019). «Алгоритмы конкурентного разделения обязанностей». arXiv : 1907.01766 [ cs.GT ].
^ Перейти обратно: ^а ^б ^с ^д ^и ^ж Сандомирский, Федор; Сегал-Халеви, Эрель (01 мая 2022 г.). «Эффективное справедливое разделение с минимальным долевым участием» . Исследование операций . 70 (3): 1762–1782. arXiv : 1908.01669 . дои : 10.1287/opre.2022.2279 . ISSN 0030-364X . S2CID 247922344 .
^ Барбанель, Юлиус Б. (24 января 2005 г.). Геометрия эффективного ярмарочного разделения . Издательство Кембриджского университета. ISBN 978-1-139-44439-2 .
^ Мас-Колелл, Андреу (1995). «Микроэкономическая теория» . 1 . {{cite journal}}: Для цитирования журнала требуется |journal= ( помощь )
^ де Кейзер, Барт; Бувере, Сильвен; Клос, Томас; Чжан, Инцянь (2009). «О сложности эффективности и независтливости при справедливом разделе неделимых товаров с аддитивными преференциями» . В Росси, Франческа; Цукиас, Алексис (ред.). Алгоритмическая теория принятия решений . Конспекты лекций по информатике. Том. 5783. Берлин, Гейдельберг: Springer. стр. 98–110. дои : 10.1007/978-3-642-04428-1_9 . ISBN 978-3-642-04428-1 .
^ Перейти обратно: ^а ^б Гарг, Джугал; Мурхекар, Аникет (2021). «Вычисление справедливого и эффективного распределения с небольшой полезностью» . В Караяннисе, Иоаннис; Хансен, Кристоффер Арнсфельт (ред.). Алгоритмическая теория игр . Конспекты лекций по информатике. Том. 12885. Чам: Springer International Publishing. стр. 345–359. дои : 10.1007/978-3-030-85947-3_23 . ISBN 978-3-030-85947-3 . S2CID 237521642 .
^ Бармен, Сиддхарт; Кришнамурти, Санат Кумар (17 июля 2019 г.). «О близости рынков с интегральными равновесиями» . Материалы конференции AAAI по искусственному интеллекту . 33 (1): 1748–1755. arXiv : 1811.08673 . дои : 10.1609/aaai.v33i01.33011748 . ISSN 2374-3468 . S2CID 53793188 .
^ Азиз, Харис; Мулен, Эрве; Сандомирский, Федор (01.09.2020). «Алгоритм с полиномиальным временем для вычисления оптимального по Парето и почти пропорционального распределения» . Письма об исследованиях операций . 48 (5): 573–578. arXiv : 1909.00740 . дои : 10.1016/j.orl.2020.07.005 . ISSN 0167-6377 . S2CID 202541717 .
^ Мурхекар, Аникет; Гарг, Джугал (18 мая 2021 г.). «О справедливом и эффективном распределении неделимых благ» . Материалы конференции AAAI по искусственному интеллекту . 35 (6): 5595–5602. arXiv : 2204.14229 . дои : 10.1609/aaai.v35i6.16703 . ISSN 2374-3468 . S2CID 235306087 .
^ Дарманн, Андреас; Шауэр, Иоахим (1 декабря 2015 г.). «Максимизация социального благосостояния продукта Нэша при распределении неделимых благ» . Европейский журнал операционных исследований . 247 (2): 548–559. дои : 10.1016/j.ejor.2015.05.071 . ISSN 0377-2217 .
^ Бармен, Сиддхарт; Кришнамурти, Санат Кумар; Вайш, Рохит (9 июля 2018 г.). «Жадные алгоритмы максимизации социального благосостояния Нэша» . Материалы 17-й Международной конференции по автономным агентам и мультиагентным системам . ААМАС '18. Ричленд, Южная Каролина: Международный фонд автономных агентов и мультиагентных систем: 7–13. arXiv : 1801.09046 .
^ Аманатидис, Георгиос; Бирмпас, Георгиос; Филос-Рацикас, Арис; Холлендер, Александрос; Вудурис, Александрос А. (08 апреля 2021 г.). «Максимальное благосостояние Нэша и другие истории об EFX» . Теоретическая информатика . 863 : 69–85. arXiv : 2001.09838 . дои : 10.1016/j.tcs.2021.02.020 . ISSN 0304-3975 . S2CID 232423008 .
^ Гарг, Джугал; Мурхекар, Аникет; Цинь, Джон (18 октября 2021 г.). «Справедливое и эффективное распределение обязанностей по двузначным предпочтениям». arXiv : 2110.09601 [ cs.GT ].
^ Бай, Юши; Гёльц, Пауль (11 февраля 2022 г.). «Распределения без зависти и оптимальные по Парето для агентов с асимметричными случайными оценками». arXiv : 2109.08971 [ cs.GT ].

[:0-1] Перейти обратно: ^а ^б ^с Барман С., Кришнамурти С.К. и Вайш Р., «Нахождение справедливого и эффективного распределения» , EC '18: Материалы конференции ACM 2018 по экономике и вычислениям , июнь 2018 г.

[:4-2] Перейти обратно: ^а ^б ^с Фриман, Руперт; Сикдар, Суджой; Вайш, Рохит; Ся, Лижун (10 августа 2019 г.). «Справедливое распределение неделимых благ» . Материалы 28-й Международной совместной конференции по искусственному интеллекту . IJCAI'19. Макао, Китай: AAAI Press: 280–286. arXiv : 1905.10656 . ISBN 978-0-9992411-4-1 .

[3] Негиси, Такаши (1 июня 1960 г.). «Экономика благосостояния и существование равновесия для конкурентоспособной экономики» . Метроэкономика . 12 (2–3): 92–97. дои : 10.1111/j.1467-999X.1960.tb00275.x . ISSN 0026-1386 .

[4] Вариан, Хэл Р. (1 апреля 1976 г.). «Две проблемы теории справедливости» . Журнал общественной экономики . 5 (3): 249–260. дои : 10.1016/0047-2727(76)90018-9 . hdl : 1721.1/64180 . ISSN 0047-2727 .

[:1-5] Перейти обратно: ^а ^б Брынзей, Симина; Сандомирский, Федор (03.07.2019). «Алгоритмы конкурентного разделения обязанностей». arXiv : 1907.01766 [ cs.GT ].

[:2-6] Перейти обратно: ^а ^б ^с ^д ^и ^ж Сандомирский, Федор; Сегал-Халеви, Эрель (01 мая 2022 г.). «Эффективное справедливое разделение с минимальным долевым участием» . Исследование операций . 70 (3): 1762–1782. arXiv : 1908.01669 . дои : 10.1287/opre.2022.2279 . ISSN 0030-364X . S2CID 247922344 .

[7] Барбанель, Юлиус Б. (24 января 2005 г.). Геометрия эффективного ярмарочного разделения . Издательство Кембриджского университета. ISBN 978-1-139-44439-2 .

[8] Мас-Колелл, Андреу (1995). «Микроэкономическая теория» . 1 . {{cite journal}}: Для цитирования журнала требуется |journal= ( помощь )

[9] де Кейзер, Барт; Бувере, Сильвен; Клос, Томас; Чжан, Инцянь (2009). «О сложности эффективности и независтливости при справедливом разделе неделимых товаров с аддитивными преференциями» . В Росси, Франческа; Цукиас, Алексис (ред.). Алгоритмическая теория принятия решений . Конспекты лекций по информатике. Том. 5783. Берлин, Гейдельберг: Springer. стр. 98–110. дои : 10.1007/978-3-642-04428-1_9 . ISBN 978-3-642-04428-1 .

[:3-10] Перейти обратно: ^а ^б Гарг, Джугал; Мурхекар, Аникет (2021). «Вычисление справедливого и эффективного распределения с небольшой полезностью» . В Караяннисе, Иоаннис; Хансен, Кристоффер Арнсфельт (ред.). Алгоритмическая теория игр . Конспекты лекций по информатике. Том. 12885. Чам: Springer International Publishing. стр. 345–359. дои : 10.1007/978-3-030-85947-3_23 . ISBN 978-3-030-85947-3 . S2CID 237521642 .

[11] Бармен, Сиддхарт; Кришнамурти, Санат Кумар (17 июля 2019 г.). «О близости рынков с интегральными равновесиями» . Материалы конференции AAAI по искусственному интеллекту . 33 (1): 1748–1755. arXiv : 1811.08673 . дои : 10.1609/aaai.v33i01.33011748 . ISSN 2374-3468 . S2CID 53793188 .

[12] Азиз, Харис; Мулен, Эрве; Сандомирский, Федор (01.09.2020). «Алгоритм с полиномиальным временем для вычисления оптимального по Парето и почти пропорционального распределения» . Письма об исследованиях операций . 48 (5): 573–578. arXiv : 1909.00740 . дои : 10.1016/j.orl.2020.07.005 . ISSN 0167-6377 . S2CID 202541717 .

[13] Мурхекар, Аникет; Гарг, Джугал (18 мая 2021 г.). «О справедливом и эффективном распределении неделимых благ» . Материалы конференции AAAI по искусственному интеллекту . 35 (6): 5595–5602. arXiv : 2204.14229 . дои : 10.1609/aaai.v35i6.16703 . ISSN 2374-3468 . S2CID 235306087 .

[14] Дарманн, Андреас; Шауэр, Иоахим (1 декабря 2015 г.). «Максимизация социального благосостояния продукта Нэша при распределении неделимых благ» . Европейский журнал операционных исследований . 247 (2): 548–559. дои : 10.1016/j.ejor.2015.05.071 . ISSN 0377-2217 .

[15] Бармен, Сиддхарт; Кришнамурти, Санат Кумар; Вайш, Рохит (9 июля 2018 г.). «Жадные алгоритмы максимизации социального благосостояния Нэша» . Материалы 17-й Международной конференции по автономным агентам и мультиагентным системам . ААМАС '18. Ричленд, Южная Каролина: Международный фонд автономных агентов и мультиагентных систем: 7–13. arXiv : 1801.09046 .

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

[17] Гарг, Джугал; Мурхекар, Аникет; Цинь, Джон (18 октября 2021 г.). «Справедливое и эффективное распределение обязанностей по двузначным предпочтениям». arXiv : 2110.09601 [ cs.GT ].

[18] Бай, Юши; Гёльц, Пауль (11 февраля 2022 г.). «Распределения без зависти и оптимальные по Парето для агентов с асимметричными случайными оценками». arXiv : 2109.08971 [ cs.GT ].

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

[16]

[17]

[18]