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

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

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

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

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

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

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

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

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

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

Обозначения

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

Назначение

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

Объяснение

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

Утилита победителя

Победитель торгов, чья ставка соответствует истинной стоимости $A$ для предмета $t_{j}$ , $v_{i}(t_{j})=A,$ извлекает максимальную полезность $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 долларов. Таким образом, после аукциона стоимость, полученная участником торгов А, составляет 5 долларов США, участником торгов Б — 2 доллара США, а участником торгов С — 0 долларов США (поскольку участник торгов С ничего не получает). Обратите внимание, что определение победителей — это, по сути, задача о рюкзаке .

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

Для участника А : Плата за выигрыш, требуемая от А, определяется следующим образом: во-первых, на аукционе, в котором исключается участник А, в результате максимизации социального благосостояния оба яблока будут переданы участнику С с общей социальной ценностью 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 нейтральен (ничего не выиграв).

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

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

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

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

Пример №3

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

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

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

.

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

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

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

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

{\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}}

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

Чтобы было понятнее, сформируем разницу $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]$ между чистой полезностью $U_{i}$ из $b_{i}$ по честным торгам $v_{i}$ получен предмет $t_{i}$ и чистая полезность $U_{j}$ участника торгов $b_{i}$ на неправдивых торгах $v'_{i}$ для предмета $t_{i}$ получен предмет $t_{j}$ об истинной полезности $v_{j}$ .

$\left[v_{j}+V_{N\setminus \{b_{i}\}}^{M\setminus \{t_{j}\}}\right]$ — это корпоративная валовая полезность, полученная в результате неправдивых торгов. Но назначение распределения $t_{j}$ к $b_{i}$ отличается от назначения распределения $t_{i}$ к $b_{i}$ который получает максимальную (истинную) валовую корпоративную полезность. Следовательно $\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$ и $U_{i}\geq U_{j}$ кед

См. также

Ссылки

^ фон Ан, Луис (13 октября 2011 г.). «Спонсируемый поиск» (PDF) . 15–396: Примечания к веб-курсу «Наука» . Университет Карнеги-Меллон. Архивировано из оригинала (PDF) 6 марта 2015 г. Проверено 13 апреля 2015 г.
^ Викри, Уильям (1961). «Контрспекуляции, аукционы и закрытые тендеры». Журнал финансов . 16 (1): 8–37. дои : 10.1111/j.1540-6261.1961.tb02789.x .
^ Кларк, Э. (1971). «Многочастное ценообразование на общественные блага». Общественный выбор . 11 (1): 17–33. дои : 10.1007/bf01726210 . S2CID 154860771 .
^ Гроувс, Т. (1973). «Стимулы в командах». Эконометрика . 41 (4): 617–631. дои : 10.2307/1914085 . JSTOR 1914085 .
^ Декаролис, Франческо; Гольдманис, Марис; Пента, Антонио (2017). «Маркетинговые агентства и сговор на аукционах онлайн-рекламы» . Национальное бюро экономических исследований . Серия рабочих документов. дои : 10.3386/w23962 . S2CID 44056837 .
^ Блюм, Аврим (28 февраля 2013 г.). «Алгоритмы, игры и сети. Лекция 14» (PDF) . Проверено 28 декабря 2023 г.

[1] фон Ан, Луис (13 октября 2011 г.). «Спонсируемый поиск» (PDF) . 15–396: Примечания к веб-курсу «Наука» . Университет Карнеги-Меллон. Архивировано из оригинала (PDF) 6 марта 2015 г. Проверено 13 апреля 2015 г.

[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). «Стимулы в командах». Эконометрика . 41 (4): 617–631. дои : 10.2307/1914085 . JSTOR 1914085 .

[5] Декаролис, Франческо; Гольдманис, Марис; Пента, Антонио (2017). «Маркетинговые агентства и сговор на аукционах онлайн-рекламы» . Национальное бюро экономических исследований . Серия рабочих документов. дои : 10.3386/w23962 . S2CID 44056837 .

[6] Блюм, Аврим (28 февраля 2013 г.). «Алгоритмы, игры и сети. Лекция 14» (PDF) . Проверено 28 декабря 2023 г.

[ 1 ]

[ 2 ]

[ 3 ]

[ 4 ]

[ 5 ]

[ 6 ]