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

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

Определение

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Написанное в этом параграфе доказывает что назначение ставки равной вашей истинной оценки ценности оптимальна для вас^[6]. Для каждого участника ${\displaystyle b_{i}}$, пусть ${\displaystyle v_{i}}$ его истинная ценность товара ${\displaystyle t_{i}}$, допустим (без потери общности) что ${\displaystyle b_{i}}$ получает ${\displaystyle t_{i}}$ выставляя в качестве ставки свою истинную ценность товара. Тогда чистая прибыль ${\displaystyle U_{i}}$ достигаемая участником ${\displaystyle b_{i}}$ будет ${\displaystyle 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}}$${\displaystyle =\sum _{i}v_{i}-V_{N\setminus \{b_{i}\}}^{M}}$. Так как ${\displaystyle V_{N\setminus \{b_{i}\}}^{M}}$ не зависит от ${\displaystyle v_{i}}$, то максимизация чистой прибыли достигается согласно механизму аукциона при максимизации суммарного дохода ${\displaystyle \sum _{i}v_{i}}$ для выставленной ставки ${\displaystyle v_{i}}$. Другими словами, механизм аукциона таким образом назначает платежи, что при достижении максимального дохода игрока достигается максимальное значение прибыли. И задача участника не манипулировать ставками, а выставить такую ставку, которая будет равна его истинной ценности товара. Это позволяет участникам исключить из задачи оптимизации своей прибыли функцию платежей.

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

VCG-аукцион используется для продажи рекламных мест на интернет-площадках. В частности, эту модель аукциона используют Facebook^[7], Google (в своей партнерской сети)^[8] и Яндекс (на странице результатов поиска)^[9]. Другой популярной моделью продажи рекламных мест является аукцион обобщенной второй цены (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_{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})}$

Два слагаемых в этом уравнении сокращаются и получается: ${\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_{i}}$, ${\displaystyle x_{2}\cdot p_{i}}$, ${\displaystyle x_{3}\cdot p_{i}}$, то есть есть множители ${\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 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}}$

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