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

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

Формальное описание

Определение

Для любого набора продаваемых на аукционе товаров $M=\{t_{1},\ldots ,t_{m}\}$ и набора участников $N=\{b_{1},\ldots ,b_{n}\}$, пусть $V_{N}^{M}$ — это «общественная выгода» (в качестве «общества» выступает множество участников) от результата VCG-аукциона при данном наборе ставок. Для участника $b_{i}$ и товара $t_{j}$ ставкой участника будет $v_{i}(t_{j})$.

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

Участник $b_{i}$, чья ставка для товара $t_{j}$, а именно $v_{i}(t_{j})$, является максимальной среди участников, выигрывает аукцион, но платит $V_{N\setminus \{b_{i}\}}^{M}-V_{N\setminus \{b_{i}\}}^{M\setminus \{t_{j}\}}$ что равно размеру неполученной выгоды оставшихся участников от его выигрыша (сам выигрыш определён остальными участниками).

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

Множество участников-конкурентов для $b_{i}$ определяются следующим образом: $N\setminus \{b_{i}\}$. Когда товар $t_{j}$ доступен для конкурентов, они могут достичь благосостояния $V_{N\setminus \{b_{i}\}}^{M}$. Выигрыш товара участником $b_{i}$ уменьшает набор доступных товаров до $M\setminus \{t_{j}\}$, но всё ещё достижимым является благосостояние $V_{N\setminus \{b_{i}\}}^{M\setminus \{t_{j}\}}$. Разница между этими двумя уровнями благосостояния и будет являться упущенной выгодой остальных игроков при условии, что игрок $b_{i}$ получает товар $t_{j}$ (игроки-конкуренты позволили ему выиграть). Эта величина зависит от заявок участников-конкурентов и не известна для участника $b_{i}$.

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

Выигравший участник аукциона, чьей ставкой является его истинная ценность $A$ товара $t_{j}$, $v_{i}(t_{j})=A,$ получает максимум прибыли $A-\left(V_{N\setminus \{b_{i}\}}^{M}-V_{N\setminus \{b_{i}\}}^{M\setminus \{t_{j}\}}\right).$

Примеры

Пример #1

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

Пример #2

Предположим, что есть два игрока, $b_{1}$ и $b_{2}$, и два товара, $t_{1}$ и $t_{2}$, и каждый участник может получить только один товар. Пусть $v_{i,j}$ это ценность товара $t_{j}$ для игрока $b_{i}$. Положим $v_{1,1}=10$, $v_{1,2}=5$, $v_{2,1}=5$, и $v_{2,2}=3$. Видно, что оба игрока $b_{1}$ и $b_{2}$ предпочтут получить товар $t_{1}$; однако «социально оптимальная» схема проведения аукциона назначает товар $t_{1}$ игроку $b_{1}$ (так что его полученная ценность будет равна $10$) и товар $t_{2}$ игроку $b_{2}$ (так что его полученная ценность будет равна $3$). Таким образом, общая полученная ценность будет равна $13$, что является оптимальным.

Если игрок $b_{2}$ не принимает участие в аукционе, участник $b_{1}$ всё равно получает товар $t_{1}$, то есть для него ничего не меняется. Текущая полученная ценность будет равна $10$, следовательно с игрока $b_{2}$ будет списано $10-10=0$.

Если игрок $b_{1}$ не принимает участие в аукционе, товар $t_{1}$ достаётся игроку $b_{2}$, и имеет ценность $5$. Текущая полученная ценность будет равна $3$, следовательно с игрока $b_{1}$ будет списано $5-3=2$.

Пример #3

Рассмотрим многотоварный аукцион. Пусть в аукционе участвует $n$ участников, $n$ домов, и ценности ${\tilde {v}}_{ij}$ дома $j$ для участника $i$. Возможным результатом проведения аукциона в этом случае может являться паросочетание в двудольном графе, с помощью которого могут быть составлены пары домов с участниками аукционов. Если мы знаем ценности, то максимизация общественного благосостояния ограничивается поиском паросочетания максимального веса в соответствующем двудольном графе. Если мы не знаем ценностей, то вместо этого можно запросить ставки ${\tilde {b}}_{ij}$, которые готов заплатить участник $i$ за дом $j$. Обозначим $b_{i}(a)={\tilde {b}}_{ik}$ если участник $i$ получает дом $k$ в паросочетании $a$. Теперь вычислим $a^{*}$, паросочетание максимального веса в двудольном графе в случае назначения в ставок в качестве весов и вычислим

$p_{i}=\left[\max _{a\in A}\sum _{j\neq i}b_{j}(a)\right]-\sum _{j\neq i}b_{j}(a^{*})$.

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

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

Написанное в этом параграфе доказывает что назначение ставки равной вашей истинной оценки ценности оптимальна для вас. Для каждого участника $b_{i}$, пусть $v_{i}$ его истинная ценность товара $t_{i}$, допустим (без потери общности) что $b_{i}$ получает $t_{i}$ выставляя в качестве ставки свою истинную ценность товара. Тогда чистая прибыль $U_{i}$ достигаемая участником $b_{i}$ будет $U_{i}=v_{i}-\left(V_{N\setminus \{b_{i}\}}^{M}-V_{N\setminus \{b_{i}\}}^{M\setminus \{t_{i}\}}\right)=\sum _{i}v_{i}-\sum _{j\neq i}v_{j}+V_{N\setminus \{b_{i}\}}^{M\setminus \{t_{i}\}}-V_{N\setminus \{b_{i}\}}^{M}=\sum _{i}v_{i}-V_{N\setminus \{b_{i}\}}^{M\setminus \{t_{i}\}}+V_{N\setminus \{b_{i}\}}^{M\setminus \{t_{i}\}}-V_{N\setminus \{b_{i}\}}^{M}$$=\sum _{i}v_{i}-V_{N\setminus \{b_{i}\}}^{M}$. Так как $V_{N\setminus \{b_{i}\}}^{M}$ не зависит от $v_{i}$, то максимизация чистой прибыли достигается согласно механизму аукциона при максимизации суммарного дохода $\sum _{i}v_{i}$ для выставленной ставки $v_{i}$. Другими словами, механизм аукциона таким образом назначает платежи, что при достижении максимального дохода игрока достигается максимальное значение прибыли. И задача участника не манипулировать ставками, а выставить такую ставку, которая будет равна его истинной ценности товара. Это позволяет участникам исключить из задачи оптимизации своей прибыли функцию платежей.

Запишем разницу $U_{i}-U_{j}=\left[v_{i}+V_{N\setminus \{b_{i}\}}^{M\setminus \{t_{i}\}}\right]-\left[v_{j}+V_{N\setminus \{b_{i}\}}^{M\setminus \{t_{j}\}}\right]$ между чистой прибылью $U_{i}$ участника $b_{i}$ выставляющего ставку равную его истинной ценности $v_{i}$ полученного товара $t_{i}$, и чистую прибыль $U_{j}$ участника $b_{i}$ при неправдивой стратегии выставления ставки $v'_{i}$ за товар $t_{i}$ и получившим товар $t_{j}$ с истинной ценностью $v_{j}$. $\left[v_{j}+V_{N\setminus \{b_{i}\}}^{M\setminus \{t_{j}\}}\right]$ это максимум общего дохода полученного в результате неправдивой стратегии выставления ставок. Но назначение товара $t_{j}$ участнику $b_{i}$ отличается от назначении товара $t_{i}$ участнику $b_{i}$ что доставляет максимум суммарному доходу. Следовательно $\left[v_{i}+V_{N\setminus \{b_{i}\}}^{M\setminus \{t_{i}\}}\right]-\left[v_{j}+V_{N\setminus \{b_{i}\}}^{M\setminus \{t_{j}\}}\right]\geq 0$ и $U_{i}\geq U_{j}$ ч.т.д.

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

VCG-аукцион используется для продажи рекламных мест на интернет-площадках. В частности, эту модель аукциона используют Facebook, Google (в своей партнерской сети) и Яндекс (на странице результатов поиска). Другой популярной моделью продажи рекламных мест является аукцион обобщенной второй цены (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_{1})+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_{i}$, $x_{2}\cdot p_{i}$, $x_{3}\cdot p_{i}$, то есть есть множители $\{x_{1},x_{2},x_{3}\}$ меньше 1, определяющие мультипликативный поправки к исходной вероятности клика. Назовем их кликабельностями позиций. Не теряя общности, рассмотрим случай, когда позиции расположены в порядке убывания кликабельности, то есть $x_{1}\geq x_{2}\geq 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}$ получаем:

$c_{1}\cdot p_{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})$ стала равна средне-взвешенному ценностей объявлений показанных ниже и одного невидимого объявления. Веса в этом усреднении определяются кликабельностью позиций.