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

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

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

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

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

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

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

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

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

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

Обозначение

Для любого набора выставленных на аукционе лотов и любой набор участников торгов , позволять быть социальной ценностью аукциона VCG для данной комбинации ставок. То есть, насколько каждый человек ценит только что выигранные предметы, в сумме для всех. Если они не выиграют, ценность предмета равна нулю. Участнику торгов и предмет , пусть заявка участника аукциона будет . Обозначение означает набор элементов A, которые не являются элементами B.

Назначение

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

Объяснение

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

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

Победитель торгов, ставка которого является истинной стоимостью для пункта , извлекает максимальную пользу

Примеры

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

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

  • Претендент А хочет одно яблоко и готов заплатить за это яблоко 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 нейтрально (ничего не выиграв).

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

Предположим, что есть два участника торгов, и , два предмета, и , и каждый участник торгов может получить по одной позиции. Мы позволяем быть участником торгов оценка товара . Предполагать , , , и . Мы видим, что оба и предпочел бы получить товар ; однако социально оптимальное задание дает элемент к участнику торгов (так что их достигнутое значение ) и элемент к участнику торгов (так что их достигнутое значение ). Следовательно, общее достигнутое значение составляет , что оптимально.

Если человек не участвовали в аукционе, человек все равно будет назначен , и, следовательно, человек больше ничего не получишь. Текущий результат ; следовательно взимается .

Если человек не было на аукционе, будет назначен , и будет иметь оценку . Текущий результат - 3; следовательно взимается .

Пример # 3

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

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

.

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

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

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

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

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

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

это корпоративная валовая полезность, полученная в результате неправдивых торгов. Но присвоение распределения к отличается от присвоения распределения к который получает максимальную (истинную) валовую корпоративную полезность. Следовательно и q.e.d.

Смотрите также

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

  1. ^ фон Ан, Луис (2011-10-13). "Рекламный поиск" (PDF). 15–396: Примечания к курсу "Наука в Интернете". Университет Карнеги Меллон. Архивировано из оригинал (PDF) на 2015-03-06. Получено 2015-04-13.
  2. ^ Викри, Уильям (1961). «Противодействие спекуляциям, аукционы и закрытые конкурсные торги». Журнал финансов. 16 (1): 8–37. Дои:10.1111 / j.1540-6261.1961.tb02789.x.
  3. ^ Кларк, Э. (1971). «Многокомпонентное ценообразование на общественные блага». Общественный выбор. 11 (1): 17–33. Дои:10.1007 / bf01726210. S2CID  154860771.
  4. ^ Гровс, Т. (1973). «Поощрения в командах». Econometrica. 41 (4): 617–631. Дои:10.2307/1914085. JSTOR  1914085.
  5. ^ Декаролис, Франческо; Гольдманис, Марис; Пента, Антонио. "Маркетинговые агентства и сговор на аукционах рекламы в Интернете". Национальное бюро экономических исследований.
  6. ^ https://www.cs.cmu.edu/~arielpro/15896/docs/notes14.pdf