Аукцион Викри – Кларка – Гроувса - Википедия - Vickrey–Clarke–Groves auction

А Аукцион Викри-Кларка-Гроувса (VCG) представляет собой тип аукциона с запечатанными предложениями для нескольких позиций. Участники торгов подают заявки, в которых указывается их оценка товаров, не зная предложений других участников торгов. Аукционная система распределяет предметы в социально оптимальный способ: он взимает с каждого человека ущерб, который они причиняют другим участникам торгов.^[1] Это дает участникам торгов стимул предложить свою истинную оценку, гарантируя, что оптимальная стратегия для каждого участника торгов заключается в том, чтобы предлагать свою истинную стоимость товаров; это может быть подорвано сговором участников торгов и, в частности, в некоторых случаях, когда один участник торгов делает несколько предложений под разными именами. Это обобщение Викри аукцион для нескольких предметов.

Аукцион назван в честь Уильям Викри,^[2] Эдвард Х. Кларк,^[3] и Теодор Гровс^[4] за их статьи, которые последовательно обобщали эту идею.

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

Интуитивное описание

Рассмотрим аукцион, на котором продается набор идентичных товаров. Участники торгов могут принять участие в аукционе, объявив максимальную цену, которую они готовы заплатить за получение N товаров. Каждый покупатель может подать более одной ставки, поскольку его готовность платить на единицу может отличаться в зависимости от общего количества получаемых единиц. Участники торгов не могут видеть заявки других людей в любой момент, поскольку они запечатаны (видимы только для системы аукциона). После того, как все ставки сделаны, аукцион закрывается.

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

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

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

Формальное описание

Обозначение

Для любого набора выставленных на аукционе лотов ${ Displaystyle М = {т_ {1}, ldots, т_ {м} }}$ и любой набор участников торгов ${ Displaystyle N = {b_ {1}, ldots, b_ {n} }}$ , позволять ${ Displaystyle V_ {N} ^ {M}}$ быть социальной ценностью аукциона VCG для данной комбинации ставок. То есть, насколько каждый человек ценит только что выигранные предметы, в сумме для всех. Если они не выиграют, ценность предмета равна нулю. Участнику торгов ${ displaystyle b_ {i}}$ и предмет ${ displaystyle t_ {j}}$ , пусть заявка участника аукциона будет ${ displaystyle v_ {i} (t_ {j})}$ . Обозначение ${ Displaystyle A setminus B}$ означает набор элементов A, которые не являются элементами B.

Назначение

Участник торгов ${ displaystyle b_ {i}}$ чья ставка на предмет ${ displaystyle t_ {j}}$ это "перебид", а именно ${ displaystyle v_ {i} (t_ {j})}$ , выигрывает предмет, но платит ${ displaystyle V_ {N setminus {b_ {i} }} ^ {M} -V_ {N setminus {b_ {i} }} ^ {M setminus {t_ {j} }} }$ , который представляет собой социальную цену своей победы, которую несут остальные агенты.

Объяснение

Действительно, множество участников торгов, кроме ${ displaystyle b_ {i}}$ является ${ displaystyle N setminus {b_ {i} }}$ . Когда товар ${ displaystyle t_ {j}}$ доступен, они могли бы получить благосостояние ${ displaystyle V_ {N setminus {b_ {i} }} ^ {M}.}$ Выигрыш предмета ${ displaystyle b_ {i}}$ сокращает набор доступных предметов до ${ displaystyle M setminus {t_ {j} }}$ однако, так что достижимое благосостояние теперь ${ displaystyle V_ {N setminus {b_ {i} }} ^ {M setminus {t_ {j} }}}$ . Таким образом, разница между двумя уровнями благосостояния - это потеря достижимого благосостояния, которую понесли остальные участники торгов, как и было предсказано. данный победитель ${ displaystyle b_ {i}}$ получил предмет ${ displaystyle t_ {j}}$ . Это количество зависит от предложений остальных агентов и неизвестно агенту. ${ displaystyle b_ {i}}$ .

Полезность победителя

Победитель торгов, ставка которого является истинной стоимостью ${ displaystyle A}$ для пункта ${ displaystyle t_ {j}}$ , ${ displaystyle v_ {i} (t_ {j}) = A,}$ извлекает максимальную пользу ${ Displaystyle A- left (V_ {N setminus {b_ {i} }} ^ {M} -V_ {N setminus {b_ {i} }} ^ {M setminus {t_ { j} }} right).}$

Примеры

Два предмета, три участника торгов

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

Претендент А хочет одно яблоко и готов заплатить за это яблоко 5 долларов.
Претендент B хочет одно яблоко и готов заплатить за него 2 доллара.
Претендент C хочет два яблока и готов заплатить 6 долларов за оба яблока, но не заинтересован в покупке только одного без другого.

Во-первых, результат аукциона определяется максимизацией ставок: яблоки поступают к участнику торгов A и участнику торгов B, поскольку их комбинированная ставка в размере 5 долларов США + 2 доллара США = 7 долларов США превышает ставку за два яблока участника торгов C, который готов заплатить только 6 долларов. Таким образом, после аукциона цена, достигнутая участником аукциона A, составляет 5 долларов, участником торгов B - 2 доллара, а участником торгов C - 0 долларов (поскольку участник торгов C ничего не получает). Обратите внимание, что определение победителей - это, по сути, проблема с рюкзаком.

Далее формула определения выплат дает:

Участнику торгов А: Плата за победу, требуемую для A, определяется следующим образом: Во-первых, в аукционе, исключающем участника торгов A, результат максимизации общественного благосостояния назначит оба яблока участнику торгов C на общую социальную ценность в 6 долларов. Затем общая социальная ценность первоначального аукциона. без учета стоимости A вычисляется как 7 - 5 долларов = 2 доллара. Наконец, вычтите второе значение из первого. Таким образом, оплата, необходимая для A, составляет 6 долларов - 2 доллара = 4 доллара.
Участнику торгов B: Как и в предыдущем случае, лучший результат для аукциона, исключающего участника торгов B, назначает оба яблока участнику торгов C за 6 долларов. Общая социальная ценность первоначального аукциона минус часть B составляет 5 долларов. Таким образом, платеж, требуемый от B, составляет 6–5 долларов = 1 доллар.
Наконец, платеж для участника торгов C составляет ((5 долларов + 2 доллара) - (5 долларов + 2 доллара)) = 0 долларов.

После аукциона A становится на 1 доллар лучше, чем раньше (заплатив 4 доллара, чтобы получить 5 долларов полезности), B - на 1 доллар лучше, чем раньше (заплатив 1 доллар, чтобы получить 2 доллара полезности), и C нейтрально (ничего не выиграв).

Два участника торгов

Предположим, что есть два участника торгов, ${ displaystyle b_ {1}}$ и ${ displaystyle b_ {2}}$ , два предмета, ${ displaystyle t_ {1}}$ и ${ displaystyle t_ {2}}$ , и каждый участник торгов может получить по одной позиции. Мы позволяем ${ displaystyle v_ {я, j}}$ быть участником торгов ${ displaystyle b_ {i}}$ оценка товара ${ displaystyle t_ {j}}$ . Предполагать ${ displaystyle v_ {1,1} = 10}$ , ${ displaystyle v_ {1,2} = 5}$ , ${ displaystyle v_ {2,1} = 5}$ , и ${ displaystyle v_ {2,2} = 3}$ . Мы видим, что оба ${ displaystyle b_ {1}}$ и ${ displaystyle b_ {2}}$ предпочел бы получить товар ${ displaystyle t_ {1}}$ ; однако социально оптимальное задание дает элемент ${ displaystyle t_ {1}}$ к участнику торгов ${ displaystyle b_ {1}}$ (так что их достигнутое значение ${ displaystyle 10}$ ) и элемент ${ displaystyle t_ {2}}$ к участнику торгов ${ displaystyle b_ {2}}$ (так что их достигнутое значение ${ displaystyle 3}$ ). Следовательно, общее достигнутое значение составляет ${ displaystyle 13}$ , что оптимально.

Если человек ${ displaystyle b_ {2}}$ не участвовали в аукционе, человек ${ displaystyle b_ {1}}$ все равно будет назначен ${ displaystyle t_ {1}}$ , и, следовательно, человек ${ displaystyle b_ {1}}$ больше ничего не получишь. Текущий результат ${ displaystyle 10}$ ; следовательно ${ displaystyle b_ {2}}$ взимается ${ displaystyle 10-10 = 0}$ .

Если человек ${ displaystyle b_ {1}}$ не было на аукционе, ${ displaystyle t_ {1}}$ будет назначен ${ displaystyle b_ {2}}$ , и будет иметь оценку ${ displaystyle 5}$ . Текущий результат - 3; следовательно ${ displaystyle b_ {1}}$ взимается ${ displaystyle 5-3 = 2}$ .

Пример # 3

Многопозиционный аукцион с ${ displaystyle n}$ участники торгов, ${ displaystyle n}$ дома и ценности ${ displaystyle { tilde {v}} _ {ij}}$ , представляющий ценного игрока ${ displaystyle i}$ есть для дома ${ displaystyle j}$ . Возможные исходы характеризуются двудольные соответствия Если мы знаем ценности, то максимизация общественного благосостояния сводится к вычислению максимального веса двустороннего сопоставления.

Если мы не знаем значений, мы запрашиваем ставки. ${ displaystyle { tilde {b}} _ {ij}}$ , спрашивая каждого игрока ${ displaystyle i}$ сколько они хотели бы заплатить за дом ${ displaystyle j}$ .Определять ${ displaystyle b_ {я} (а) = { тильда {b}} _ {ik}}$ если участник торгов ${ displaystyle i}$ получает дом ${ displaystyle k}$ в соответствии ${ displaystyle a}$ . Теперь вычислите ${ displaystyle a ^ {*}}$ , максимальный вес двустороннего сопоставления по ставкам и вычислить

{ displaystyle p_ {i} = left [ max _ {a in A} sum _ {j neq i} b_ {j} (a) right] - sum _ {j neq i} b_ {j} (a ^ {*})}

.

Первый член - это еще одно двустороннее сопоставление максимального веса, а второй член может быть легко вычислен из ${ displaystyle a ^ {*}}$ .

Оптимальность честных торгов

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

Для каждого участника торгов ${ displaystyle b_ {i}}$ , позволять ${ displaystyle v_ {i}}$ быть их истинной оценкой предмета ${ displaystyle t_ {i}}$ , и предположим (не теряя общий смысл ) который ${ displaystyle b_ {i}}$ выигрывает ${ displaystyle t_ {i}}$ после представления их истинных оценок. Затем чистая полезность ${ displaystyle U_ {i}}$ достигнутый ${ displaystyle b_ {i}}$ определяется их собственной оценкой выигранного ими предмета за вычетом уплаченной цены:

{ displaystyle { begin {align} U_ {i} & = v_ {i} - left (V_ {N setminus {b_ {i} }} ^ {M} -V_ {N setminus {b_) {i} }} ^ {M setminus {t_ {i} }} right) & = sum _ {j} v_ {j} - sum _ {j neq i} v_ {j } + V_ {N setminus {b_ {i} }} ^ {M setminus {t_ {i} }} - V_ {N setminus {b_ {i} }} ^ {M} & = sum _ {j} v_ {j} -V_ {N setminus {b_ {i} }} ^ {M setminus {t_ {i} }} + V_ {N setminus { b_ {i} }} ^ {M setminus {t_ {i} }} - V_ {N setminus {b_ {i} }} ^ {M} & = sum _ {j} v_ {j} -V_ {N setminus {b_ {i} }.} ^ {M} end {выровнено}}}

В качестве ${ displaystyle V_ {N setminus {b_ {i} }} ^ {M}}$ не зависит от ${ displaystyle v_ {i}}$ , максимизация чистой полезности преследуется механизмом наряду с максимизацией корпоративной валовой полезности ${ displaystyle sum _ {j} v_ {j}}$ за объявленную ставку ${ displaystyle v_ {i}}$ .

Чтобы было понятнее, сформируем разницу ${ displaystyle U_ {i} -U_ {j} = left [v_ {i} + V_ {N setminus {b_ {i} }} ^ {M setminus {t_ {i} }} right] - left [v_ {j} + V_ {N setminus {b_ {i} }} ^ {M setminus {t_ {j} }} right]}$ между чистой полезностью ${ displaystyle U_ {i}}$ из ${ displaystyle b_ {i}}$ по честным торгам ${ displaystyle v_ {i}}$ получил предмет ${ displaystyle t_ {i}}$ , и чистая полезность ${ displaystyle U_ {j}}$ участника торгов ${ displaystyle b_ {i}}$ по нечестным торгам ${ displaystyle v '_ {i}}$ для пункта ${ displaystyle t_ {i}}$ получил предмет ${ displaystyle t_ {j}}$ на истинной полезности ${ displaystyle v_ {j}}$ .

${ displaystyle left [v_ {j} + V_ {N setminus {b_ {i} }} ^ {M setminus {t_ {j} }} right]}$ это корпоративная валовая полезность, полученная в результате неправдивых торгов. Но присвоение распределения ${ displaystyle t_ {j}}$ к ${ displaystyle b_ {i}}$ отличается от присвоения распределения ${ displaystyle t_ {i}}$ к ${ displaystyle b_ {i}}$ который получает максимальную (истинную) валовую корпоративную полезность. Следовательно ${ displaystyle left [v_ {i} + V_ {N setminus {b_ {i} }} ^ {M setminus {t_ {i} }} right] - left [v_ {j} + V_ {N setminus {b_ {i} }} ^ {M setminus {t_ {j} }} right] geq 0}$ и ${ Displaystyle U_ {i} geq U_ {j}}$ q.e.d.