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

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

Формальная модель [ править ]

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

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

Мы можем придумать дополнительные виртуальные слоты с нулевым рейтингом кликов, так что для . Теперь каждый участник торгов подает заявку с указанием максимальной суммы, которую они готовы заплатить за слот. У каждого участника торгов также есть внутренняя стоимость покупки слота . Обратите внимание, что ставка игрока не обязательно должна совпадать с его истинной оценкой . Мы упорядочиваем участников по их ставкам, скажем:${\ displaystyle nk}$${\ displaystyle \ alpha _ {m} = 0}$${\ Displaystyle к <м \ Leq п}$${\ 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}.}$

Механизм GSP [ править ]

Чтобы указать механизм, нам необходимо определить правило распределения (кто и какой слот получает) и цены, оплачиваемые каждым участником торгов. На обобщенном аукционе второй цены мы упорядочиваем участников по их ставкам и отдаем верхнюю ячейку тому, кто предложит самую высокую цену, второй верхний сегмент - тому, кто сделал самую высокую ставку, и так далее. Тогда, если предположить , что ставки будут перечислены в порядке убывания торгов претендент получает слот для . Каждый участник победы слот платит ставку на следующий самую высокую цену, так: .${\ Displaystyle b_ {1} \ geq b_ {2} \ geq \ cdots \ geq b_ {n}, \,}$${\ displaystyle b_ {i}}$${\ displaystyle i}$${\ Displaystyle 1 \ Leq я \ Leq к}$${\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 [ править ]

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

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

GSP и неопределенность [ править ]

Классические результаты Эдельмана, Островского и Шварца ^[1] и Вариана ^[2] справедливы в условиях полной информации - когда нет никакой неопределенности. Недавние результаты, как Gomes and Sweeney ^[8] и Caragiannis et al. ^[4], а также эмпирически Эти и Некипелов ^[9] обсуждают байесовскую версию игры, в которой игроки имеют представления о других игроках, но не обязательно знают их оценки.

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

Бюджетные ограничения [ править ]

Влияние бюджетных ограничений на модель спонсируемого поиска / аукциона по позициям обсуждается в Ashlagi et al. ^[11] и в более общей задаче о присваивании Аггарвалом и др. ^[12] и Dütting et al. ^[13]

См. Также [ править ]

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

Ссылки [ править ]

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