Цена анархии на аукционах

редактировать

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

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

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

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

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

$P o A = max s ∈ A llocations W elf (s) min s ∈ E quilibrium A llocations W elf (s) {\ displaystyle PoA = {\ frac {\ max _ {s \ in Allocations} Welf (s)} {\ min _ {s \ in EquilibriumAllocations} Welf (s) }}}$ ${\ displaystyle PoA = {\ frac {\ max _ {s \ in Allocations} Welf (s)} { \ min _ {s \ in EquilibriumAllocations} Welf (s)}}}$

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

$P о S = max s ∈ A llocations W elf (s) max s ∈ E quilibrium A llocations W elf (s) {\ displaystyle PoS = {\ frac {\ max _ {s \ in Allocations} Welf (s)} {\ max _ {s \ in EquilibriumAllocations} Welf (s)}}}$ ${\ displaystyle PoS = {\ frac {\ max _ {s \ in Allocations} Welf (s)} {\ max _ {s \ in EquilibriumAllocations} Welf (s) }}}$

Очевидно, $1 ≤ P o S ≤ P o A ≤ ∞ {\ displaystyle 1 \ leq PoS \ leq PoA \ leq \ infty}$ ${\ displaystyle 1 \ leq PoS \ leq PoA \ leq \ infty}$ .

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

Содержание

1 Аукционы отдельных товаров
2 Параллельные аукционы
3 Последовательные аукционы
4 Аукционы с использованием жадных алгоритмов
5 Обобщенные аукционы второй цены
6 Связанные темы
7 Сводная таблица
8 Ссылки

Аукционы отдельных товаров

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

На последовательном аукционе, $m {\ displaystyle m}$ $m$ товаров ar е продаются на последовательных аукционах, один за другим. Обычным типом равновесия является совершенное равновесие в подиграх в чистых стратегиях (SPEPS). Когда покупатели имеют полную информацию (т. Е. Заранее знают последовательность аукционов) и в каждом раунде продается один предмет, SPEPS всегда существует.

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

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

Случай 1: идентичные товары, два покупателя, вторая цена аукционы :

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

Случай 2: добавочные покупатели :

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

Случай 3: спрос на единицу покупателей :

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

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

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

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

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

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

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

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

См.

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

См.

Связанные темы

Исследования PoA на аукционах предоставили понимание других настроек, не связанных с аукционами, например, игры формирования сети

Сводная таблица

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

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

Ссылки