Обобщенный аукцион второй цены

Обобщенный аукцион второй цены (GSP) — это недостоверный механизм аукциона для нескольких товаров. Каждый участник торгов делает ставку. Участник, предложивший самую высокую цену, получает первое место, второй по величине, второй слот и так далее, но участник, предложивший самую высокую цену, платит цену, предложенную вторым по величине участником, второй по величине платит цену, предложенную третьим по величине, и скоро. Первоначально задуманный как естественное продолжение аукциона Викри , он сохраняет некоторые желательные свойства аукциона Викри. Он используется в основном в контексте аукционов по ключевым словам, где спонсируемые поисковые места продаются на аукционной основе. Первые анализы ВСП содержатся в экономической литературе Эдельманом, Островским и Шварцем. и Вариан . Он используется технологией Google AdWords и Facebook.

Формальная модель

Предположим, что существуют $n$ участники торгов и $k<n$ слоты. Каждый слот имеет вероятность нажатия $\alpha _{i}$. Мы можем предположить, что верхние слоты имеют большую вероятность нажатия, поэтому:

$\alpha _{1}\geq \alpha _{2}\geq \cdots \geq \alpha _{k}.\,$

Мы можем подумать о $n-k$ дополнительные виртуальные слоты с нулевым кликабельностью, т.е. $\alpha _{m}=0$ для $k<m\leq n$. Теперь каждый участник торгов подает заявку $b_{i}$ с указанием максимальной суммы, которую они готовы заплатить за слот. Каждый участник торгов также имеет внутреннюю ценность для покупки слота. $v_{i}$. игрока Обратите внимание, что ставка $b_{i}$ не обязательно должна совпадать с их истинной оценкой $v_{i}$. Мы упорядочиваем участников торгов по их ставкам, скажем:

$b_{1}\geq b_{2}\geq \cdots \geq b_{n},\,$

и взимать с каждого участника торгов цену $p_{i}$. Цена будет 0, если они не выиграли слот. Слоты продаются по модели с оплатой за клик , поэтому участник торгов просто платит за слот, если пользователь действительно нажимает на него. Мы говорим о полезности участника торгов $i$ кто назначен на слот $i$ является $u_{i}=\alpha _{i}(v_{i}-p_{i})$. Общее социальное благосостояние от владения или продажи всех слотов определяется следующим образом: $SW=\sum _{i}\alpha _{i}v_{i}.$ Ожидаемый общий доход определяется следующим образом: $TR=\sum _{i}\alpha _{i}p_{i}.$

механизм ВСП

Чтобы указать механизм, нам нужно определить правило распределения (кто какое место получит) и цены, которые платит каждый участник торгов. На обобщенном аукционе второй цены мы упорядочиваем участников по их ставкам и отдаем верхнее место тому, кто предложит самую высокую цену, второе верхнее место — тому, кто предложит вторую по величине цену, и так далее. Затем, предполагая, что ставки перечислены в порядке убывания $b_{1}\geq b_{2}\geq \cdots \geq b_{n},\,$ участник торгов $b_{i}$ получает слот $i$ для $1\leq i\leq k$. Каждый участник, выигравший слот, платит ставку следующего участника, предложившего самую высокую цену, поэтому: $p_{i}=b_{i+1}$.

Неправдивость

Бывают случаи, когда предложение истинной оценки не является равновесием Нэша . Например, рассмотрим два слота с $\alpha _{1}=1$ и $\alpha _{2}=0.4$ и три претендента с оценками $v_{1}=7$, $v_{2}=6$ и $v_{3}=1$ и ставки $b_{1}=7$, $b_{2}=6$ и $b_{3}=1$ соответственно. Таким образом, $p_{1}=b_{2}=6$, и $p_{2}=b_{3}=1$. Утилита для участников торгов $1$ является $u_{1}=\alpha _{1}(v_{1}-p_{1})=1(7-6)=1.$ Этот набор ставок не является равновесием Нэша, поскольку первый участник торгов может снизить свою ставку до 5 и получить второй слот по цене 1, увеличивая свою полезность до $0.4(6-1)=2$.

Равновесия GSP

Эдельман, Островский и Шварц, работая в условиях полной информации, покажите, что ВСП (в ​​модели, представленной выше) всегда имеет эффективное равновесие, свободное от местной зависти, т. е. равновесие, максимизирующее социальное благосостояние, которое измеряется как $SW=\sum _{i}\alpha _{i}v_{i}$ где участник торгов $i$ выделен слот $i$ по убывающему вектору ставки $(b_{1},\dots ,b_{n})$. Кроме того, ожидаемый общий доход в любом равновесии, свободном от локальной зависти, по меньшей мере так же высок, как и в (правдивом) результате VCG .

Границы благосостояния при равновесии Нэша даны Caragiannis et al., доказывая цену анархии, связанную $1.282$. Дюттинг и др. и Люсье и др. доказывать что любое равновесие Нэша извлекает по крайней мере половину истинного дохода VCG из всех слотов, кроме первого. Компьютерный анализ этой игры был выполнен Томпсоном и Лейтоном-Брауном .

ВСП и неопределенность

Классические результаты Эдельмана, Островского и Шварца. и Вариан проводить в условиях полной информации – когда нет никакой неопределенности. Последние результаты как Гомес и Суини и Карагианнис и др. а также эмпирически Атей и Некипелов обсудите байесовскую версию игры, в которой игроки имеют убеждения относительно других игроков, но не обязательно знают оценки других игроков.

Гомес и Суини доказать, что эффективное равновесие может не существовать в условиях частичной информации. Караяннис и др. рассмотрите потерю благосостояния при равновесии Байеса-Нэша и докажите, что цена анархии равна 2,927. Границы дохода в равновесии Байеса – Нэша даны Lucier et al. и Карагианнис и др.

Бюджетные ограничения

Эффект бюджетных ограничений в модели спонсируемого поиска или аукциона позиций обсуждается в Ashlagi et al. и в более общей задаче о назначениях Аггарвала и др. и Дюттинг и др.

См. также

• Аукцион Викри-Кларка-Гроувса
• Обобщенный аукцион первой цены
• Google Реклама
• Теория аукционов
• Японский аукцион

Ссылки

• С. Лахайе, Д. Пеннок, А. Сабери и Р. Вохра. Алгоритмическая теория игр , глава «Спонсорские поисковые аукционы», страницы 699–716. Издательство Кембриджского университета, 2007 г.
• Конспекты лекций по рекламе на основе ключевых слов