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

Механизм поискового аукциона

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

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

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

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

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

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

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

Механизм ВСП

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

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

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

Равновесия GSP

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

Границы благосостояния в равновесии Нэша даны Карагианнисом и др. ^[3], доказывающими цену анархии . Дюттинг и др. ^[4] и Люсьер и др. доказывают ^[5] , что любое равновесие Нэша извлекает по крайней мере половину истинного дохода VCG из всех слотов, кроме первого. Вычислительный анализ этой игры был выполнен Томпсоном и Лейтоном-Брауном . ^[6] ${\displaystyle 1.282}$

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

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

Гомес и Суини ^[7] доказывают, что эффективное равновесие может не существовать в условиях частичной информации. Карагианнис и др. ^[3] рассматривают потерю благосостояния в равновесии Байеса-Нэша и доказывают, что цена анархии составляет 2,927. Границы дохода в равновесии Байеса-Нэша даны Люсьером и др. ^[5] и Карагианнисом и др. ^[9]

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

Влияние бюджетных ограничений в модели спонсируемого поиска или аукциона позиций обсуждается в работе Ашлаги и др. ^[10] , а в более общей задаче назначения — в работе Аггарвала и др. ^[11] и Дюттинга и др. ^[12].

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

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

Ссылки

1. Бенджамин Эдельман, Майкл Островски и Майкл Шварц: «Интернет-реклама и обобщенный аукцион второй цены: продажа ключевых слов на миллиарды долларов». American Economic Review 97(1), 2007 стр. 242-259
2. HR Varian: «Позиционные аукционы. Международный журнал промышленной организации, 2006».
3. Караяннис, Иоаннис; Какламанис, Христос; Канеллопулос, Панайотис; Киропулу, Мария; Люсье, Брендан; Паес Леме, Ренато; Тардос, Ева (2015). «Ограничение неэффективности результатов на обобщенных аукционах второй цены». Журнал экономической теории . 156 : 343–388. arXiv : 1201.6429 . дои : 10.1016/j.jet.2014.04.010. S2CID  37395632.
4. Дюттинг, Пол; Фишер, Феликс; Паркс, Дэвид К. (2011). «Компромисс простоты и выразительности в проектировании механизмов». Труды 12-й конференции ACM по электронной коммерции . стр. 341–350. doi :10.1145/1993574.1993632. ISBN 9781450302616. S2CID  607322.
5. Люсьер, Брендан; Ренато, Паес Леме; Ева, Тардос (2012). «О доходах на обобщенном аукционе второй цены». Труды 21-й международной конференции по Всемирной паутине . С. 361–370. doi :10.1145/2187836.2187886. ISBN 9781450312295. S2CID  6518222.
6. DRM Thompson и K. Leyton-Brown. Вычислительный анализ аукционов с идеальной информацией. В EC '09: Труды десятой конференции ACM по электронной коммерции, страницы 51–60, Нью-Йорк, США, 2009. ACM.
7. RD Gomes и KS Sweeney. "Равновесие Байеса–Нэша обобщенного аукциона второй цены". В EC '09: Труды десятой конференции ACM по электронной коммерции , страницы 107–108, Нью-Йорк, США, 2009. ACM
8. Сьюзан Атей и Денис Некипелов. Структурная модель аукционов спонсируемой поисковой рекламы Архивировано 25.04.2012 в Wayback Machine , Ad Auctions Workshop, 2010
9. Caragiannis, Ioannis; Kaklamanis, Christos; Kanellopoulos, Panagiotis; Kyropoulou, Maria (2014). «Гарантии дохода на обобщенном аукционе второй цены» (PDF) . ACM Transactions on Internet Technology . 14 (2–3): 1–19. doi :10.1145/2663497. S2CID  9233522.
10. Ашлаги, Итай; Браверман, Марк ; Хассидим, Авинатам; Лави, Рон; Тенненхольц, Моше (2010). «Позиционные аукционы с бюджетами: существование и уникальность». BE Journal of Theoretical Economics . 10 (1): Статья 20. doi :10.2202/1935-1704.1648. hdl : 1721.1/64459 . S2CID  8624078.
11. Аггарвал, Гаган; Мутукришнан, Муту ; Пал, Дэвид; Пал, Мартин (2009). «Общий механизм аукциона для поисковой рекламы». Труды 18-й международной конференции по Всемирной паутине . С. 241–250. arXiv : 0807.1297 . doi : 10.1145/1526709.1526742. ISBN 9781605584874. S2CID  2800123.
12. Дюттинг, Пол; Хензингер, Моника ; Вебер, Ингмар (2011). «Выразительный механизм для аукционов в Интернете». Труды 20-й международной конференции по Всемирной паутине . С. 127–136. doi :10.1145/1963405.1963427. ISBN 9781450306324. S2CID  2138064.

• S. Lahaie, D. Pennock, A. Saberi и R. Vohra. Алгоритмическая теория игр , глава «Спонсируемые аукционы поиска», страницы 699–716. Cambridge University Press, 2007
• Конспект лекций по теме «Реклама на основе ключевых слов»