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

Определение

Для любого набора продаваемых на аукционе товаров ${\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).}$

Написанное в этом параграфе доказывает что назначение ставки равной вашей истинной оценки ценности оптимальна для вас[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-аукционе уже не имеет простого описания.

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