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

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

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

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

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

В случае множественных идентичных (или делимых) товаров, реализуемых в рамках одного аукциона, очевидным обобщением является продажа товара всем участникам, выигравшим аукцион, по наибольшей цене неудовлетворенных предложений. Такое обобщение известно как аукцион с однородной ценой (the uniform-price 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-аукцион используется для продажи рекламных мест на интернет-площадках. В частности, эту модель аукциона используют Яндекс^[3], Facebook^[4] и Google (в своей партнерской сети)^[5]. Другой популярной моделью продажи рекламных мест является аукцион обобщенной второй цены (generalized second-price auction).

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

Ценность кандидата в этой модели задаётся функцией ${\displaystyle V(b,p)=b\cdot p}$. Наилучшие по ценности ${\displaystyle K}$ объявлений идут в показ. Для ${\displaystyle i}$-го игрока имеем ${\displaystyle V_{i}=V(b_{i},p_{i})=b_{i}\cdot p_{i}}$.

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

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

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

Тогда для случая трёх мест (${\displaystyle K=3}$) для вычисления стоимости клика первого объявления ${\displaystyle c_{1}}$ нужно решить уравнение: ${\displaystyle 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})}$

Два слагаемых в этом уравнении сокращаются и получается: ${\displaystyle V(c_{1},p_{1})=V(b_{4},p_{4}).}$

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

${\displaystyle c_{1}=b_{4}\cdot p_{4}/p_{1}.}$

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

${\displaystyle c_{2}=b_{4}\cdot p_{4}/p_{2}.}$

${\displaystyle c_{3}=b_{4}\cdot p_{4}/p_{3}.}$

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

При ${\displaystyle K=1}$ аукцион VCG совпадает с аукционом второй цены.

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

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

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

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

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

Пусть для объявления ${\displaystyle i}$ вероятность клика на местах 1, 2 , 3 равны соответственно ${\displaystyle x_{1}\cdot p_{1}}$, ${\displaystyle x_{2}\cdot p_{1}}$, ${\displaystyle x_{3}\cdot p_{1}}$, то есть есть множители ${\displaystyle \{x_{1},x_{2},x_{3}\}}$ меньше 1, определяющие мультипликативный поправки к исходной вероятности клика. Назовем их кликабельностями позиций. Не теряя общности, рассмотрим случай, когда позиции расположены в порядке убывания кликабельности, то есть ${\displaystyle x_{1}\geq x_{2}\geq x_{3}}$. Уравнение определения стоимости клика ${\displaystyle c_{1}}$ первого объявления станет следующим:

${\displaystyle 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})}$

Подставляя ${\displaystyle V_{i}=V(b_{i},p_{i})=b_{i}\cdot p_{i}}$ получаем:

${\displaystyle V_{1}=((x_{1}-x_{2})\cdot V_{2}+(x_{2}-x_{3})\cdot V_{3}+x_{3}\cdot V_{4})/x_{1}}$

${\displaystyle 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-го уменьшается настолько, чтобы его ценность ${\displaystyle 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, она оказывается немонотонна.

• Английский аукцион
• Голландский аукцион
• Японский аукцион

• 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. https://web.archive.org/web/20081008174053/http://scienceoftheweb.org/15-396/lectures/lecture09.pdf. Retrieved on 2008-11-06.