Механизм Викри — Кларка — Гровса

Материал из Википедии — свободной энциклопедии
(перенаправлено с «Механизм Викри-Кларка-Гровса»)
Перейти к навигации Перейти к поиску

В теории аукционов, механизм аукциона Викри — Кларка — Гровса (обобщённый аукцион Викри) — это тип многотоварных аукционов закрытой формы. Участники ставят ставки, которые соответствуют их оценкам ценности товаров, не зная ставок других участников. Аукцион распределяет товары «социально оптимальным» образом (по отношению к участникам аукциона, участник максимально оценивающий товар гарантированно получает его): каждый участник аукциона платит цену равную воздействию его участия на результат аукциона (исходя из того, как его участие воздействует на всех остальных участников)[1] . Он также создаёт стимулы для участников ставить в качестве ставок свои собственные оценки ценности товара, гарантируя, что оптимальной стратегией для участника будет правдиво сообщать свою оценку ценности товара посредством своей ставки (выставления в качестве ставки свою истинную ценность товара). Это обобщение аукциона Викри для многотоварных аукционов. Аукцион назван в честь Вильяма Викри[2], Эдварда Кларка[3], и Теодора Гровса[4], которые в своих статьях успешно обобщили идею аукциона Викри для случая однотоварного аукциона на случай многотоварного.

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

Определение

Для любого набора продаваемых на аукционе товаров и набора участников , пусть  — это «общественная выгода» (в качестве «общества» выступает множество участников) от результата VCG-аукциона при данном наборе ставок. Для участника и товара ставкой участника будет .

Назначение победителя

Участник чья ставка для товара , а именно , является максимальной среди участников, выигрывает аукцион, но платит что равно размеру неполученной выгоды оставшихся участников от его выигрыша (сам выигрыш определён остальными участниками).

Объяснение (интуиция)

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

Значение функции полезности для победителя

Выигравший участник аукциона, чьей ставкой является его истинная ценность товара , получает максимум прибыли

Примеры[править | править код]

Пример #1[править | править код]

Пример с яблоками в разделе с примерами аукциона Викри.

Пример #2[править | править код]

Предположим, что есть два игрока, и , и два товара, и , и каждый участник может получить только один товар. Пусть это ценность товара для игрока . Положим , , , и . Видно, что оба игрока и предпочтут получить товар ; однако «социально оптимальная» схема проведения аукциона назначает товар игроку (так что его полученная ценность будет равна ) и товар игроку (так что его полученная ценность будет равна ). Таким образом, общая полученная ценность будет равна , что является оптимальным.

Если игрок не принимает участие в аукционе, участник всё равно получает товар , то есть для него ничего не меняется. Текущая полученная ценность будет равна , следовательно с игрока будет списано .

Если игрок не принимает участие в аукционе, товар достаётся игроку , и имеет ценность . Текущая полученная ценность будет равна , следовательно с игрока будет списано .

Пример #3[править | править код]

Рассмотрим многотоварный аукцион. Пусть в аукционе участвует участников, домов, и ценности дома для участника . Возможным результатом проведения аукциона в этом случае может являться паросочетание в двудольном графе, с помощью которого могут быть составлены пары домов с участниками аукционов. Если мы знаем ценности, то максимизация общественного благосостояния ограничивается поиском паросочетания максимального веса в соответствующем двудольном графе[5]. Если мы не знаем ценностей, то вместо этого можно запросить ставки , которые готов заплатить участник за дом . Обозначим если участник получает дом в паросочетании . Теперь вычислим , паросочетание максимального веса в двудольном графе в случае назначения в ставок в качестве весов и вычислим

.

Первое слагаемое это другое паросочетание максимального веса в двудольном графе, а второе слагаемое может быть легко получено из .

Оптимальность стратегии правдивого раскрытия своих оценок ценности товара[править | править код]

Написанное в этом параграфе доказывает что назначение ставки равной вашей истинной оценки ценности оптимальна для вас[6]. Для каждого участника , пусть его истинная ценность товара , допустим (без потери общности) что получает выставляя в качестве ставки свою истинную ценность товара. Тогда чистая прибыль достигаемая участником будет . Так как не зависит от , то максимизация чистой прибыли достигается согласно механизму аукциона при максимизации суммарного дохода для выставленной ставки . Другими словами, механизм аукциона таким образом назначает платежи, что при достижении максимального дохода игрока достигается максимальное значение прибыли. И задача участника не манипулировать ставками, а выставить такую ставку, которая будет равна его истинной ценности товара. Это позволяет участникам исключить из задачи оптимизации своей прибыли функцию платежей. Запишем разницу между чистой прибылью участника выставляющего ставку равную его истинной ценности полученного товара , и чистую прибыль участника при неправдивой стратегии выставления ставки за товар и получившим товар с истинной ценностью . это максимум общего дохода полученного в результате неправдивой стратегии выставления ставок. Но назначение товара участнику отличается от назначении товара участнику что доставляет максимум суммарному доходу. Следовательно и ч.т.д.

Использование в интернет-рекламе[править | править код]

VCG-аукцион используется для продажи рекламных мест на интернет-площадках. В частности, эту модель аукциона используют Facebook[7], Google (в своей партнерской сети)[8] и Яндекс (на странице результатов поиска)[9]. Другой популярной моделью продажи рекламных мест является аукцион обобщенной второй цены (generalized second-price auction).

Пусть в рекламном блоке мест. За эти места конкурируют несколько рекламных объявлений. В модели, когда оплата осуществляется за клики (pay per click модель), важными параметрами конкурирующих объявлений являются их ставки за клики и вероятности клика

Ценность кандидата в этой модели задается функцией . Наилучшие по ценности объявлений идут в показ. Для -го игрока имеем .

Возможны более сложные варианты функции ценности , важное требование к этой функции — монотонность относительно ставки .

Правила VCG-аукциона для заданной функции ценности и мест в рекламном блоке звучат следующим образом: нужно отобрать объявлений максимальных по и с -го игрока взять за клик столько денег , что ценность меньше ценности его исходной ставки ровно настолько, насколько упала бы суммарная ценность показанных игроков, если бы игрок не участвовал в аукционе.

Рассмотрим случай, когда все позиции одинаково хороши, то есть вероятности клика объявлений не зависят от позиции.

Тогда для случая трех мест () для вычисления стоимости клика первого объявления нужно решить уравнение:

Два слагаемых в этом уравнении сокращаются и получается:

То есть для вычисления цены клика первого объявления нужно уменьшить его ставку настолько, чтобы его ценность уменьшилось до ценности первого непоказанного игрока (в данном случае — 4-го объявления).

Аналогичное утверждение верно и для 2-го и 3-го игроков:

Таким образом, если вероятности клика участвующих в аукционе объявлений равны (оценки CTR совпадают), и их ставки равны 10, 7, 5, 2, то в показ пойдут первые три, и все они будут платить 2 — цену 4-го объявления.

В случае, когда аукцион VCG совпадает с аукционом второй цены.

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

Свойство правдивости назначения ставок (thruthfulness) VCG-аукциона в случае интернет-рекламы означает следующее: для решения задачи максимизации свой прибыли рекламодателю нужно ставить такую ставку, что в случае, если бы списываемая цена была равна в точности выставленной, рекламодатель получил бы нулевую прибыль от клика в среднем. Для случая, когда рекламодатель хочет получать прибыль с ROI выше некоторого заданного значения ему нужно ставить минимальную ставку, при которой достигается необходимый ему ROI. Как с ограничением так и без ограничения на ROI оптимальная ставка не зависит от ставок других игроков.

Когда у рекламодателя кроме ограничения на ROI есть фиксированный бюджет на рекламу в единицу времени и это ограничение не фиктивное, а регулярно достигаемое, то его алгоритм выставления оптимальной ставки (максимизирующей его прибыль) в VCG-аукционе уже не имеет простого описания.

Также алгоритм вычисления оптимальной ставки также сложен и зависит от ставок конкурентов, когда максимизируется не прибыль, а некая комбинация оборота и прибыли.

Случай различной кликабельности мест[править | править код]

Рассмотрим случай, когда вероятности клика на объявление зависят от места. Пусть для объявления вероятность клика на местах 1, 2 , 3 равны соответственно , , , то есть есть множители меньше 1, определяющие мультипликативный поправки к исходной вероятности клика. Назовем их кликабельностями позиций. Не теряя общности, рассмотрим случай, когда позиции расположены в порядке убывания кликабельности, то есть . Уравнение определения стоимости клика первого объявления станет следующим:

Подставляя получаем:

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

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

  1. von Ahn, Luis Sponsored Search (PDF) (недоступная ссылка). 15–396: Science of the Web Course Notes. Carnegie Mellon University (13 октября 2011). Дата обращения 13 апреля 2015. Архивировано 6 марта 2015 года.
  2. Vickrey, William. Counterspeculation, Auctions, and Competitive Sealed Tenders (англ.) // The Journal of Finance (англ.) : journal. — 1961. — Vol. 16, no. 1. — P. 8—37. — doi:10.1111/j.1540-6261.1961.tb02789.x.
  3. Clarke, E. Multipart Pricing of Public Goods (неопр.) // Public Choice. — 1971. — Т. 11, № 1. — С. 17—33. — doi:10.1007/bf01726210.
  4. Groves, T. Incentives in Teams (англ.) // Econometrica : journal. — 1973. — Vol. 41, no. 4. — P. 617—631. — doi:10.2307/1914085.
  5. Douglas Brent West. Introduction to Graph Theory. — 2nd. — Prentice Hall, 1999. — ISBN 0-13-014400-2.
  6. http://www.cs.cmu.edu/~arielpro/15896/docs/notes14.pdf
  7. https://developers.facebook.com/docs/marketing-api/pacing
  8. http://www.econ.ucsb.edu/~tedb/Courses/UCSBpf/readings/LovelybutLonely.pdf
  9. Новый аукцион и новое ранжирование в Директе — Блог рекламных технологий