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