Аукцион Викри–Кларка–Гроувса

Тип закрытого аукциона с несколькими лотами

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

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

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

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

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

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

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

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

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

Обозначение

Для любого набора выставленных на аукцион предметов и любого набора участников пусть будет социальной ценностью аукциона VCG для данной комбинации ставок. То есть, насколько каждый человек оценивает предметы, которые он только что выиграл, суммируясь по всем. Ценность предмета равна нулю, если он не выигрывает. Для участника и предмета пусть ставка участника на предмет будет . Обозначение означает набор элементов A, которые не являются элементами B. ${\displaystyle M=\{t_{1},\ldots ,t_{m}\}}$ ${\displaystyle N=\{b_{1},\ldots ,b_{n}\}}$ ${\displaystyle V_{N}^{M}}$ ${\displaystyle b_{i}}$ ${\displaystyle t_{j}}$ ${\displaystyle v_{i}(t_{j})}$ ${\displaystyle A\setminus 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, определяется следующим образом: во-первых, на аукционе, исключающем участника торгов 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_{i,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}$

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

Если бы человек не был на аукционе, был бы назначен на , и имел бы оценку . Текущий результат 3; следовательно, взимается . ${\displaystyle b_{1}}$ ${\displaystyle t_{1}}$ ${\displaystyle b_{2}}$ ${\displaystyle 5}$ ${\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_{i}(a)={\tilde {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{aligned}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{aligned}}}$

Как не зависит от , механизм преследует цель максимизации чистой полезности наряду с максимизацией корпоративной валовой полезности для заявленной заявки . ${\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]}$это корпоративная валовая полезность, полученная с помощью нечестной ставки. Но распределение, назначающее отличается от распределения, назначающее которому получает максимальную (истинную) валовую корпоративную полезность. Следовательно и qed ${\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}}$

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

• Механизм Викри–Кларка–Гроувса
• Аукцион Викри
• Раскрытие предпочтений

Ссылки

1. фон Ан, Луис (2011-10-13). "Sponsored Search" (PDF) . 15–396: Science of the Web Course Notes . Carnegie Mellon University. Архивировано из оригинала (PDF) 2015-03-06 . Получено 2015-04-13 .
2. Викри, Уильям (1961). «Контрспекуляция, аукционы и конкурентные закрытые торги». Журнал финансов . 16 (1): 8–37. doi :10.1111/j.1540-6261.1961.tb02789.x.
3. Кларк, Э. (1971). «Многокомпонентное ценообразование общественных благ». Public Choice . 11 (1): 17–33. doi :10.1007/bf01726210. S2CID  154860771.
4. Гроувс, Т. (1973). «Стимулы в командах». Econometrica . 41 (4): 617–631. doi :10.2307/1914085. JSTOR  1914085.
5. Декаролис, Франческо; Голдманис, Марис; Пента, Антонио (2017). «Маркетинговые агентства и сговор на аукционах онлайн-рекламы». Национальное бюро экономических исследований . Серия рабочих документов. doi : 10.3386/w23962. S2CID  44056837.
6. Блюм, Аврим (28.02.2013). «Алгоритмы, игры и сети — лекция 14» (PDF) . Получено 28.12.2023 .