Цена анархии на аукционах - Price of anarchy in auctions

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

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

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

Однако на практике не всегда возможно использовать правдивые механизмы. Например, механизм VCG может быть слишком сложным для понимания участниками, может потребоваться слишком много времени для вычислений аукционисту и может иметь другие недостатки.^[1] На практике часто используются неправдивые механизмы, и интересно подсчитать, сколько общественного благосостояния теряется из-за этой неправдивости.

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

${\displaystyle PoA={\frac {\max _{s\in Allocations}Welf(s)}{\min _{s\in EquilibriumAllocations}Welf(s)}}}$

Связанное с этим понятие - Цена стабильности (PoS), который измеряет соотношение между оптимальным социальным благосостоянием и социальным благосостоянием в Лучший равновесие:

${\displaystyle PoS={\frac {\max _{s\in Allocations}Welf(s)}{\max _{s\in EquilibriumAllocations}Welf(s)}}}$

Очевидно ${\displaystyle 1\leq PoS\leq PoA\leq \infty }$.

Когда есть полная информация (каждый агент знает оценки всех других агентов), общий тип равновесия - это равновесие по Нэшу - чистое или смешанное. Когда есть неполная информация, общий тип равновесия Равновесие Байеса-Нэша. В последнем случае принято говорить о Байесовская цена анархии, или BPoA.

Разовые аукционы

В аукцион первой цены для одного элемента равновесие по Нэшу всегда эффективно, поэтому PoA и PoS равны 1.

В аукцион второй цены существует равновесие по Нэшу, в котором агенты сообщают правдиво; он эффективен, поэтому PoS равен 1. Однако PoA неограничен! Например,^[2]предположим, что есть два игрока: Алиса оценивает предмет как а и Боб как б, с а>б.

Существует «хорошее» равновесие по Нэшу, при котором Алиса делает ставку а и ставки Боба б; Алиса получает товар и платит б. Социальное благосостояние а, что оптимально.

Однако также существует «плохое» равновесие по Нэшу, при котором Алиса предлагает 0, а Боб, например, а+1; Боб получает товар и ничего не платит. Это равновесие, поскольку Алиса не хочет перебивать цену Боба. Социальное благосостояние б. Следовательно, PoA а/б, который неограничен.

Этот результат кажется излишне пессимистичным:

• Во-первых, на аукционе второй цены это слабодоминирующая стратегия чтобы каждый агент сообщил о своей истинной оценке. Если предположить, что агенты следуют своим доминирующим стратегиям, то PoA равно 1.
• Более того, это доминирующая стратегия чтобы каждый агент сообщал о любой стоимости, превышающей его истинную оценку.

Поэтому обычно анализируют PoA под нет завышенной цены предположение - агент не делает ставки выше его истинной оценки. При этом предположении PoA аукциона с одним товаром составляет 1.

Параллельные аукционы

На параллельном (одновременном) аукционе, ${\displaystyle m}$ товары продаются одновременно одной и той же группе ${\displaystyle n}$ участников. В отличие от комбинаторный аукцион - в котором агенты могут делать ставки на пакеты предметов, здесь агенты могут делать ставки только на отдельные предметы независимо от других. То есть стратегия агента - это вектор ставок, одна ставка на товар. PoA зависит от типа оценок покупателей и от типа аукциона, используемого для каждой отдельной позиции.

Случай 1: субмодульный покупатели, вторичные аукционы, полная информация:^[2]

• Существует чистый равновесие по Нэшу с оптимальным социальным обеспечением. Следовательно, PoS равен 1.
• Можно рассчитать за полиномиальное время чистое равновесие по Нэшу с общественным благосостоянием, по крайней мере, половиной оптимального. Следовательно, цена «полиномиальной устойчивости» не превосходит 2.
• PoA не ограничен, как уже было показано в примере с одним элементом выше. Однако под сильная, не завышенная цена предположение (сумма заявок любого покупателя на любой пакет не более чем стоимость этого пакета для покупателя), PoA не превышает 2. Последний результат также имеет место, когда оценки покупателей равны дробно субаддитивный.

Случай 2: дробно субаддитивный покупатели, аукцион 2-й цены, неполная информация.^[2] Предполагая сильная, не завышенная цена, любое (смешанное) равновесие Байеса-Нэша в ожидании достигает как минимум 1/2 оптимального благосостояния; следовательно, BPoA не превышает 2. Этот результат не зависит от общего априора агентов.

Случай 3: субаддитив покупатели, аукционы второй цены. ^[3] Под сильная, не завышенная цена предположение:

• При наличии полной информации благополучие каждого чистого равновесия по Нэшу составляет как минимум 1/2 от оптимума, поэтому PoA не превышает 2.
• При неполной информации существует равновесие Байеса-Нэша с уровнем благосостояния. менее 1/2 оптимальная, поэтому BPoA больше 2.
• BPoA не более ${\displaystyle 2\log {m}}$, куда ${\displaystyle m}$ количество элементов. Эта гарантия также действительна для грубо коррелированное равновесие - и, следовательно, к частным случаям смешанного равновесия по Нэшу и коррелированное равновесие.
• Обе вышеуказанные верхние границы PoA постепенно ухудшаются, когда допущения субаддитивности и отсутствия завышенной цены ослаблены. Например: если мы предположим, что каждый игрок завышает ставку не более чем на какой-то постоянный коэффициент, тогда PoA увеличивается не более чем на постоянный коэффициент.

Случай 4: Обычные (монотонные) покупатели, аукционы первой цены, полная информация:^[4]

• Набор чистых равновесий по Нэшу в игре - это в точности Вальрасовские равновесия (ценовые равновесия) рынка.^[5]
• Поскольку такие равновесия социально оптимальны (по первая теорема благосостояния ), PoA чистых равновесий по Нэшу равен 1. К сожалению, таких равновесий может не быть.
• Всегда существует смешанное равновесие по Нэшу (при выборе правильного правила разделения). Однако это не обязательно социально оптимально. PoA может достигать ${\displaystyle \Omega ({\sqrt {m}})}$, и даже PoS может достигать ${\displaystyle \Omega ({\sqrt {m}}/\log {m})}$.
  • Этот результат также распространяется на аукционы второй цены, даже если слабая цена без завышения предположение.^[6]
• PoA не более ${\displaystyle O(m)}$.
• Когда все оценки субаддитивны, PoA не более ${\displaystyle O(\log {m})}$.
• Когда все оценки ${\displaystyle \beta }$-дробно субаддитивный, PoA не более ${\displaystyle 2\beta }$ (в частности, для покупателей XOS PoA не больше 2).
• Последние три границы верны и для грубо коррелированных равновесий; они НЕ требуют допущения "не завышать цену".

Случай 5: Обычные покупатели, аукционы второй цены, полная информация.^[7] При общих оценках (которые могут иметь взаимодополняемость) предположение о строгом отсутствии завышенной цены является слишком сильным, поскольку оно не позволяет покупателям предлагать высокие цены на комплекты дополнительных товаров. Например, если оценка покупателя составляет 100 долларов за пару обуви, но 1 доллар за каждую обувь в отдельности, то строгое предположение о недопустимости завышения цены не позволяет ему предлагать цену более 1 доллара за каждую обувь, так что у него мало шансов выиграть пару. . Поэтому его заменяют на слабая цена без завышения Это означает, что условие отсутствия завышенных ставок выполняется только для пакета, который в конечном итоге выигрывает агент (т. е. сумма ставок покупателя на его выделенный пакет не превышает его стоимости для этого конкретного пакета). Исходя из этого предположения о слабой недопустимой переоценке:

• Набор чистых равновесий по Нэшу в игре - это в точности условное ценовое равновесие рынка.^[8]
• Поскольку такие равновесия являются наполовину социально оптимальными (достигают по крайней мере половины максимального общественного благосостояния), PoA чистого равновесия по Нэшу не превышает 2. К сожалению, таких равновесий может не существовать.

Случай 6: Обычные покупатели, аукционы первой цены, неполная информация. ^[4] Для любого общего приора:

• BPoA не более ${\displaystyle O(mn)}$.
• Когда все оценки ${\displaystyle \beta }$-фракционно субаддитивный, BPoA не более ${\displaystyle 4\beta }$ (в частности, для покупателей XOS BPoA составляет не более 2, а для субаддитивных покупателей это ${\displaystyle O(\log m)}$).

Случай 7: Субаддитивные покупатели, неполная информация: ^[6]

• Когда товары продаются на аукционах первой цены, BPoA составляет не более 2.
• Когда товары продаются на аукционах второй цены, BPoA составляет не более 4. Это верно как при предположении о строгом отсутствии завышенных ставок (сумма ставок любого покупателя на любой комплект не превышает стоимости этого набора для покупатель), и под слабая цена без завышения допущение (ожидаемая сумма выигравших предложений любого покупателя не превышает ожидаемой суммы выигрыша этого покупателя).

Последовательные аукционы

В последовательный аукцион, ${\displaystyle m}$ предметы продаются на последовательных аукционах, один за другим. Общий тип равновесия - это подигра идеальное равновесие в чистых стратегиях (SPEPS). Когда покупатели имеют полную информацию (т.е. они знают последовательность аукционов заранее) и в каждом раунде продается один предмет, SPEPS всегда существует.^{[9]:872–874}

PoA этого SPEPS зависит от функций полезности участников торгов и от типа аукциона, используемого для каждой отдельной позиции.

Первые пять результатов ниже применимы к операторам с полная информация (все агенты знают оценки всех других агентов):

Случай 1. Одинаковые товары, два покупателя, аукционы второй цены.:^[10][11]

• Когда хотя бы один покупатель имеет вогнутую функцию оценки (убывающая отдача ), PoA не более ${\displaystyle 1/(1-e)\approx 1.58}$.
• Численные результаты показывают, что, когда есть много участников торгов с вогнутыми функциями оценки, потеря эффективности уменьшается по мере увеличения числа пользователей.

Случай 2: добавка покупатели:^{[9] :885}

• С аукционами второй цены PoA неограничен - благосостояние в SPEPS может быть сколь угодно низким!

Случай 3: удельный спрос покупатели:^[9]

• При аукционах первой цены PoA составляет не более 2 - благосостояние в SPEPS всегда составляет не менее половины от максимума (если разрешены смешанные стратегии, PoA не превышает 4).
• С аукционами второй цены PoA снова становится неограниченным.

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

Случай 4: субмодульный покупатели^[9] (обратите внимание, что добавочная и единичная потребность являются частными случаями субмодульных):

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

Случай 5: добавка + UD.^[12] Предположим, что одни участники торгов имеют аддитивные оценки, а другие - оценки спроса на единицу продукции. В последовательности аукционов первой цены PoA может быть не менее ${\displaystyle \min(n,m)}$, куда м это количество предметов и п количество участников торгов. Более того, неэффективные равновесия сохраняются даже при повторном исключении слабо доминируемых стратегий. Это подразумевает линейную неэффективность для многих естественных условий, включая:

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

Случай 6: покупатели единичного спроса, неполная информация, аукционы первой цены:^[13] BPoA не превышает 3.

Аукционы с использованием жадных алгоритмов

Увидеть ^[14]

Обобщенные аукционы второй цены

Увидеть ^[15][16][17]

похожие темы

Исследования PoA на аукционах позволили получить представление о других параметрах, не связанных с аукционами, таких как сетевые игры ^[18]

Таблица результатов

[Неполная таблица - содержит только параллельные аукционы - необходимо заполнить]

Мульти-аукцион	Единый аукцион	Информация	Оценки	Предположения	PoA	Поз	Комментарии
Параллельный	2-я цена	полный	субмодульный	сильная, не завышенная цена	2	чистый: 1 [всегда существует]	[2]
Параллельный	2-я цена	Байесовский	XOS	сильная, не завышенная цена	2		[2]
Параллельный	2-я цена	полный	субаддитив	сильная, не завышенная цена	2		[3]
Параллельный	2-я цена	Байесовский	субаддитив	сильная, не завышенная цена	> 2, <2 log (м)		[3]
Параллельный	1-я цена	полный	монотонный	Никто	чистый: 1 [если существует]		Чистый NE = WE. [4]
Параллельный	1-я цена	полный	монотонный	Никто	смешанный: ${\displaystyle \Omega ({\sqrt {m}})}$	${\displaystyle \Omega ({\sqrt {m}}/\log {m})}$	[4]
Параллельный	1-я цена	Байесовский	монотонный	Никто	${\displaystyle O(mn)}$	${\displaystyle \Omega ({\sqrt {m}}/\log {m})}$	[4]
Параллельный	2-я цена	полный	монотонный	слабая цена без завышения	чистый: 2 [если существует]		Чистый NE = условный WE[7]
Параллельный	1-я цена	Байесовский	субаддитив	Никто	2	${\displaystyle \Omega ({\sqrt {m}}/\log {m})}$	[6]
Параллельный	2-я цена	Байесовский	субаддитив	слабая / сильная-без завышенной ставки	4		[6]

Рекомендации

1. Ausubel, Lawrence M .; Милгром, Пол (2005). "Прекрасный, но одинокий аукцион Викри". Комбинаторные аукционы. п. 17. CiteSeerX  10.1.1.120.7158. Дои:10.7551 / mitpress / 9780262033428.003.0002. ISBN  9780262033428.
2. Христодулу, Джордж; Ковач, Аннамария; Шапира, Майкл (2016). «Байесовские комбинаторные аукционы». Журнал ACM. 63 (2): 1. CiteSeerX  10.1.1.721.5346. Дои:10.1145/2835172.
3. Бхавалкар, Кшипра; Roughgarden, Тим (2011). «Гарантии благосостояния комбинаторных аукционов с торгами по позициям». Материалы двадцать второго ежегодного симпозиума ACM-SIAM по дискретным алгоритмам. п. 700. Дои:10.1137/1.9781611973082.55. ISBN  978-0-89871-993-2.
4. Хасидим, Авинатан; Каплан, Хаим; Мансур, Ишай; Нисан, Ноам (2011). «Неценовые равновесия на рынках дискретных товаров». Материалы 12-й конференции ACM по электронной коммерции - EC '11. п. 295. arXiv:1103.3950. Дои:10.1145/1993574.1993619. ISBN  9781450302616.
5. Аналогичный результат для случая полной информации уже был представлен Бихчандани, Сушил (1999). «Аукционы неоднородных предметов». Игры и экономическое поведение. 26 (2): 193–220. Дои:10.1006 / игра.1998.0659.: "В одновременных аукционах первой цены набор вальрасовских равновесных распределений содержит набор чистых распределений по Нэшу по стратегии, который, в свою очередь, содержит набор строгих вальрасовских равновесных распределений. Следовательно, чистые стратегии по Нэшу равновесия (если они существуют) эффективны. Смешанная стратегия равновесия по Нэшу может быть неэффективной. На одновременных аукционах второй цены любое эффективное распределение может быть реализовано как результат равновесия чистой стратегии по Нэшу, если существует вальрасовское равновесие ».
6. Фельдман, Михал; Фу, Ху; Гравин, Ник; Люсьер, Брендан (2013). «Одновременные аукционы (почти) эффективны». Материалы 45-го ежегодного симпозиума ACM по теории вычислений - STOC '13. п. 201. arXiv:1209.4703. Дои:10.1145/2488608.2488634. ISBN  9781450320290.
7. Фу, Ху; Клейнберг, Роберт; Лави, Рон (2012). «Результаты условного равновесия посредством процессов возрастания цен с применением комбинаторных аукционов с торгами по позициям». Материалы 13-й конференции ACM по электронной торговле - EC '12. п. 586. CiteSeerX  10.1.1.230.6195. Дои:10.1145/2229012.2229055. ISBN  9781450314152.
8. А условное равновесие цен является релаксацией вальрасовского равновесия цен: в последнем случае каждый агент должен получить оптимальный пакет с учетом вектора цен; в первом случае каждый агент должен получить набор, который слабо лучше, чем пустой набор, и слабо лучше, чем любой содержащий его набор (но может быть хуже, чем его подмножества). Последний гарантированно существует в основном для брутто-замещающие оценки, в то время как первый гарантированно существует для гораздо более широкого класса оценок.
9. Леме, Ренато Паес; Сыргканис, Василис; Тардос, Ева (2012). «Последовательные аукционы и внешние эффекты». Материалы двадцать третьего ежегодного симпозиума ACM-SIAM по дискретным алгоритмам. п. 869. arXiv:1108.2452. Дои:10.1137/1.9781611973099.70. ISBN  978-1-61197-210-8.
10. Пэ, Джунджик; Бейгман, Эял; Берри, Рэндалл; Хониг, Майкл; Вохра, Ракеш (2008). «Последовательные аукционы по пропускной способности и мощности для распределения распределенного спектра». Журнал IEEE по избранным областям коммуникаций. 26 (7): 1193. CiteSeerX  10.1.1.616.8533. Дои:10.1109 / JSAC.2008.080916.
11. Пэ, Джунджик; Бейгман, Эял; Берри, Рэндалл; Хониг, Майкл Л .; Вохра, Ракеш (2009). «Об эффективности последовательных аукционов по совместному использованию спектра». 2009 Международная конференция по теории игр для сетей. п. 199. Дои:10.1109 / gamenets.2009.5137402. ISBN  978-1-4244-4176-1.
12. Фельдман, Михал; Люсьер, Брендан; Сыргканис, Василис (2013). «Пределы эффективности последовательных аукционов». Интернет и Интернет-экономика. Конспект лекций по информатике. 8289. п. 160. arXiv:1309.2529. Дои:10.1007/978-3-642-45046-4_14. ISBN  978-3-642-45045-7.
13. Сыргканис, Василис; Тардос, Ева (2012). «Байесовские последовательные аукционы». Материалы 13-й конференции ACM по электронной торговле - EC '12. п. 929. arXiv:1206.4771. Дои:10.1145/2229012.2229082. ISBN  9781450314152.
14. Б. Люсье и А. Бородин (2010). Цена анархии для жадных аукционов. SODA 2010.
15. Леме, Ренато Паес; Тардос, Ева (2010). "Чистая цена анархии и цена Байеса-Нэша для всеобщего аукциона второй цены". 2010 51-й ежегодный симпозиум IEEE по основам компьютерных наук. п. 735. Дои:10.1109 / FOCS.2010.75. ISBN  978-1-4244-8525-3.
16. Люсьер, Брендан; Паес Леме, Ренато (2011). «Аукционы GSP с коррелированными типами». Материалы 12-й конференции ACM по электронной коммерции - EC '11. п. 71. CiteSeerX  10.1.1.232.5139. Дои:10.1145/1993574.1993587. ISBN  9781450302616.
17. Карагианнис, Иоаннис; Какламанис, Христос; Канеллопулос, Панайотис; Киропулу, Мария (2011). «Об эффективности равновесий на обобщенных аукционах второй цены». Материалы 12-й конференции ACM по электронной коммерции - EC '11. п. 81. Дои:10.1145/1993574.1993588. ISBN  9781450302616.
18. Алон, Нога; Эмек, Юваль; Фельдман, Михал; Тенненхольц, Моше (2012). «Байесовское невежество». Теоретическая информатика. 452: 1–11. Дои:10.1016 / j.tcs.2012.05.017.