Максимизация благосостояния

Проблема максимизации благосостояния — это задача оптимизации, изучаемая в экономике и информатике . Его цель — разделить набор предметов между агентами с различными функциями полезности так, чтобы благосостояние, определяемое как сумма полезностей агентов, было как можно выше. Другими словами, цель состоит в том, чтобы найти распределение предметов, удовлетворяющее утилитарному правилу . ^[1]

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

Определения

Существует набор M из m элементов и набор N из n агентов. Каждый агент i из N имеет функцию полезности $u_{i}:2^{M}\to \mathbb {R}$ . Функция присваивает реальное значение каждому возможному подмножеству элементов. Обычно предполагается, что функции полезности являются монотонными функциями множества , т. е. $Z_{1}\supseteq Z_{2}$ подразумевает $u_{i}(Z_{1})\geq u_{i}(Z_{2})$ . Также предполагается, что $u_{i}(\emptyset )=0$ . Вместе с монотонностью это означает, что все полезности неотрицательны.

Распределение — это упорядоченное разделение элементов на n непересекающихся подмножеств, по одному подмножеству на каждого агента, обозначаемое $\mathbf {X} =(X_{1},\ldots ,X_{n})$ , такой, что $M=X_{1}\sqcup \cdots \sqcup X_{n}$ Благосостояние распределения представляет собой сумму полезностей агентов: $W(\mathbf {X} ):=\sum _{i\in N}u_{i}(X_{i})$ .

Задача максимизации благосостояния состоит в следующем: найти распределение X , которое максимизирует W ( X ).

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

Присадки

Аддитивный агент имеет функцию полезности, которая является функцией аддитивного множества : для каждого аддитивного агента i и элемента j существует значение $v_{i,j}$ , такой, что $u_{i}(Z)=\sum _{j\in X_{i}}v_{i,j}$ для каждого набора Z предметов. Когда все агенты аддитивны, максимизация благосостояния может быть достигнута с помощью простого алгоритма с полиномиальным временем : дайте каждый элемент j агенту, для которого $v_{i,j}$ является максимальным (произвольно разрывая связи). Проблема усложняется, когда возникают дополнительные ограничения на распределение.

Ограничения справедливости

Кто-то может захотеть максимизировать благосостояние среди всех справедливых распределений , например, без зависти до одного пункта (EF1), пропорционального до одного пункта (PROP1) или справедливого до одного пункта (EQ1). Эта задача является строго NP-трудной, когда n является переменной. При любом фиксированном n ≥ 2 задача является слабо NP-трудной, ^[2]^[3] и имеет псевдополиномиальный алгоритм времени, основанный на динамическом программировании. ^[2] Для n = 2 задача имеет полностью полиномиальную схему аппроксимации . ^[4]

Существуют алгоритмы решения этой проблемы за полиномиальное время, когда имеется мало типов агентов, мало типов элементов или небольшие уровни значений. ^[5] Проблему также можно решить за полиномиальное время, когда аддитивные полезности агентов являются двоичными (значение каждого элемента равно 0 или 1), а также для более общего класса полезностей, называемого обобщенными двоичными . ^[6]

Ограничения Матроида

Другое ограничение на распределение состоит в том, что пакеты должны быть независимыми множествами матроида . Например, каждый пакет должен содержать не более k элементов, где k — фиксированное целое число (это соответствует однородному матроиду ). Или элементы могут быть разделены на категории, и каждый пакет должен содержать не более k _c элементов из каждой категории c (это соответствует матроиду разделения ). В общем, для каждого агента может быть свой матроид, и распределение должно дать каждому агенту i подмножество X _i , которое является независимым набором его собственного матроида.

Максимизация благосостояния с помощью аддитивных полезностей при неоднородных ограничениях на матроиды может быть выполнена за полиномиальное время путем сведения к задаче пересечения взвешенных матроидов . ^[7]

Агенты-заменители

Полезность валового замещения носит более общий характер, чем аддитивная полезность. Максимизация благосостояния с помощью агентов-валт-заменителей может быть достигнута за полиномиальное время. Это происходит потому, что в случае агентов-валрасовиков всегда существует вальрасовское равновесие , которое максимизирует сумму полезностей. ^[8] Вальрасово равновесие можно найти за полиномиальное время.

Субмодульные агенты

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

Твердость

Максимизация благосостояния с помощью субмодульных агентов является NP-трудной задачей. ^[9] Более того, его нельзя аппроксимировать с коэффициентом лучше, чем (1-1/e)≈0,632, если только P=NP. ^[10] Более того, приближение лучше, чем (1-1/e), потребует экспоненциального числа запросов к значению oracle независимо от того, P=NP. ^[11]

Жадный алгоритм

Максимальное благосостояние можно аппроксимировать с помощью следующего жадного алгоритма с полиномиальным временем :

Инициализировать X ₁ = X ₂ = ... = X _n = пусто.
Для каждого элемента g (в произвольном порядке):
- Вычислите для каждого агента предельную полезность g , определяемую как: ui _ui ( Xi ₊ его g ) - ( _для Xi ) _i .
- Отдайте предмет g агенту с наибольшей предельной полезностью.

Леман, Леман и Нисан ^[9] доказать, что жадный алгоритм находит 1/2-факторную аппроксимацию (они отмечают, что этот результат следует из результата Фишера, Немхаузера и Уолси ^[12] относительно максимизации одного субмодулярного нормирования над матроидом). Идея доказательства состоит в следующем. Предположим, алгоритм выделяет элемент g некоторому агенту i . Это способствует благосостоянию на некоторую сумму v , которая представляет собой предельную полезность g для i в данный момент. Предположим, что в оптимальном решении g должен быть передан другому агенту, скажем, k. Рассмотрим, как изменится благосостояние, если мы переместим g из i в k :

Полезность k увеличивается на его предельную полезность g , которая не превышает v . в результате жадного отбора
Предельная полезность оставшегося набора i увеличивается не более чем на v . Это следует из субмодульности: предельная полезность g при добавлении к оставшемуся пакету не может быть выше, чем его предельная полезность при его обработке алгоритмом.

Таким образом, для каждого вклада v в благосостояние алгоритма потенциальный вклад в оптимальное благосостояние может составлять не более 2 v . Следовательно, оптимальное благосостояние не более чем в 2 раза превышает благосостояние алгоритма. Коэффициент 2 является жестким для жадного алгоритма. Например, предположим, что есть два предмета x,y и их оценки таковы:

	{}	{x}	{и}	{х,у}
Алиса	0	1	1	1
Джордж	0	1	0	1

Оптимальным распределением является Алиса: {y}, Джордж: {x} с благосостоянием 2. Но если жадный алгоритм сначала выделит x, он может выделить его Алисе. Тогда, независимо от того, как распределяется y, благосостояние будет только 1.

Алгоритмы, использующие оракул значений

Оракул значений — это оракул, который по заданному набору элементов возвращает значение агента в этот набор. В этой модели:

Добзинский и Шапира ^[13] представить политайм $n/(2n-1)$ -алгоритм аппроксимации и алгоритм аппроксимации (1-1/e)≈0,632 для особого случая, когда полезности агентов являются функциями покрытия множества.
Вондрак ^[14]^{: Раздел 5} и Калинеску, Чекури, Пал и Вондрак ^[15] представить рандомизированный политайм-алгоритм, который с высокой вероятностью находит (1-1/e)-аппроксимацию . Их алгоритм использует непрерывно-жадный алгоритм — алгоритм, расширяющий дробный пакет (пакет, содержащий дробь p _j каждого элемента j ) в жадном направлении (аналогично градиентному спуску ). Их алгоритм должен вычислить ценность дробных пакетов, определяемую как ожидаемое значение пакета, достигаемое, когда каждый элемент j выбирается независимо с вероятностью p _j . В общем, для вычисления стоимости дробного пакета может потребоваться 2 ^м вызовы оракула значений; вычислить приблизительно однако его можно с высокой вероятностью путем случайной выборки . Это приводит к рандомизированному алгоритму, который с высокой вероятностью достигает (1-1/e)-аппроксимации. В случаях, когда дробные пакеты могут быть эффективно оценены (например, когда функции полезности являются функциями покрытия множества), алгоритм можно сделать детерминированным. ^[15]^{: Раздел 5} Они упоминают как открытую проблему, существует ли детерминированный алгоритм поливременной (1-1/e)-аппроксимации для общих субмодулярных функций.

Задача максимизации благосостояния (с n различными субмодулярными функциями) может быть сведена к задаче максимизации одной субмодульной функции множества с учетом матроидного ограничения: ^[9]^[14]^[15] Учитывая экземпляр с m элементами и n агентами, создайте экземпляр с парами m * n (агент, элемент), где каждая пара представляет назначение элемента агенту. Создайте одну функцию, которая присваивает каждому набору пар общее благосостояние соответствующего распределения. Можно показать, что если все полезности субмодулярны, то и эта функция благосостояния также субмодулярна. Эту функцию следует максимизировать с учетом ограничения матроида раздела , гарантируя, что каждый элемент будет назначен не более чем одному агенту.

Алгоритмы, использующие оракул спроса

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

Добзинский и Шапира ^[13] представить алгоритм поливременной (1-1/e)-аппроксимации.
Файги и Вондрак ^[16] улучшите это до (1-1/e+ε) для некоторого небольшого положительного ε (это не противоречит приведенному выше результату твердости, поскольку результат твердости использует только оракул значений; в примерах твердости сам оракул спроса потребует экспоненциально много запросы) .

Субаддитивные агенты

Когда утилиты агентов являются субаддитивными функциями множества (более общими, чем субмодульными), ${\frac {1}{m^{1/2-\epsilon }}}$ аппроксимация потребует экспоненциального количества запросов значений. ^[11]

Файги ^[17] представляет собой способ округления любого дробного решения ЛП-релаксации этой проблемы до приемлемого решения с благосостоянием, составляющим не менее 1/2 значения дробного решения. Это дает 1/2-приближение для общих субаддитивных агентов и (1-1/e)-приближение для частного случая дробно-субаддитивных оценок.

Супераддитивные агенты

Когда утилиты агентов являются супераддитивными функциями множества (более общими, чем супермодульными), ${\frac {(\log m)^{1+\epsilon }}{m}}$ аппроксимация потребует суперполиномиального количества запросов значений. ^[11]

Целеустремленные агенты

хочет Целеустремленный агент только определенный набор предметов. Для каждого целеустремленного агента i существует требуемый набор D _i значение Vi _и > 0, такие, что $u_{i}(Z)={\begin{cases}V_{i}&Z\supseteq D_{i}\\0&{\text{otherwise}}\end{cases}}$ . То есть агент получает фиксированную положительную полезность тогда и только тогда, когда его пакет содержит требуемый набор.

Максимизация благосостояния с помощью целеустремленных агентов является NP-трудной задачей, даже если $V_{i}=1$ для всех я . В этом случае задача эквивалентна упаковке множества , которая, как известно, NP-трудна. Более того, он не может быть аппроксимирован каким-либо постоянным множителем (в отличие от случая субмодулярных агентов). ^[18] Самый известный алгоритм аппроксимирует его с точностью до коэффициента $O({\sqrt {m}})$ . ^[19]

Генеральные агенты

Когда агенты могут иметь произвольные монотонные функции полезности (включая дополнительные предметы ), максимизацию благосостояния трудно аппроксимировать с точностью до коэффициента $O(n^{1/2-\epsilon })$ для любого $\epsilon >0$ . ^[20] Однако существуют алгоритмы, основанные на поиске в пространстве состояний , которые очень хорошо работают на практике. ^[21]

См. также

Ссылки

^ Вондрак, Ян (17 мая 2008 г.). «Оптимальное приближение субмодульной задачи благосостояния в модели оракула ценностей» . Материалы сорокового ежегодного симпозиума ACM по теории вычислений . СТОК '08. Нью-Йорк, штат Нью-Йорк, США: Ассоциация вычислительной техники. стр. 67–74. дои : 10.1145/1374376.1374389 . ISBN 978-1-60558-047-0 . S2CID 170510 .
^ Перейти обратно: ^а ^б Азиз, Харис; Хуан, Синь; Маттеи, Николас; Сегал-Халеви, Эрель (13 октября 2022 г.). «Расчет благосостояния: максимизация справедливого распределения неделимых благ» . Европейский журнал операционных исследований . 307 (2): 773–784. arXiv : 2012.03979 . дои : 10.1016/j.ejor.2022.10.013 . ISSN 0377-2217 . S2CID 235266307 .
^ Сунь, Анькан; Чен, Бо; Доан, Суан Винь (2 декабря 2022 г.). «Справедливость и максимизация благосостояния при распределении неделимых предметов» . Автономные агенты и мультиагентные системы . 37 (1): 8. дои : 10.1007/s10458-022-09587-1 . ISSN 1573-7454 . S2CID 254152607 .
^ Бу, Сяолинь; Ли, Цзыхао; Лю, Шэнсинь; Сун, Цзясинь; Тао, Бяошуай (27 мая 2022 г.). «О сложности максимизации социального благосостояния в рамках справедливого распределения неделимых благ». arXiv : 2205.14296 [ cs.GT ].
^ Нгуен, Чунг Тхань; Роте, Йорг (1 января 2023 г.). «Справедливое и эффективное распределение с небольшим количеством типов агентов, несколькими типами элементов или небольшими уровнями стоимости» . Искусственный интеллект . 314 : 103820. doi : 10.1016/j.artint.2022.103820 . ISSN 0004-3702 . S2CID 253430435 .
^ Камачо, Франклин; Фонсека-Дельгадо, Ригоберто; Пино Перес, Рамон; Тапиа, Гвидо (07 ноября 2022 г.). «Обобщенные двоичные функции полезности и справедливое распределение» . Математические социальные науки . 121 : 50–60. doi : 10.1016/j.mathsocsci.2022.10.003 . ISSN 0165-4896 . S2CID 253411165 .
^ Дрор, Амитей; Фельдман, Михал; Сегал-Халеви, Эрель (24 апреля 2022 г.). «О справедливом разделении при гетерогенных ограничениях матроида». arXiv : 2010.07280 [ cs.GT ].
^ Келсо, А.С.; Кроуфорд, вице-президент (1982). «Подбор должностей, формирование коалиций и валовые заменители». Эконометрика . 50 (6): 1483. дои : 10.2307/1913392 . JSTOR 1913392 .
^ Перейти обратно: ^а ^б ^с Леманн, Бенни; Леманн, Дэниел; Нисан, Ноам (14 октября 2001 г.). «Комбинаторные аукционы с убывающей предельной полезностью» . Материалы 3-й конференции ACM по электронной коммерции . ЕС '01. Нью-Йорк, штат Нью-Йорк, США: Ассоциация вычислительной техники. стр. 18–28. arXiv : cs/0202015 . дои : 10.1145/501158.501161 . ISBN 978-1-58113-387-5 . S2CID 2241237 .
^ Хот, Субхаш; Липтон, Ричард Дж.; Маркакис, Евангелос; Мехта, Араньяк (1 сентября 2008 г.). «Результаты неаппроксимируемости для комбинаторных аукционов с субмодулярными функциями полезности» . Алгоритмика . 52 (1): 3–18. дои : 10.1007/s00453-007-9105-7 . ISSN 1432-0541 . S2CID 7600128 .
^ Перейти обратно: ^а ^б ^с Миррокни, Вахаб; Шапира, Майкл; Вондрак, Ян (8 июля 2008 г.). «Жесткие нижние границы теории информации для максимизации благосостояния на комбинаторных аукционах» . Материалы 9-й конференции ACM по электронной коммерции . ЕС '08. Нью-Йорк, штат Нью-Йорк, США: Ассоциация вычислительной техники. стр. 70–77. дои : 10.1145/1386790.1386805 . ISBN 978-1-60558-169-9 . S2CID 556774 .
^ Фишер, ML; Немхаузер, Г.Л.; Уолси, Луизиана (1978), Балински, М.Л.; Хоффман, А.Дж. (ред.), «Анализ приближений для максимизации субмодулярных функций множества — II» , Полиэдральная комбинаторика: Посвящается памяти Д. Р. Фулкерсона , Берлин, Гейдельберг: Springer, стр. 73–87, doi : 10.1007/bfb0121195 , ISBN 978-3-642-00790-3 , получено 26 февраля 2023 г.
^ Перейти обратно: ^а ^б Добзинский, Шахар; Шапира, Майкл (22 января 2006 г.). «Улучшенный алгоритм аппроксимации комбинаторных аукционов с субмодульными участниками торгов» . Материалы семнадцатого ежегодного симпозиума ACM-SIAM по дискретному алгоритму - SODA '06 . СОДА '06. США: Общество промышленной и прикладной математики. стр. 1064–1073. дои : 10.1145/1109557.1109675 . ISBN 978-0-89871-605-4 . S2CID 13108913 .
^ Перейти обратно: ^а ^б Вондрак, Ян (17 мая 2008 г.). «Оптимальное приближение субмодульной задачи благосостояния в модели оракула ценностей» . Материалы сорокового ежегодного симпозиума ACM по теории вычислений . СТОК '08. Нью-Йорк, штат Нью-Йорк, США: Ассоциация вычислительной техники. стр. 67–74. дои : 10.1145/1374376.1374389 . ISBN 978-1-60558-047-0 . S2CID 170510 .
^ Перейти обратно: ^а ^б ^с Калинеску, Груя; Чекури, Чандра; Пал, Мартин; Вондрак, Ян (1 января 2011 г.). «Максимизация монотонной субмодульной функции с учетом ограничения матроида» . SIAM Journal по вычислительной технике . 40 (6): 1740–1766. дои : 10.1137/080733991 . ISSN 0097-5397 .
^ Файги, Уриэль; Вондрак, Ян (9 декабря 2010 г.). «Субмодульная проблема благосостояния с запросами спроса» . Теория вычислений . 6 : 247–290. дои : 10.4086/toc.2010.v006a011 .
^ Файги, Уриэль (21 мая 2006 г.). «О максимизации благосостояния при субаддитивности функций полезности» . Материалы тридцать восьмого ежегодного симпозиума ACM по теории вычислений . СТОК '06. Нью-Йорк, штат Нью-Йорк, США: Ассоциация вычислительной техники. стр. 41–50. дои : 10.1145/1132516.1132523 . ISBN 978-1-59593-134-4 . S2CID 11504912 .
^ Хазан, Элад; Сафра, Шмуэль; Шварц, Одед (2006). «О сложности аппроксимации упаковки k -множеств». Вычислительная сложность . 15 (1): 20–39. CiteSeerX 10.1.1.352.5754 . дои : 10.1007/s00037-006-0205-6 . МР 2226068 . S2CID 1858087 . . См., в частности, стр. 21: «Максимальная клика (и, следовательно, максимальное независимое множество и упаковка максимального множества) не может быть аппроксимирована с точностью до $O(n^{1-\epsilon })$ если только NP ⊂ ZPP».
^ Халлдорссон, Магнус М.; Краточвил, Ян; Телле, Ян Арне (1998). Независимые множества с ограничениями на доминирование . 25-й Международный коллоквиум по автоматам, языкам и программированию. Конспекты лекций по информатике. Том. 1443. Шпрингер-Верлаг. стр. 176–185.
^ Леманн, Дэниел; Очаллаган, Лиадан Ита; Шохам, Йоав (1 сентября 2002 г.). «Выявление истины на приблизительно эффективных комбинаторных аукционах» . Журнал АКМ . 49 (5): 577–602. дои : 10.1145/585265.585266 . ISSN 0004-5411 . S2CID 52829303 .
^ Сандхольм, Туомас; Сури, Субхаш (30 июля 2000 г.). «Улучшенные алгоритмы оптимального определения победителя в комбинаторных аукционах и обобщениях» . Материалы семнадцатой национальной конференции по искусственному интеллекту и двенадцатой конференции по инновационным применениям искусственного интеллекта . АААИ Пресс: 90–97. ISBN 978-0-262-51112-4 .

[1] Вондрак, Ян (17 мая 2008 г.). «Оптимальное приближение субмодульной задачи благосостояния в модели оракула ценностей» . Материалы сорокового ежегодного симпозиума ACM по теории вычислений . СТОК '08. Нью-Йорк, штат Нью-Йорк, США: Ассоциация вычислительной техники. стр. 67–74. дои : 10.1145/1374376.1374389 . ISBN 978-1-60558-047-0 . S2CID 170510 .

[:0-2] Перейти обратно: ^а ^б Азиз, Харис; Хуан, Синь; Маттеи, Николас; Сегал-Халеви, Эрель (13 октября 2022 г.). «Расчет благосостояния: максимизация справедливого распределения неделимых благ» . Европейский журнал операционных исследований . 307 (2): 773–784. arXiv : 2012.03979 . дои : 10.1016/j.ejor.2022.10.013 . ISSN 0377-2217 . S2CID 235266307 .

[3] Сунь, Анькан; Чен, Бо; Доан, Суан Винь (2 декабря 2022 г.). «Справедливость и максимизация благосостояния при распределении неделимых предметов» . Автономные агенты и мультиагентные системы . 37 (1): 8. дои : 10.1007/s10458-022-09587-1 . ISSN 1573-7454 . S2CID 254152607 .

[4] Бу, Сяолинь; Ли, Цзыхао; Лю, Шэнсинь; Сун, Цзясинь; Тао, Бяошуай (27 мая 2022 г.). «О сложности максимизации социального благосостояния в рамках справедливого распределения неделимых благ». arXiv : 2205.14296 [ cs.GT ].

[5] Нгуен, Чунг Тхань; Роте, Йорг (1 января 2023 г.). «Справедливое и эффективное распределение с небольшим количеством типов агентов, несколькими типами элементов или небольшими уровнями стоимости» . Искусственный интеллект . 314 : 103820. doi : 10.1016/j.artint.2022.103820 . ISSN 0004-3702 . S2CID 253430435 .

[6] Камачо, Франклин; Фонсека-Дельгадо, Ригоберто; Пино Перес, Рамон; Тапиа, Гвидо (07 ноября 2022 г.). «Обобщенные двоичные функции полезности и справедливое распределение» . Математические социальные науки . 121 : 50–60. doi : 10.1016/j.mathsocsci.2022.10.003 . ISSN 0165-4896 . S2CID 253411165 .

[7] Дрор, Амитей; Фельдман, Михал; Сегал-Халеви, Эрель (24 апреля 2022 г.). «О справедливом разделении при гетерогенных ограничениях матроида». arXiv : 2010.07280 [ cs.GT ].

[kc82-8] Келсо, А.С.; Кроуфорд, вице-президент (1982). «Подбор должностей, формирование коалиций и валовые заменители». Эконометрика . 50 (6): 1483. дои : 10.2307/1913392 . JSTOR 1913392 .

[:1-9] Перейти обратно: ^а ^б ^с Леманн, Бенни; Леманн, Дэниел; Нисан, Ноам (14 октября 2001 г.). «Комбинаторные аукционы с убывающей предельной полезностью» . Материалы 3-й конференции ACM по электронной коммерции . ЕС '01. Нью-Йорк, штат Нью-Йорк, США: Ассоциация вычислительной техники. стр. 18–28. arXiv : cs/0202015 . дои : 10.1145/501158.501161 . ISBN 978-1-58113-387-5 . S2CID 2241237 .

[10] Хот, Субхаш; Липтон, Ричард Дж.; Маркакис, Евангелос; Мехта, Араньяк (1 сентября 2008 г.). «Результаты неаппроксимируемости для комбинаторных аукционов с субмодулярными функциями полезности» . Алгоритмика . 52 (1): 3–18. дои : 10.1007/s00453-007-9105-7 . ISSN 1432-0541 . S2CID 7600128 .

[:2-11] Перейти обратно: ^а ^б ^с Миррокни, Вахаб; Шапира, Майкл; Вондрак, Ян (8 июля 2008 г.). «Жесткие нижние границы теории информации для максимизации благосостояния на комбинаторных аукционах» . Материалы 9-й конференции ACM по электронной коммерции . ЕС '08. Нью-Йорк, штат Нью-Йорк, США: Ассоциация вычислительной техники. стр. 70–77. дои : 10.1145/1386790.1386805 . ISBN 978-1-60558-169-9 . S2CID 556774 .

[12] Фишер, ML; Немхаузер, Г.Л.; Уолси, Луизиана (1978), Балински, М.Л.; Хоффман, А.Дж. (ред.), «Анализ приближений для максимизации субмодулярных функций множества — II» , Полиэдральная комбинаторика: Посвящается памяти Д. Р. Фулкерсона , Берлин, Гейдельберг: Springer, стр. 73–87, doi : 10.1007/bfb0121195 , ISBN 978-3-642-00790-3 , получено 26 февраля 2023 г.

[:3-13] Перейти обратно: ^а ^б Добзинский, Шахар; Шапира, Майкл (22 января 2006 г.). «Улучшенный алгоритм аппроксимации комбинаторных аукционов с субмодульными участниками торгов» . Материалы семнадцатого ежегодного симпозиума ACM-SIAM по дискретному алгоритму - SODA '06 . СОДА '06. США: Общество промышленной и прикладной математики. стр. 1064–1073. дои : 10.1145/1109557.1109675 . ISBN 978-0-89871-605-4 . S2CID 13108913 .

[:5-14] Перейти обратно: ^а ^б Вондрак, Ян (17 мая 2008 г.). «Оптимальное приближение субмодульной задачи благосостояния в модели оракула ценностей» . Материалы сорокового ежегодного симпозиума ACM по теории вычислений . СТОК '08. Нью-Йорк, штат Нью-Йорк, США: Ассоциация вычислительной техники. стр. 67–74. дои : 10.1145/1374376.1374389 . ISBN 978-1-60558-047-0 . S2CID 170510 .

[:4-15] Перейти обратно: ^а ^б ^с Калинеску, Груя; Чекури, Чандра; Пал, Мартин; Вондрак, Ян (1 января 2011 г.). «Максимизация монотонной субмодульной функции с учетом ограничения матроида» . SIAM Journal по вычислительной технике . 40 (6): 1740–1766. дои : 10.1137/080733991 . ISSN 0097-5397 .

[16] Файги, Уриэль; Вондрак, Ян (9 декабря 2010 г.). «Субмодульная проблема благосостояния с запросами спроса» . Теория вычислений . 6 : 247–290. дои : 10.4086/toc.2010.v006a011 .

[17] Файги, Уриэль (21 мая 2006 г.). «О максимизации благосостояния при субаддитивности функций полезности» . Материалы тридцать восьмого ежегодного симпозиума ACM по теории вычислений . СТОК '06. Нью-Йорк, штат Нью-Йорк, США: Ассоциация вычислительной техники. стр. 41–50. дои : 10.1145/1132516.1132523 . ISBN 978-1-59593-134-4 . S2CID 11504912 .

[18] Хазан, Элад; Сафра, Шмуэль; Шварц, Одед (2006). «О сложности аппроксимации упаковки k -множеств». Вычислительная сложность . 15 (1): 20–39. CiteSeerX 10.1.1.352.5754 . дои : 10.1007/s00037-006-0205-6 . МР 2226068 . S2CID 1858087 . . См., в частности, стр. 21: «Максимальная клика (и, следовательно, максимальное независимое множество и упаковка максимального множества) не может быть аппроксимирована с точностью до $O(n^{1-\epsilon })$ если только NP ⊂ ZPP».

[19] Халлдорссон, Магнус М.; Краточвил, Ян; Телле, Ян Арне (1998). Независимые множества с ограничениями на доминирование . 25-й Международный коллоквиум по автоматам, языкам и программированию. Конспекты лекций по информатике. Том. 1443. Шпрингер-Верлаг. стр. 176–185.

[20] Леманн, Дэниел; Очаллаган, Лиадан Ита; Шохам, Йоав (1 сентября 2002 г.). «Выявление истины на приблизительно эффективных комбинаторных аукционах» . Журнал АКМ . 49 (5): 577–602. дои : 10.1145/585265.585266 . ISSN 0004-5411 . S2CID 52829303 .

[21] Сандхольм, Туомас; Сури, Субхаш (30 июля 2000 г.). «Улучшенные алгоритмы оптимального определения победителя в комбинаторных аукционах и обобщениях» . Материалы семнадцатой национальной конференции по искусственному интеллекту и двенадцатой конференции по инновационным применениям искусственного интеллекта . АААИ Пресс: 90–97. ISBN 978-0-262-51112-4 .

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

[16]

[17]

[18]

[19]

[20]

[21]