Аукцион Викри

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск

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

Аукцион был предложен Уильямом Викри. Этот тип аукциона стратегически схож с английским аукционом, стимулируя участников делать ставки по истинной оценке ими ценности товара.

Аукционы Викри хорошо изучены в экономической литературе, однако не особенно распространены на практике. Одним из рынков, на котором они активно используются, является коллекционирование марок. Система аукционов eBay также схожа, но не идентична, с аукционом Викри. Слегка обобщённый вариант аукциона Викри, называемый обобщённым аукционом со второй ценой (generalized second-price auction), отличный от механизма VCG, используется в системах онлайн-рекламы Google и Yahoo![1][2].

Обобщения[править | править вики-текст]

Оригинальная статья Викри рассматривала только аукционы по продаже простых неделимых товаров. В этом случае условия аукциона Викри и закрытого аукциона со второй ценой эквивалентны.

Аукцион с однородной ценой[править | править вики-текст]

В случае множественных идентичных (или делимых) товаров, реализуемых в рамках одного аукциона, очевидным обобщением является продажа товара всем участникам, выигравшим аукцион, по наибольшей цене неудовлетворенных предложений. Такое обобщение известно как аукцион с однородной ценой (the uniform-price auction). Последний стимулирует участников делать ставки в соответствии с их истинной оценкой ценности только в случае, когда каждому игроку разрешено купить только один товар. В случае возможности делать ставки на несколько товаров свойство оптимальности правдивых ставок в общем случае не выполняется.

Механизм Викри-Кларка-Гровса (VCG auction)[править | править вики-текст]

Обобщение аукциона Викри на случай продажи нескольких товаров, сохраняющее стимулы к правдивому назначению ставок, известно как механизм Викри-Кларка-Гровса (Vickrey-Clarke-Groves, VCG). Идея VCG-аукциона состоит в том, что каждый участник аукциона платит цену исходя из того, как его участие воздействует на всех остальных участников. А именно, каждый игрок платит по итогам аукциона сумму, равную недополученной ценности товаров другими игроками из-за того, что в аукционе участвует этот игрок.

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

  • Участник A желает одно яблоко и делает ставку $5.
  • Участник B также хочет одно яблоко и готов заплатить $2.
  • Участник C претендует на два яблока и намерен заплатить $6 за оба, но не желает приобретать одно яблоко без другого.

Во-первых, мы определяем победителей путем максимизации ставок: яблоки отходят к участникам A и B (поскольку проиграв одно яблоко участнику A, С не претендует на второе).

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

  • Платеж победителя A: B получает яблоко, сделав ставку $2. Если бы участника A не было, C выиграл бы оба яблока и заплатил бы за них $6. Так что A платит разницу между ценой C за оба яблока и ценой B за одно из них: $6-$2 = $4.
  • Платеж победителя B: A получает яблоко, сделав ставку $5, а C не получает ничего. Не будь B, C получил бы оба яблока за $6 (поскольку $6 за два яблока превышает ставку A $5 в отсутствие других участников). Поэтому B платит разницу $6-$5 = $1.

Механизм Викри-Кларка-Гровса (VCG auction) в интернет рекламе[править | править вики-текст]

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

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

Ценность кандидата в этой модели задается функцией V(b,p) = b \cdot p. Наилучшие по ценности K объявлений идут в показ. Для i-го игрока имеем V_i =  V(b_i, p_i) = b_i \cdot p_i.

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

Правила VCG-аукциона для заданной функции ценности V(b, p) и K мест в рекламном блоке звучат следующим образом: нужно отобрать K объявлений максимальных по V и с i-го игрока взять за клик столько денег c_i, что ценность V(c_i, p_i) меньше ценности V(b_i, p_i) его исходной ставки ровно настолько, насколько упала бы суммарная ценность показанных игроков, если бы игрок i не участвовал в аукционе.

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

Тогда для случая трех мест (K = 3) для вычисления стоимости клика первого объявления c_1 нужно решить уравнение: V(c_1, p_i) + V(b_2, p_2) + V(b_3, p_3) =  V(b_2, p_2) + V(b_3, p_3) + V(b_4, p_4)

Два слагаемых в этом уравнении сокращаются и получается: V(c_1, p_1) = V(b_4, p_4).

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

c_1 = b_4 \cdot p_4 / p_1.

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

c_2 = b_4 \cdot p_4 / p_2.

c_3 = b_4 \cdot p_4 / p_3.

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

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

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

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

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

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

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

Рассмотрим случай, когда вероятности клика на объявление зависят от места. Пусть для объявления i вероятность клика на местах 1, 2 , 3 равны соответственно x_1 \cdot p_1, x_2 \cdot p_1, x_3 \cdot p_1, то есть есть множители \{x_1,x_2,x_3\} меньше 1, определяющие мультипликативный поправки к исходной вероятности клика. Назовем их кликабельностями позиций. Не теряя общности, рассмотрим случай, когда позиции расположены в порядке убывания кликабельности, то есть x_1 \ge x_2 \ge x_3. Уравнение определения стоимости клика c_1 первого объявления станет следующим:

x_1  \cdot V(c_1, p_1) + x_2 \cdot V(b_2, p_2) + x_3 \cdot V(b_3, p_3) =  x_1  \cdot V(b_2, p_2) + x_2 \cdot  V(b_3, p_3) + x_3 \cdot V(b_4, p_4)


Подставляя V_i = V(b_i, p_i) = b_i \cdot p_i получаем:

V_1 = ( (x_1 - x_2) \cdot V_2 + (x_2 - x_3) \cdot V_3 + x_3 \cdot V_4 ) / x_1

c_1 = ( (x_1 - x_2) \cdot b_2 \cdot p_2 + (x_2 - x_3) \cdot b_3 \cdot p_3 + x_3 \cdot b_4 \cdot p_4 ) /( x_1 \cdot p_1)

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

Свойства[править | править вики-текст]

Стимулирование раскрытия истинных оценок[править | править вики-текст]

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

Эффективность распределения ресурсов[править | править вики-текст]

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

Ограничения[править | править вики-текст]

При всех преимуществах, аукцион Викри имеет ряд ограничений:

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

Механизм VCG имеет дополнительные ограничения:

  • Возможность потери ставок участников аукциона.
  • Уязвимость покупателей из-за возможности «подставных ставок» со стороны продавца.
  • Отсутствие максимизации выручки продавца — последняя может даже оказаться равной нулю по итогам аукциона VCG. Если целью аукциона является максимизация прибыли продавца, а не просто эффективное распределение ресурсов среди покупателей, тогда VCG может оказаться плохим выбором.
  • Выручка продавца не монотонна по отношению к размерам ставок.

Немонотонность выручки продавца относительно размера ставки может быть продемонстрирована следующим примером.

Рассмотрим трёх участников A, B, и C, и два одинаковых товара Y и Z.

  • A претендует на оба товара и делает ставку $2 за сумму Y и Z.
  • Как B, так и C делают ставки по $2 за любой из товаров ($2 за Y или Z).

В итоге Y и Z отходят к B и C, но по цене $0, как можно увидеть, последовательно удаляя B и C.

При этом если C поставил бы $0 вместо $2, то продавец получил бы $2 вместо $0. Поскольку выручка продавца также может вырасти с ростом ставок B и C, она оказывается немонотонна.

Примечания[править | править вики-текст]

  1. Benjamin Edelman, Michael Ostrovsky, and Michael Schwarz: «Internet Advertising and the Generalized Second-Price Auction: Selling Billions of Dollars Worth of Keywords». American Economic Review 97(1), 2007 pp 242—259.
  2. Hal R. Varian: «Position Auctions». International Journal of Industrial Organization, 2006, doi:10.1016/j.ijindorg.2006.10.002.
  3. https://developers.facebook.com/docs/marketing-api/pacing
  4. http://www.econ.ucsb.edu/~tedb/Courses/UCSBpf/readings/LovelybutLonely.pdf

Литература[править | править вики-текст]

  • W. Vickrey. Counterspeculation, auctions and competitive sealed tenders. Columbia University. 1961
  • von Ahn, Luis (2008-09-30)."Auctions" (PDF). 15-396: Science of the Web Course Nodes. Carnegie Mellon University. http://www.scienceoftheweb.org/15-396/lectures/lecture09.pdf. Retrieved on 2008-11-06.