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

редактировать

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

Содержание

1 Формальная модель
2 GSP механизм
3 Неверность
4 Равновесие GSP
5 GSP и неопределенность
6 Бюджетные ограничения
7 См. также
8 Ссылки

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

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

α 1 ≥ α 2 ≥ ⋯ ≥ α k. {\ displaystyle \ alpha _ {1} \ geq \ alpha _ {2} \ geq \ cdots \ geq \ alpha _ {k}. \,}

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

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

b 1 ≥ b 2 ≥ ⋯ ≥ bn, {\ displaystyle b_ {1} \ geq b_ {2} \ geq \ cdots \ geq b_ {n}, \, }

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

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

Механизм GSP

Чтобы указать механизм , нам нужно определить распределение правило (кто получает какой слот) и цены, оплачиваемые каждым участником торгов. На обобщенном аукционе второй цены мы упорядочиваем участников по их ставкам и отдаем верхнюю ячейку тому, кто предложит самую высокую цену, второй верхний сегмент - тому, кто сделал самую высокую ставку, и так далее. Затем, предполагая, что ставки перечислены в порядке убывания $b 1 ≥ b 2 ≥ ⋯ ≥ bn, {\ displaystyle b_ {1} \ geq b_ {2} \ geq \ cdots \ geq b_ {n}, \,}$ ${\ displaystyle b_ {1} \ geq b_ {2} \ geq \ cdots \ geq b_ {n}, \,}$ участник торгов $bi {\ displaystyle b_ {i}}$ $b_ {i}$ получает слот $i {\ displaystyle i}$ $я$ для $1 ≤ я ≤ К {\ Displaystyle 1 \ Leq я \ Leq k}$ $1 \ leq i \ leq k$ . Каждый участник ставки, выигравший слот, платит ставку следующего по величине участника, так что: $pi = bi + 1 {\ displaystyle p_ {i} = b_ {i + 1}}$ $p_ {i} = b _ {{i + 1}}$ .

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

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

Равновесие GSP

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

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

GSP и неопределенность

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

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

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

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

См. также

Ссылки

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