Русская Википедия:Механизм Викри — Кларка — Гровса

Содержание

Текст

Текст

Текст

Текст

Текст

Текст

Текст

Текст

Текст

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

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

Определение

Для любого набора продаваемых на аукционе товаров <math>M = \{t_1,\ldots,t_m\}</math> и набора участников <math>N = \{b_1,\ldots,b_n\}</math>, пусть <math>V^M_N</math> — это «общественная выгода» (в качестве «общества» выступает множество участников) от результата VCG-аукциона при данном наборе ставок. Для участника <math>b_i</math> и товара <math>t_j</math> ставкой участника будет <math>v_{i}(t_{j})</math>.

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

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

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

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

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

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

Примеры

Пример #1

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

Пример #2

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

Если игрок <math>b_2</math> не принимает участие в аукционе, участник <math>b_1</math> всё равно получает товар <math>t_1</math>, то есть для него ничего не меняется. Текущая полученная ценность будет равна <math>10</math>, следовательно с игрока <math>b_2</math> будет списано <math>10-10=0</math>.

Если игрок <math>b_1</math> не принимает участие в аукционе, товар <math>t_1</math> достаётся игроку <math>b_2</math>, и имеет ценность <math>5</math>. Текущая полученная ценность будет равна <math>3</math>, следовательно с игрока <math>b_1</math> будет списано <math>5-3=2</math>.

Пример #3

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

<math>p_i = \left[ \max_{a \in A} \sum_{j \neq i} b_j(a) \right] - \sum_{j \neq i} b_j(a^*) </math>.

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

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

Написанное в этом параграфе доказывает что назначение ставки равной вашей истинной оценки ценности оптимальна для вас. Для каждого участника <math>b_i</math>, пусть <math>v_i</math> его истинная ценность товара <math>t_i</math>, допустим (без потери общности) что <math>b_i</math> получает <math>t_i</math> выставляя в качестве ставки свою истинную ценность товара. Тогда чистая прибыль <math>U_i</math> достигаемая участником <math>b_i</math> будет <math>U_i = v_i-\left(V^{M}_{N \setminus \{b_i\}}-V^{M \setminus \{t_i\}}_{N \setminus \{b_i\}}\right)=\sum_{i}v_i-\sum_{j\neq i}v_j+V^{M\setminus \{t_i\}}_{N\setminus \{b_i\}}-V^M_{N\setminus\{b_i\}}=\sum_i v_i-V^{M\setminus \{t_i\}}_{N\setminus \{b_i\}}+V^{M\setminus \{t_i\}}_{N\setminus \{b_i\}}-V^M_{N\setminus\{b_i\}}</math><math>=\sum_i v_i-V^M_{N\setminus\{b_i\}}</math>. Так как <math>V^M_{N\setminus\{b_i\}}</math> не зависит от <math>v_i</math>, то максимизация чистой прибыли достигается согласно механизму аукциона при максимизации суммарного дохода <math>\sum_i v_i</math> для выставленной ставки <math>v_i</math>. Другими словами, механизм аукциона таким образом назначает платежи, что при достижении максимального дохода игрока достигается максимальное значение прибыли. И задача участника не манипулировать ставками, а выставить такую ставку, которая будет равна его истинной ценности товара. Это позволяет участникам исключить из задачи оптимизации своей прибыли функцию платежей.

Запишем разницу <math>U_i - U_j = \left[v_i + V^{M \setminus \{t_i\}}_{N \setminus \{b_i\}}\right] - \left[v_j + V^{M \setminus \{t_j\}}_{N \setminus \{b_i\}}\right] </math> между чистой прибылью <math>U_i</math> участника <math>b_i</math> выставляющего ставку равную его истинной ценности <math>v_i</math> полученного товара <math>t_i</math>, и чистую прибыль <math>U_j</math> участника <math>b_i</math> при неправдивой стратегии выставления ставки <math>v'_i</math> за товар <math>t_i</math> и получившим товар <math>t_j</math> с истинной ценностью <math>v_j</math>. <math>\left[v_j + V^{M \setminus \{t_j\}}_{N \setminus \{b_i\}}\right] </math> это максимум общего дохода полученного в результате неправдивой стратегии выставления ставок. Но назначение товара <math>t_j</math> участнику <math>b_i</math> отличается от назначении товара <math>t_i</math> участнику <math>b_i</math> что доставляет максимум суммарному доходу. Следовательно <math>\left[v_i + V^{M \setminus \{t_i\}}_{N \setminus \{b_i\}}\right] - \left[v_j + V^{M \setminus \{t_j\}}_{N \setminus \{b_i\}}\right]\geq 0 </math> и <math>U_i\geq U_j</math> ч.т.д.

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

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

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

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

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

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

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

Тогда для случая трех мест (<math>K = 3</math>) для вычисления стоимости клика первого объявления <math>c_1</math> нужно решить уравнение: <math>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)</math>

Два слагаемых в этом уравнении сокращаются и получается: <math>V(c_1, p_1) = V(b_4, p_4).</math>

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

<math>c_1 = b_4 \cdot p_4 / p_1.</math>

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

<math>c_2 = b_4 \cdot p_4 / p_2.</math>

<math>c_3 = b_4 \cdot p_4 / p_3.</math>

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

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

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

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

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

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

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

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

<math>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)</math>

Подставляя <math>V_i = V(b_i, p_i) = b_i \cdot p_i</math> получаем:

<math>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</math>

<math>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)</math>

Таким образом ставка 1-го уменьшается ровно настолько, чтобы его ценность <math>V(c_1, p_1)</math> стала равна средне-взвешенному ценностей объявлений показанных ниже и одного невидимого объявления. Веса в этом усреднении определяются кликабельностью позиций.