Цены без зависти

Цены без зависти ^{[ 1 ]} это своего рода справедливое распределение предметов . Существует один продавец, владеющий некоторыми товарами, и группа покупателей, заинтересованных в этих товарах. Покупатели имеют разные оценки товаров, и они имеют квазилинейную функцию полезности ; это означает, что полезность, которую агент получает от набора предметов, равна стоимости агента для набора за вычетом общей цены предметов в наборе. Продавец должен определить цену на каждый товар и продать его некоторым покупателям, чтобы не было зависти . Рассматриваются два вида зависти:

Зависть агента означает, что какой-то агент присваивает более высокую полезность (более высокую разницу между стоимостью и ценой) пакету, выделенному другому агенту.
Рыночная зависть означает, что некий агент присваивает любому набору более высокую полезность (более высокую разницу стоимости-цены).

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

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

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

Ценообразование без зависти связано, но не идентично, с другими проблемами справедливого распределения:

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

Результаты

Равновесие Вальраса — это ценообразование без рыночной зависти с дополнительным требованием, что все товары с положительной ценой должны быть распределены (все нераспределенные товары должны иметь нулевую цену). Это максимизирует социальное благосостояние. ^ Однако вальрасовское равновесие может не существовать (оно гарантированно существует только тогда, когда агенты имеют оценки валового замещения ). Более того, даже если он существует, доходы продавцов могут быть низкими. Разрешение продавцу отказаться от некоторых товаров может помочь продавцу получить более высокий доход.

Максимизация дохода продавца при условии отсутствия рыночной зависти.

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

Гурусвами, Хартлайн, Карлин, Кемпе, Кеньон и МакШерри ^{[ 1 ]} (который ввёл термин «ценообразование без зависти» ) изучил два класса функций полезности: единичный спрос и целеустремлённость . Они показали:

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

Балкан , Блюм и Мансур ^{[ 2 ]} изучили два параметра: товары с неограниченным предложением (например, цифровые товары ) и товары с ограниченным предложением . Они показали, что одна цена, выбранная случайным образом, приносит ожидаемый доход, который является нетривиальным приближением к максимальному общественному благосостоянию:

При неограниченном предложении случайная единая цена достигает логарифмического приближения к максимальному социальному благосостоянию. Это верно даже для общих (не монотонных) оценок. Для одного агента и m типов товаров доход составляет не менее 4 log (2 m ) от максимального благосостояния; для n покупателей это как минимум O(log( n ) + log( m )) максимального благосостояния.
При ограниченном предложении для субаддитивных оценок случайная единая цена приносит доход в течение 2 ^{O(√(log n loglog n ))} максимального благосостояния.
В случае с несколькими единицами, когда ни одному покупателю не требуется более 1-ε доли товаров, случайная единая цена обеспечивает доход в пределах O(log n ) от максимального благосостояния.
Нижняя граница для дробно субаддитивных покупателей: любая отдельная цена имеет коэффициент аппроксимации 2. ^{Ом(логарифм ^1/4п )}.

Брист и Криста ^{[ 3 ]} ориентированы на товары с неограниченным предложением и целеустремленными покупателями - каждый покупатель хочет только одну партию товаров. Они показали, что:

Задача является слабо NP-сложной, даже если искомые пакеты вложены .
Проблема APX-сложна даже для очень редких экземпляров.
Существует алгоритм аппроксимации лог-фактора.

Брест ^{[ 4 ]} ориентирован на спросом за единицу товара покупателей с минимальным . У каждого такого покупателя есть подмножество желаемых предметов, и он хотел бы приобрести самый дешевый и доступный желаемый предмет с учетом цен. Он сосредоточился на случае единого бюджета. Он показал, что при некоторых разумных предположениях о сложности:

Задача ценообразования минимальной покупки единицы товара с однородными бюджетами не может быть аппроксимирована за политайм для некоторого ε > 0.
Еще сложнее аппроксимировать несколько более общую задачу, в которой потребители заданы в виде явного распределения вероятностей.
Все результаты применимы и к целеустремленным покупателям.

Чен, Гош и Васильвецкий ^{[ 5 ]} ориентирован на товары с метрикой взаимозаменяемости - покупателя i ценность для товара j равна v _i - c _i,j , а затраты на замену c _i,j образуют метрику . Они показывают, что

Благодаря метрической подстановке задача может быть решена точно за полиномиальное время.
Когда затраты замещения являются лишь приблизительно метрикой (т. е. они приблизительно удовлетворяют неравенству треугольника ), задача становится NP-трудной.

Ван, Лу и Им ^{[ 6 ]} изучите проблему с ограничениями предложения, заданными как система независимости над элементами, например ограничения матроида . Они ориентированы на покупателей с единичным спросом .

Чен и Дэн ^{[ 7 ]} Изучите рынки, состоящие из нескольких товаров: существует m неделимых товаров с единичным предложением каждого и n потенциальных покупателей, каждый из которых хочет купить один товар. Они показывают:

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

Чунг и Свами ^{[ 8 ]} представить алгоритмы поливременной аппроксимации для целеустремленных агентов с ограниченным предложением. Они аппроксимируют доход относительно максимального социального благосостояния.

Хартлайн и Ян ^{[ 9 ]} изучить максимизацию дохода с использованием без предварительной оценки правдивых механизмов . Они также демонстрируют простую структуру ценообразования без зависти и ее связь с правдивой конструкцией механизмов.

Chalermsook, Chuzhoy, Kannan and Khanna ^{[ 10 ]} изучить два варианта задачи. В обоих вариантах у каждого покупателя имеется набор «желаемых предметов».

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

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

Чалермсук, Лаеханукит и Нанонгкай ^{[ 11 ]} доказать трудность аппроксимации варианта, называемого ценообразованием k-гиперграфа . Они также доказывают жесткость минимальной закупки на единицу продукции и целенаправленного ценообразования. ^{[ 12 ]}

Демейн, Файги, Хаджиагайи и Салаватипур ^{[ 13 ]} покажите результаты твердости аппроксимации путем редукции к задаче единственного покрытия .

Аншелевич, Кар и Секар ^{[ 14 ]} изучить ценообразование EF на крупных рынках. Они рассматривают как максимизацию доходов, так и максимизацию благосостояния.

Било, Фламмини и Монако ^{[ 15 ]} изучите ценообразование EF с жесткими требованиями, когда каждый покупатель заинтересован в фиксированном количестве товара.

Колини-Бальдески, Леонарди, Санковски и Чжан ^{[ 16 ]} и Фельдман, Фиат, Леонарди и Санковски ^{[ 17 ]} изучите цены EF с агентами, имеющими бюджет.

Монако, Санковски и Чжан ^{[ 18 ]} изучить многоквартирные рынки. Они изучают максимизацию доходов как при отсутствии рыночной зависти, так и при отсутствии агентской зависти. Они учитывают как цены на товары, так и цены на пакеты.

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

Чен и Рудра ^{[ 19 ]} рассмотрим ослабление вальрасовского равновесия, при котором только победители должны быть свободны от зависти. Цель состоит в том, чтобы максимизировать количество покупателей без зависти.
Алон, Мансур и Тенненхольц ^{[ 20 ]} и Аманатидис, Фулла, Маркакис и Сорнат ^{[ 21 ]} рассмотреть возможность ослабления рыночной свободы от зависти, при которой покупатели организуются в социальную сеть, цены должны быть одинаковыми только между узлами, соседними в сети, а проигравшие не должны завидовать.
Фламмини, Мауро и Тонелли ^{[ 22 ]}^{[ 23 ]} рассмотрите возможность ослабления свободы от рыночной зависти, при которой каждый агент видит только товары соседних агентов (в данной социальной сети).
Эльбассиони, Фуз и Свами ^{[ 24 ]} рассмотрите возможность ослабления свободы агентов от зависти, при которой только победители не должны завидовать. Они рассматривают пакетную цену.
Берчи, Кодацци, Голак и Григорьев ^{[ 25 ]} изучить концепцию динамического ценообразования, при которой цены могут адаптироваться к рыночным условиям для поддержания справедливости среди потребителей, расширяя традиционные представления об отсутствии зависти за пределы статических сценариев.

См. также

Оракул спроса — оракул, который часто используется в алгоритмах ценообразования без зависти.

Ссылки

^ Перейти обратно: ^а ^б Гурусвами, Венкатесан; Хартлайн, Джейсон Д.; Карлин, Анна Р.; Кемпе, Дэвид; Кеньон, Клэр; МакШерри, Фрэнк (23 января 2005 г.). О ценах без зависти, максимизирующих прибыль . Общество промышленной и прикладной математики. стр. 1164–1173. ISBN 978-0-89871-585-9 .
^ Балкан, Мария-Флорина; Блюм, Аврим; Мансур, Ишай (2008). «Ценообразование на товары для максимизации дохода». В Фортнау, Лэнс; Ридл, Джон; Сандхольм, Туомас (ред.). Материалы 9-й конференции ACM по электронной коммерции (EC-2008), Чикаго, Иллинойс, США, 8–12 июня 2008 г. стр. 50–59. дои : 10.1145/1386790.1386802 . ISBN 9781605581699 . S2CID 53038874 .
^ Брист, Патрик; Криста, Петр (22 января 2006 г.). «Целоустремленное неограниченное ценообразование на редкие экземпляры» . Материалы семнадцатого ежегодного симпозиума ACM-SIAM по дискретному алгоритму - SODA '06 . СОДА '06. Майами, Флорида: Общество промышленной и прикладной математики. стр. 1093–1102. дои : 10.1145/1109557.1109678 . ISBN 978-0-89871-605-4 . S2CID 4191038 .
^ Брист, Патрик (2008). «Единые бюджеты и проблема ценообразования без зависти». В Ачето, Лука; Дамгорд, Иван; Голдберг, Лесли Энн; Халльдорссон, Магнус М.; Ингольфсдоттир, Анна; Валукевич, Игорь (ред.). Автоматы, языки и программирование . Конспекты лекций по информатике. Том. 5125. Шпрингер Берлин Гейдельберг. стр. 808–819. CiteSeerX 10.1.1.205.433 . дои : 10.1007/978-3-540-70575-8_66 . ISBN 9783540705758 .
^ Чен, Нин; Гош, Арпита; Васильвицкий, Сергей (2011). «SIAM (Общество промышленной и прикладной математики)». SIAM Journal по вычислительной технике . 40 (3): 623–645. CiteSeerX 10.1.1.193.6235 . дои : 10.1137/080740970 .
^ Я, Сонджин; Лу, Пиньян; Ван, Яджун (2010). «Ценообразование без зависти при общих ограничениях поставок» . В Сабери, Амин (ред.). Интернет и сетевая экономика . Конспекты лекций по информатике. Том. 6484. Берлин, Гейдельберг: Springer. стр. 483–491. дои : 10.1007/978-3-642-17572-5_41 . ISBN 978-3-642-17572-5 .
^ Чен, Нин; Дэн, Сяоте (1 февраля 2014 г.). «Ценообразование без зависти на многотоварных рынках». Транзакции ACM на алгоритмах . 10 (2): 7:1–7:15. CiteSeerX 10.1.1.297.784 . дои : 10.1145/2567923 . ISSN 1549-6325 . S2CID 15309106 .
^ Чунг, М.; Свами, К. (1 октября 2008 г.). «Алгоритмы аппроксимации для целеустремленных задач максимизации прибыли без зависти с ограниченным предложением» . 2008 49-й ежегодный симпозиум IEEE по основам информатики . стр. 35–44. дои : 10.1109/FOCS.2008.15 . ISBN 978-0-7695-3436-7 . S2CID 1318192 .
^ Деванур, Нихил Р.; Хартлайн, Джейсон Д.; Ян, Цици (01 марта 2015 г.). «Зависть к свободе и априорно-свободному конструированию механизмов» . Журнал экономической теории . 156 : 103–143. arXiv : 1212.3741 . дои : 10.1016/j.jet.2014.08.001 . ISSN 0022-0531 . S2CID 17990320 .
^ Чалермсук, Паринья; Чужой, Юлия; Каннан, Сампат; Ханна, Санджив (2012). «Улучшение результатов твердости для решения задач ценообразования максимизации прибыли при неограниченном предложении» . В Гупте — Анупам; Янсен, Клаус; Ролим, Хосе; Серведио, Рокко (ред.). Аппроксимация, рандомизация и комбинаторная оптимизация. Алгоритмы и методы . Конспекты лекций по информатике. Том. 7408. Берлин, Гейдельберг: Springer. стр. 73–84. дои : 10.1007/978-3-642-32512-0_7 . ISBN 978-3-642-32512-0 .
^ Чалермсук, П.; Лаеханукит, Б.; Нанонкай, Д. (1 октября 2013 г.). «Независимый набор, индуцированное сопоставление и ценообразование: связи и жесткость приближения (субэкспоненциальное время)» . 54-й ежегодный симпозиум IEEE по основам информатики , 2013 г. стр. 370–379. arXiv : 1308.2617 . дои : 10.1109/FOCS.2013.47 . ISBN 978-0-7695-5135-7 . S2CID 972321 .
^ Чалермсук, Паринья; Лаеханукит, Бундит; Нанонгкай, Данупон (6 января 2013 г.). «Возвращение к графическим продуктам: жесткость аппроксимации индуцированного сопоставления, размерность частичного набора и многое другое». Материалы ежегодного симпозиума ACM-SIAM по дискретным алгоритмам 2013 г. Слушания. Общество промышленной и прикладной математики. стр. 1557–1576. arXiv : 1212.4129 . дои : 10.1137/1.9781611973105.112 . ISBN 978-1-61197-251-1 . S2CID 6556716 . Проверено 4 апреля 2021 г.
^ Демейн, Эрик Д.; Файги, Уриэль; Хаджиагайи, Мохаммад Таги; Салаватипур, Мохаммад Р. (1 января 2008 г.). «Комбинирование может быть трудным: аппроксимация проблемы уникального покрытия» . SIAM Journal по вычислительной технике . 38 (4): 1464–1483. дои : 10.1137/060656048 . ISSN 0097-5397 . S2CID 12248889 .
^ Аншелевич, Эллиот; Кар, Кошик; Секар, Шреяс (9 августа 2017 г.). «Ценообразование без зависти на крупных рынках: приближение доходов и благосостояния» . Транзакции ACM по экономике и вычислениям . 5 (3): 16:1–16:42. дои : 10.1145/3105786 . ISSN 2167-8375 . S2CID 7008965 .
^ Било, Витторио; Фламмини, Микеле; Монако, Джанпьеро (01 февраля 2017 г.). «Аппроксимация задачи максимизации доходов острыми требованиями» . Теоретическая информатика . 662 : 9–30. arXiv : 1312.3892 . дои : 10.1016/j.tcs.2016.12.002 . ISSN 0304-3975 .
^ Колини-Бальдески, Риккардо; Леонарди, Стефано; Санковский, Петр; Чжан, Цян (2014). «Аукционы с фиксированной ценой и бюджетом без зависти, максимизирующие доход» . В Лю, Те-Янь; Ци, Ци; Йе, Иньюй (ред.). Экономика Интернета и Интернета . Конспекты лекций по информатике. Том. 8877. Чам: Springer International Publishing. стр. 233–246. дои : 10.1007/978-3-319-13129-0_18 . hdl : 11573/754515 . ISBN 978-3-319-13129-0 .
^ Фельдман, Михал ; Фиат, Амос; Леонарди, Стефано; Санковский, Петр (2012). «Аукционы с участием нескольких объектов без зависти и с бюджетом, максимизирующие доход». Материалы 13-й конференции ACM по электронной коммерции . ЭК '12. Нью-Йорк, штат Нью-Йорк, США: ACM. стр. 532–549. дои : 10.1145/2229012.2229052 . ISBN 9781450314152 . S2CID 15639601 .
^ Монако, Джанпьеро; Санковский, Петр; Чжан, Цян (25 июля 2015 г.). «Максимизация доходов, ценообразование на однородные ресурсы без зависти» . Материалы 24-й Международной конференции по искусственному интеллекту . IJCAI'15. Буэнос-Айрес, Аргентина: AAAI Press: 90–96. ISBN 978-1-57735-738-4 .
^ Чен, Нин; Рудра, Атри (1 сентября 2008 г.). «Вальрасово равновесие: жесткость, приближения и разрешимые примеры» . Алгоритмика . 52 (1): 44–64. дои : 10.1007/s00453-007-9103-9 . ISSN 1432-0541 . S2CID 18839423 .
^ Алон, Нога; Мансур, Ишай; Теннегольц, Моше (16 июня 2013 г.). «Дифференциальное ценообразование с неприятием неравенства в социальных сетях» . Материалы четырнадцатой конференции ACM по электронной коммерции . ЭК '13. Филадельфия, Пенсильвания, США: Ассоциация вычислительной техники. стр. 9–24. дои : 10.1145/2492002.2482545 . ISBN 978-1-4503-1962-1 .
^ Аманатидис, Георгиос; Фулла, Питер; Маркакис, Евангелос; Сорнат, Кшиштоф (17 декабря 2019 г.). «Ценообразование в социальных сетях, не допускающее неравенства: алгоритмы аппроксимации и результаты твердости». arXiv : 1606.06664 [ cs.GT ].
^ Фламмини, Микеле; Мауро, Мануэль; Тонелли, Маттео (01 апреля 2019 г.). «О свободе от социальной зависти на многоквартирных рынках» . Искусственный интеллект . 269 : 1–26. дои : 10.1016/j.artint.2018.12.003 . ISSN 0004-3702 . S2CID 19205358 .
^ «Ценообразование, не допускающее неравенства на многоквартирных рынках» . iris.gssi.it. Проверено 5 апреля 2021 г.
^ Эльбасиони, Халед; Фуз, Махмуд; Свами, Чайтанья (2010). «Алгоритмы аппроксимации для нецеленаправленных задач максимизации прибыли с ограниченным предложением» . В Сабери, Амин (ред.). Интернет и сетевая экономика . Конспекты лекций по информатике. Том. 6484. Берлин, Гейдельберг: Springer. стр. 462–472. arXiv : 1312.0137 . дои : 10.1007/978-3-642-17572-5_39 . ISBN 978-3-642-17572-5 . S2CID 14124011 .
^ «Динамическая свобода от зависти в ценообразовании» . Проверено 10 апреля 2024 г.

[:0-1] Перейти обратно: ^а ^б Гурусвами, Венкатесан; Хартлайн, Джейсон Д.; Карлин, Анна Р.; Кемпе, Дэвид; Кеньон, Клэр; МакШерри, Фрэнк (23 января 2005 г.). О ценах без зависти, максимизирующих прибыль . Общество промышленной и прикладной математики. стр. 1164–1173. ISBN 978-0-89871-585-9 .

[2] Балкан, Мария-Флорина; Блюм, Аврим; Мансур, Ишай (2008). «Ценообразование на товары для максимизации дохода». В Фортнау, Лэнс; Ридл, Джон; Сандхольм, Туомас (ред.). Материалы 9-й конференции ACM по электронной коммерции (EC-2008), Чикаго, Иллинойс, США, 8–12 июня 2008 г. стр. 50–59. дои : 10.1145/1386790.1386802 . ISBN 9781605581699 . S2CID 53038874 .

[3] Брист, Патрик; Криста, Петр (22 января 2006 г.). «Целоустремленное неограниченное ценообразование на редкие экземпляры» . Материалы семнадцатого ежегодного симпозиума ACM-SIAM по дискретному алгоритму - SODA '06 . СОДА '06. Майами, Флорида: Общество промышленной и прикладной математики. стр. 1093–1102. дои : 10.1145/1109557.1109678 . ISBN 978-0-89871-605-4 . S2CID 4191038 .

[4] Брист, Патрик (2008). «Единые бюджеты и проблема ценообразования без зависти». В Ачето, Лука; Дамгорд, Иван; Голдберг, Лесли Энн; Халльдорссон, Магнус М.; Ингольфсдоттир, Анна; Валукевич, Игорь (ред.). Автоматы, языки и программирование . Конспекты лекций по информатике. Том. 5125. Шпрингер Берлин Гейдельберг. стр. 808–819. CiteSeerX 10.1.1.205.433 . дои : 10.1007/978-3-540-70575-8_66 . ISBN 9783540705758 .

[5] Чен, Нин; Гош, Арпита; Васильвицкий, Сергей (2011). «SIAM (Общество промышленной и прикладной математики)». SIAM Journal по вычислительной технике . 40 (3): 623–645. CiteSeerX 10.1.1.193.6235 . дои : 10.1137/080740970 .

[6] Я, Сонджин; Лу, Пиньян; Ван, Яджун (2010). «Ценообразование без зависти при общих ограничениях поставок» . В Сабери, Амин (ред.). Интернет и сетевая экономика . Конспекты лекций по информатике. Том. 6484. Берлин, Гейдельберг: Springer. стр. 483–491. дои : 10.1007/978-3-642-17572-5_41 . ISBN 978-3-642-17572-5 .

[7] Чен, Нин; Дэн, Сяоте (1 февраля 2014 г.). «Ценообразование без зависти на многотоварных рынках». Транзакции ACM на алгоритмах . 10 (2): 7:1–7:15. CiteSeerX 10.1.1.297.784 . дои : 10.1145/2567923 . ISSN 1549-6325 . S2CID 15309106 .

[8] Чунг, М.; Свами, К. (1 октября 2008 г.). «Алгоритмы аппроксимации для целеустремленных задач максимизации прибыли без зависти с ограниченным предложением» . 2008 49-й ежегодный симпозиум IEEE по основам информатики . стр. 35–44. дои : 10.1109/FOCS.2008.15 . ISBN 978-0-7695-3436-7 . S2CID 1318192 .

[9] Деванур, Нихил Р.; Хартлайн, Джейсон Д.; Ян, Цици (01 марта 2015 г.). «Зависть к свободе и априорно-свободному конструированию механизмов» . Журнал экономической теории . 156 : 103–143. arXiv : 1212.3741 . дои : 10.1016/j.jet.2014.08.001 . ISSN 0022-0531 . S2CID 17990320 .

[10] Чалермсук, Паринья; Чужой, Юлия; Каннан, Сампат; Ханна, Санджив (2012). «Улучшение результатов твердости для решения задач ценообразования максимизации прибыли при неограниченном предложении» . В Гупте — Анупам; Янсен, Клаус; Ролим, Хосе; Серведио, Рокко (ред.). Аппроксимация, рандомизация и комбинаторная оптимизация. Алгоритмы и методы . Конспекты лекций по информатике. Том. 7408. Берлин, Гейдельберг: Springer. стр. 73–84. дои : 10.1007/978-3-642-32512-0_7 . ISBN 978-3-642-32512-0 .

[11] Чалермсук, П.; Лаеханукит, Б.; Нанонкай, Д. (1 октября 2013 г.). «Независимый набор, индуцированное сопоставление и ценообразование: связи и жесткость приближения (субэкспоненциальное время)» . 54-й ежегодный симпозиум IEEE по основам информатики , 2013 г. стр. 370–379. arXiv : 1308.2617 . дои : 10.1109/FOCS.2013.47 . ISBN 978-0-7695-5135-7 . S2CID 972321 .

[12] Чалермсук, Паринья; Лаеханукит, Бундит; Нанонгкай, Данупон (6 января 2013 г.). «Возвращение к графическим продуктам: жесткость аппроксимации индуцированного сопоставления, размерность частичного набора и многое другое». Материалы ежегодного симпозиума ACM-SIAM по дискретным алгоритмам 2013 г. Слушания. Общество промышленной и прикладной математики. стр. 1557–1576. arXiv : 1212.4129 . дои : 10.1137/1.9781611973105.112 . ISBN 978-1-61197-251-1 . S2CID 6556716 . Проверено 4 апреля 2021 г.

[13] Демейн, Эрик Д.; Файги, Уриэль; Хаджиагайи, Мохаммад Таги; Салаватипур, Мохаммад Р. (1 января 2008 г.). «Комбинирование может быть трудным: аппроксимация проблемы уникального покрытия» . SIAM Journal по вычислительной технике . 38 (4): 1464–1483. дои : 10.1137/060656048 . ISSN 0097-5397 . S2CID 12248889 .

[14] Аншелевич, Эллиот; Кар, Кошик; Секар, Шреяс (9 августа 2017 г.). «Ценообразование без зависти на крупных рынках: приближение доходов и благосостояния» . Транзакции ACM по экономике и вычислениям . 5 (3): 16:1–16:42. дои : 10.1145/3105786 . ISSN 2167-8375 . S2CID 7008965 .

[15] Било, Витторио; Фламмини, Микеле; Монако, Джанпьеро (01 февраля 2017 г.). «Аппроксимация задачи максимизации доходов острыми требованиями» . Теоретическая информатика . 662 : 9–30. arXiv : 1312.3892 . дои : 10.1016/j.tcs.2016.12.002 . ISSN 0304-3975 .

[16] Колини-Бальдески, Риккардо; Леонарди, Стефано; Санковский, Петр; Чжан, Цян (2014). «Аукционы с фиксированной ценой и бюджетом без зависти, максимизирующие доход» . В Лю, Те-Янь; Ци, Ци; Йе, Иньюй (ред.). Экономика Интернета и Интернета . Конспекты лекций по информатике. Том. 8877. Чам: Springer International Publishing. стр. 233–246. дои : 10.1007/978-3-319-13129-0_18 . hdl : 11573/754515 . ISBN 978-3-319-13129-0 .

[17] Фельдман, Михал ; Фиат, Амос; Леонарди, Стефано; Санковский, Петр (2012). «Аукционы с участием нескольких объектов без зависти и с бюджетом, максимизирующие доход». Материалы 13-й конференции ACM по электронной коммерции . ЭК '12. Нью-Йорк, штат Нью-Йорк, США: ACM. стр. 532–549. дои : 10.1145/2229012.2229052 . ISBN 9781450314152 . S2CID 15639601 .

[18] Монако, Джанпьеро; Санковский, Петр; Чжан, Цян (25 июля 2015 г.). «Максимизация доходов, ценообразование на однородные ресурсы без зависти» . Материалы 24-й Международной конференции по искусственному интеллекту . IJCAI'15. Буэнос-Айрес, Аргентина: AAAI Press: 90–96. ISBN 978-1-57735-738-4 .

[19] Чен, Нин; Рудра, Атри (1 сентября 2008 г.). «Вальрасово равновесие: жесткость, приближения и разрешимые примеры» . Алгоритмика . 52 (1): 44–64. дои : 10.1007/s00453-007-9103-9 . ISSN 1432-0541 . S2CID 18839423 .

[20] Алон, Нога; Мансур, Ишай; Теннегольц, Моше (16 июня 2013 г.). «Дифференциальное ценообразование с неприятием неравенства в социальных сетях» . Материалы четырнадцатой конференции ACM по электронной коммерции . ЭК '13. Филадельфия, Пенсильвания, США: Ассоциация вычислительной техники. стр. 9–24. дои : 10.1145/2492002.2482545 . ISBN 978-1-4503-1962-1 .

[21] Аманатидис, Георгиос; Фулла, Питер; Маркакис, Евангелос; Сорнат, Кшиштоф (17 декабря 2019 г.). «Ценообразование в социальных сетях, не допускающее неравенства: алгоритмы аппроксимации и результаты твердости». arXiv : 1606.06664 [ cs.GT ].

[22] Фламмини, Микеле; Мауро, Мануэль; Тонелли, Маттео (01 апреля 2019 г.). «О свободе от социальной зависти на многоквартирных рынках» . Искусственный интеллект . 269 : 1–26. дои : 10.1016/j.artint.2018.12.003 . ISSN 0004-3702 . S2CID 19205358 .

[23] «Ценообразование, не допускающее неравенства на многоквартирных рынках» . iris.gssi.it. Проверено 5 апреля 2021 г.

[24] Эльбасиони, Халед; Фуз, Махмуд; Свами, Чайтанья (2010). «Алгоритмы аппроксимации для нецеленаправленных задач максимизации прибыли с ограниченным предложением» . В Сабери, Амин (ред.). Интернет и сетевая экономика . Конспекты лекций по информатике. Том. 6484. Берлин, Гейдельберг: Springer. стр. 462–472. arXiv : 1312.0137 . дои : 10.1007/978-3-642-17572-5_39 . ISBN 978-3-642-17572-5 . S2CID 14124011 .

[25] «Динамическая свобода от зависти в ценообразовании» . Проверено 10 апреля 2024 г.

[ 1 ]

[ 2 ]

[ 3 ]

[ 4 ]

[ 5 ]

[ 6 ]

[ 7 ]

[ 8 ]

[ 9 ]

[ 10 ]

[ 11 ]

[ 12 ]

[ 13 ]

[ 14 ]

[ 15 ]

[ 16 ]

[ 17 ]

[ 18 ]

[ 19 ]

[ 20 ]

[ 21 ]

[ 22 ]

[ 23 ]

[ 24 ]

[ 25 ]