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

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

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

Определение

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

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

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

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

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

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

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

ПримерыПравить

Пример #1Править

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

Пример #2Править

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

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

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

Пример #3Править

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

$p_i=\left[\underset{a\in <!--\; \in \; -->A}{max}\underset{j\ne <!--\; \ne \; -->i}{\sum <!--\; \sum \; -->}{b}_j(a)\right]-<!--\; -\; -->\underset{j\ne <!--\; \ne \; -->i}{\sum <!--\; \sum \; -->}{b}_j(a^{\ast <!--\; \ast \; -->})$$p_{i}=\left[\max _{{a\in A}}\sum _{{j\neq i}}b_{j}(a)\right]-\sum _{{j\neq i}}b_{j}(a^{*})$ .

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

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

Написанное в этом параграфе доказывает что назначение ставки равной вашей истинной оценки ценности оптимальна для вас. Для каждого участника $b_i$$b_{i}$ , пусть $v_i$$v_{i}$  его истинная ценность товара $t_i$$t_{i}$ , допустим (без потери общности) что $b_i$$b_{i}$  получает $t_i$$t_{i}$  выставляя в качестве ставки свою истинную ценность товара. Тогда чистая прибыль $U_i$$U_{i}$  достигаемая участником $b_i$$b_{i}$  будет $U_i=v_i-<!--\; -\; -->\left(V_{N\setminus <!--\; \setminus \; -->\{b_i\}}^M-<!--\; -\; -->V_{N\setminus <!--\; \setminus \; -->\{b_i\}}^{M\setminus <!--\; \setminus \; -->\{t_i\}}\right)=\underset{i}{\sum <!--\; \sum \; -->}{v}_i-<!--\; -\; -->\underset{j\ne <!--\; \ne \; -->i}{\sum <!--\; \sum \; -->}{v}_j+V_{N\setminus <!--\; \setminus \; -->\{b_i\}}^{M\setminus <!--\; \setminus \; -->\{t_i\}}-<!--\; -\; -->V_{N\setminus <!--\; \setminus \; -->\{b_i\}}^M=\underset{i}{\sum <!--\; \sum \; -->}{v}_i-<!--\; -\; -->V_{N\setminus <!--\; \setminus \; -->\{b_i\}}^{M\setminus <!--\; \setminus \; -->\{t_i\}}+V_{N\setminus <!--\; \setminus \; -->\{b_i\}}^{M\setminus <!--\; \setminus \; -->\{t_i\}}-<!--\; -\; -->V_{N\setminus <!--\; \setminus \; -->\{b_i\}}^M$$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}$ $=\underset{i}{\sum <!--\; \sum \; -->}{v}_i-<!--\; -\; -->V_{N\setminus <!--\; \setminus \; -->\{b_i\}}^M$$=\sum _{i}v_{i}-V_{{N\setminus \{b_{i}\}}}^{M}$ . Так как $V_{N\setminus <!--\; \setminus \; -->\{b_i\}}^M$$V_{{N\setminus \{b_{i}\}}}^{M}$  не зависит от $v_i$$v_{i}$ , то максимизация чистой прибыли достигается согласно механизму аукциона при максимизации суммарного дохода $\underset{i}{\sum <!--\; \sum \; -->}{v}_i$$\sum _{i}v_{i}$  для выставленной ставки $v_i$$v_{i}$ . Другими словами, механизм аукциона таким образом назначает платежи, что при достижении максимального дохода игрока достигается максимальное значение прибыли. И задача участника не манипулировать ставками, а выставить такую ставку, которая будет равна его истинной ценности товара. Это позволяет участникам исключить из задачи оптимизации своей прибыли функцию платежей.

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

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

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

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

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

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

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

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

Тогда для случая трех мест ($K=3$$K=3$ ) для вычисления стоимости клика первого объявления $c_1$$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_{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).$$V(c_{1},p_{1})=V(b_{4},p_{4}).$ 

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

$c_1=b_4\cdot <!--\; \cdot \; -->p_4/p_1.$$c_{1}=b_{4}\cdot p_{4}/p_{1}.$ 

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

$c_2=b_4\cdot <!--\; \cdot \; -->p_4/p_2.$$c_{2}=b_{4}\cdot p_{4}/p_{2}.$ 

$c_3=b_4\cdot <!--\; \cdot \; -->p_4/p_3.$$c_{3}=b_{4}\cdot p_{4}/p_{3}.$ 

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

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

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

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

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

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

Случай различной кликабельности местПравить

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

$x_1\cdot <!--\; \cdot \; -->V(c_1,p_1)+x_2\cdot <!--\; \cdot \; -->V(b_2,p_2)+x_3\cdot <!--\; \cdot \; -->V(b_3,p_3)=x_1\cdot <!--\; \cdot \; -->V(b_2,p_2)+x_2\cdot <!--\; \cdot \; -->V(b_3,p_3)+x_3\cdot <!--\; \cdot \; -->V(b_4,p_4)$$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 <!--\; \cdot \; -->p_i$$V_{i}=V(b_{i},p_{i})=b_{i}\cdot p_{i}$  получаем:

$c_1\cdot <!--\; \cdot \; -->p_1=((x_1-<!--\; -\; -->x_2)\cdot <!--\; \cdot \; -->V_2+(x_2-<!--\; -\; -->x_3)\cdot <!--\; \cdot \; -->V_3+x_3\cdot <!--\; \cdot \; -->V_4)/x_1$$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 <!--\; \cdot \; -->b_2\cdot <!--\; \cdot \; -->p_2+(x_2-<!--\; -\; -->x_3)\cdot <!--\; \cdot \; -->b_3\cdot <!--\; \cdot \; -->p_3+x_3\cdot <!--\; \cdot \; -->b_4\cdot <!--\; \cdot \; -->p_4)/(x_1\cdot <!--\; \cdot \; -->p_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)$$V(c_{1},p_{1})$  стала равна средне-взвешенному ценностей объявлений показанных ниже и одного невидимого объявления. Веса в этом усреднении определяются кликабельностью позиций.