Математическое описание аукциона интернет-рекламы и разработка оптимального механизма аукциона

Эта статья подготовлена командой OPPO Internet Basic Technology Team, пожалуйста, укажите автора для перепечатки. В то же время приглашаем обратить внимание на нашу общедоступную учетную запись: OPPO_tech, чтобы поделиться с вами передовыми интернет-технологиями и деятельностью OPPO.

Аукционы знакомы большинству людей и имеют простой формат. Аукционная деятельность зародилась в древнем рабовладельческом обществе и восходит к свадебным аукционам в Древней Греции в 500 г. до н.э.

Однако аукцион представляет собой относительно сложную проблему, которая в основном отражается в понимании и исследовании сущности аукциона.Исследования по теории аукциона способствуют эффективной разработке механизма аукциона, тем самым способствуя рациональному и эффективному распределению ресурсов.

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

1. Говоря о моделировании аукционов на основе аукционов с отдельными позициями

1.1 Аукцион отдельных предметов

Аукцион по одному предмету является относительно простой формой среди многих форм аукциона и имеет множество сценариев применения.Конкретная проблема может быть выражена так: «У продавца есть товар на продажу, и несколько покупателей желают купить товар одновременно, но продавец не продает товар. Неясно, какова реальная стоимость товара для этих покупателей и сколько покупатель готов заплатить за него. В настоящее время продавец надеется, что подходящий Механизм аукциона может максимизировать ожидаемый доход от продажи предмета».

Для удобства исследования мы предполагаем, что все покупатели симметричны, а котировки раскрываются продавцам в соответствии с их истинными оценками стоимости товаров (то есть предположение о механизме прямого раскрытия выполняется). , Майерсон доказывает, что почему Осуществимый механизм имеет механизм прямого раскрытия информации, который может генерировать одинаковые ожидания покупателей и продавцов.Поэтому оптимальная конструкция механизма, основанная на механизме прямого раскрытия информации, также является общей, т. е. необходимо только найти наиболее оптимальный механизм в механизме прямого раскрытия Оптимальный механизм является оптимальным решением среди всех возможных механизмов.

Из вышеприведенного описания проблемы видно, что весь аукцион включает в себя оценку покупателя, котировку покупателя, распределение ресурсов продавца и оплату покупателем, как показано на рисунке ниже. Основная проблема аукционного механизма заключается в том, чтобы сформулировать или разработать механизм, который может максимизировать ожидаемую прибыль и обеспечить долгосрочное устойчивое развитие покупателей и продавцов.

1.2 Несколько основных допущений аукциона

Из описания проблемы аукциона отдельных предметов мы можем сделать следующие разумные основные предположения об аукционе:

нейтральный к риску

Цель покупателя на аукционе — максимизировать ожидаемую прибыль, которая представляет собой разницу между ожидаемым доходом покупателя и ожидаемой оплатой.

частная оценка

Оценка товара покупателем относится к частной информации покупателя, которую знает только он, продавец и другие покупатели не знают.

независимость

Все оценки товаров покупателями являются независимыми случайными величинами.

рациональное предположение

Ожидается, что покупатели с оценкой 0 также будут платить 0.

1.3 Математическое описание единичных аукционов

Как упоминалось ранее, механизм аукциона по сути представляет собой набор правил, которые определяют, какому покупателю будет отдан выставленный на аукцион лот на основе ставок участников, а также комиссии, которую должен заплатить победивший покупатель. Этот раздел будет моделировать аукцион на математическом языке. Предположим, продавец хочет продать товар с аукциона.Множество покупателей, участвующих в конкурсе, выражается как $N=\{1,2,...,n\}$ .

(а) Описание оценки

v=(v_1,v_2,...,v_n) заоценка покупателем стоимости предмета аукциона, v_i означает первыйОценка покупателем частной стоимости предмета, а также покупательМаксимальная цена, которую вы готовы заплатить за этот товар. Вектор оценкиЭто неизвестно продавцу, и покупатели не знают друг о друге.

Примечание: хотя покупатель v_i Продавцу это неизвестно, но продавец может анализировать данные с помощью анализа данных (например, анализа исторических данных о торгах рекламодателя рекламной платформой). v_i Имеется приблизительная оценка распределения v_i Распределение вероятности значения f_i(v_i) ,в $f_i:[\underline v_i,\overline v_i]\rightarrow \Re +,\, -\infty \lt \underline v_i\lt \overline v_i \lt +\infty$ , f_i(·) Монотонно возрастает в области определения и больше 0.

Точно так же продавцы могут использовать кумулятивное распределение вероятностей, чтобы привлечь покупателей.Максимальное значение оценивается как v_i Вероятность $F_i(v_i)=\int^{v_i}_{\underline v_i}f_i(x)dx$ , так как оценки между покупателями независимы друг от друга, вектор оценок всех покупателей v=(v_1,v_2,...,v_n) следовать распределению вероятностей $f(v)=\prod\limits_i f_i(v_i)$ , аналогично, за исключением того, что покупательКроме того, вектор оценки других покупателей $v_{-i}=(v_1,\dots,v_{i-1},v_{i+1}\dots,v_n)$ подчиняться распределению $f_{-i}(v)=\prod\limits_{j,j\ne i}f_j(v_j)$ .

(б) Правила распространения

Разработайте функцию распределения $q:v\to R^n$ , согласно вектору оценки покупателяЧтобы получить вероятность того, что предмет аукциона будет распределен каждому покупателю, в общем случае функция распределения удовлетворяет:

q_i>=0,\quad\sum\limits_iq_i\le1 \tag{1}

(c) Правила оплаты

Разработайте функцию ценообразования: $p:v\to R^n$ , указывающая комиссию, которую должен заплатить каждый покупатель после определения результата распределения.

Уже, (q,p) Диада описывает и определяет механизм аукциона.

2. Общий механизм аукциона интернет-рекламы

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

GFP (Обобщенная первая цена) Обобщенный аукцион первой цены

Правила распределения: распределяйте ресурсы в соответствии с уровнем ставки, и побеждает тот, у кого самая высокая цена;

Правила оплаты: После успешного аукциона вам необходимо оплатить свою ставку;

Особенности: простой и понятный, но поскольку участники торгов будут использовать «стратегию небольшой разницы», чтобы вызвать колебания цен, доход платформы нестабилен, а эффективность торгов невысока.

GSP (Обобщенная вторая цена) Обобщенный аукцион второй цены

Правила оплаты: после успешного аукциона участник торгов, предложивший вторую по величине ставку плюс минимальная стоимость, должен быть оплачен;

Особенности: GSP — это стабильный метод торгов с высокой функциональностью, а также основной метод торгов для интернет-рекламы на данном этапе. Недостатком является то, что ВСП не является механизмом «поощрения к правдивости», правдивость не является доминирующей стратегией, а результаты торгов не обязательно глобально оптимальны.

VCG (Vickrey-Clarke-Groves)

Правила оплаты: оплатить потерю полезности, причиненную другим рекламодателям в связи с их участием в аукционе;

Особенности: Он может обеспечить наилучшую социальную полезность. Говорить правду — слабо доминирующая стратегия для участников. Недостаток в том, что прибыль от того, что VCG говорит правду, является нижним пределом равновесия без зависти GSP. Фактическая реализация проекта более сложно, стоимость интерпретации высока, а преимущества платформы приводят к потерям.

3. Разработка оптимального аукционного механизма

Как упоминалось выше, несколько современных основных аукционных механизмов имеют свои преимущества и недостатки, поэтому существует ли оптимальный аукционный механизм с точки зрения максимизации ожидаемых преимуществ платформы? Чтобы ответить на этот вопрос, нам сначала нужно уточнить характеристики, которыми должен обладать оптимальный аукционный механизм:

а) вероятностное ограничение: товар распределен не более чем одному покупателю, т. е. формула (1) выполняется;

(b) Индивидуальная рациональность: покупатель участвует в аукционе добровольно, то есть ожидаемая прибыль покупателя, участвующего в аукционе, больше или равна 0;

(c) Совместимость стимулов: покупатели, предлагающие свои истинные оценки, сами являются оптимальными стратегиями, то есть покупатели могут достичь равновесия Нэша, когда они предлагают свои истинные оценки.

(d) В рамках этого аукционного механизма ожидаемый доход платформы максимизируется.

Механизм удовлетворения (a), (b), (c) таков:осуществимый механизм, а допустимый механизм, который одновременно удовлетворяет (d), естьоптимальный аукционный механизм. Существует ли оптимальный механизм аукциона?

Путем математического моделирования и описания ожидаемых доходов всех сторон, участвующих в аукционном процессе, всемирно известный магистр экономики Роджер Майерсон преобразовал проблему оптимального механизма аукциона в задачу математической оптимизации и дал оптимальное решение. Эта теория также получила Нобелевскую премию. по экономике в 2007 году. В этом разделе в основном будут представлены основная идея и математический вывод оптимального аукционного механизма.

3.1 Цели оптимизации и ограничения оптимального аукционного механизма

оптимизировать цель

Следуя обозначениям, описанным в разделе 1, механизм аукциона (q,p) Далее, во-первых, давайте определим выгоду покупателя. покупательПредложите оценку его истинной стоимости v_i Ожидаемый доход (то есть полезность для покупателя), когда:

U_i(q,p,v_i)=E_{-i}[v_iq_i(v_i,v_{-i})-p_i(v_i,v_{-i})] \tag{2}

Во-вторых, определим заработок продавца (платформы). Вот первое определение: продавец сохраняет стоимость предмета, удерживаемого как v_0 , то ожидаемый доход можно определить как:

U_0(p,q)=E_v[v_0(1-\sum\limits_iq_i(v))+\sum\limits_i p_i(v)] \tag{3}

Физическая интерпретация формулы (3) такова: предмет до знака «плюс» представляет собой стоимость предмета, удерживаемого продавцом, когда предмет не продан; предмет после знака «плюс» представляет собой общую стоимость успешно проданного предмета. На данный момент мы получили цель оптимизации оптимального механизма аукциона, то есть максимизацию ожидаемого дохода платформы, что математически выражается формулой (3).

Ограничения

Оптимальный механизм аукциона также является осуществимым механизмом, который должен удовлетворять следующим трем условиям:

а) вероятностные ограничения, т. е. формула (1) должна выполняться;

(b) Индивидуальные рациональные ограничения, т.е. удовлетворяют

(c) Ограничение совместимости поощрения: это доминирующая стратегия, когда покупатели делают ставки за свою истинную оценку. гипотетический покупательИстинная оценка v_i , которая подала заявку на s_i , а его ожидаемая доходность: $E_{-i}[v_iq_i(s_i,v_{-i})-p_i(s_i,v_{-i})]$ . Для поощрения говорить правду механизм должен обеспечивать установление следующих неравенств

U_i(q,p,v_i)\ge E_{-i}[v_iq_i(s_i,v_{-i})-p_i(s_i,v_{-i})] \tag{5}

Подводя итог: оптимальный механизм аукциона может быть математически описан как: максимизация при ограничениях U_0 решение (q,p) .

До сих пор мы определили математическое выражение того, как спроектировать оптимальный механизм в механизме прямого раскрытия.Хотя оно основано на механизме прямого раскрытия, Майерсон дал теоретическое доказательство: любой возможный механизм имеет механизм прямого раскрытия, который может производить Таким же образом, оптимальная конструкция механизма, основанная на механизме прямого раскрытия, является общей, то есть в механизме прямого раскрытия необходимо найти только оптимальный механизм, который является оптимальным решением среди всех возможных механизмов.

3.2. Достаточные и необходимые условия для допустимого механизма

Формулы описания (1), (4), (5) допустимого механизма имеют сильное физическое объяснение, но они не могут быть непосредственно использованы для вывода оптимального механизма, поэтому сначала выведем другую форму допустимого механизма (достаточное и необходимое) условие), то есть уравнения (7), (8), (9) ниже.

запомнить покупателяделать ставку s_i , вероятность выигрыша аукциона равна $Q(s_i)=E_{v-i}[q_i(s_i,v_{-i})]$ , то покупательделать ставку s_i Ожидаемый доход:

\begin{align}&E_{v-i}[v_iq_i(s_i,v_{-i})-p_i(s_i,v_{-i})] \\ & =E_{v-i}[(s_i+v_i-s_i)q_i(s_i,v_{-i})-p_i(s_i,v_{-i})] \\ &=U_i(q,p,s_i)+(v_i-s_i)Q_i(s_i) \end{align}

Подставьте его в уравнение (5), чтобы получить:

U_i(q,p,v_i)\ge U_i(q,p,s_i)+(v_i-s_i)Q_i(s_i)\tag{6}

Правая часть уравнения (6) состоит в том, что если покупатель делает ставку не в соответствии с истинной оценкой (то есть покупатель говорит неправду), его ожидаемый доход равен: ожиданию дополнительного дохода, полученного в результате нереалистичных торгов. (v_i-s_i)Q(s_i) , плюс ложная цитата s_i Ожидаемый доход при измерении стоимости предмета U_i(q,p,s_i) . Далее из формулы (6) можно получить:

(v_i-s_i)Q_i(s_i)\le U_i(q,p,v_i)-U_i(q,p,]s_i)\le (v_i-s_i)Q_i(v_i) \\ \forall i,有 Q_i(x_1)\le Q_i(x_2)\quad if\,x_1\le x_2, \quad x_1,x_2\in[\underline{v_i},\overline{v^i}] \tag{7}

Интуитивное объяснение формулы (7) таково: чем выше ставка покупателя, тем выше ставка ставки.

Из формулы (6) также можно вывести

\forall \delta,\,Q_i(s_i)\le U_i(q,p,s_i+\delta)-U_i(q,p,s_i)\le \delta Q_i(s_i+\delta)

Известен (7) Q(·) — монотонно возрастающая функция, удовлетворяющая условию интеграла Римана, поэтому имеем

\int_{\underline{vi}}^{v_i}Q_i(s_i)ds_i=U_i(q,p,v_i)-U(q,p,\underline{v_i})\tag{8}

Определено, что:

Доказательство необходимости относительно просто и опущено.

3.3 Решение оптимального аукционного механизма

При ограничениях (7), (8), (9) цель оптимизации (3) переписывается в виде следующей формулы (10) Конкретный процесс показан в приложении.

U_0(q,p)=E_v[v_0(1-\sum\limits_iq_i(v))+\sum\limits_ip_i(v)]\\ =\sum\limits_{i\in N}E_v[q_i(v)(v_i-v_0-\frac{1-F_i(v_i)}{f_i(v_i)})]+v_0-\sum\limits_{i\in N}U_i(q,p,\underline{v_i}) \tag{10}

Как было сказано ранее, задача проектирования оптимального аукционного механизма трансформируется в оптимизационную математическую задачу с ограничениями: при ограничениях (7), (8), (9) найти максимальное значение (10) (q,p) .

Решение правила оптимальной оплаты P

Из (10) видно, что p относится только к последнему элементу.Чтобы сделать (10) наибольшим, мы можем сделать

\sum\limits_{i\in N}U_i(q,p,\underline{v_i})=0 \tag{11}

Решая (11) следующим образом, можно увидеть, что при определении правила распределения q также определяется оптимальное правило оплаты, поэтому ядро решения оптимального механизма аукциона заключается в определении оптимального правила распределения.

\begin{align} &\sum\limits_{i\in N}U_i(q,p,\underline{v_i}) \Leftrightarrow \\ & \sum\limits_{i\in N}\left(U_i(q,p,v_i)-\int _{\underline{v_i}}^{v_i}Q_i(s)ds\right)=0\Leftrightarrow \\ & \sum\limits_{i\in N}\left(E_{v-i}\left[v_iq_i(v_i,v_{-i})-p_i(v_i,v_{-i})-\int_{\underline{v_i}}^{v_i}q_i(s,v_{=i})ds \right] \right) =0 \Leftrightarrow \\ & p_i(v)=v_iq_i(v)-\int_{\underline{v_i}}^{v_i}q_i(s,v_{-i})ds \end{align}

Решение правила оптимального размещения Q

Вывод Майерсона в статье указывает на то, что при допустимом механизме ожидаемый доход продавца полностью определяется распределением q и доходом покупателя при самой низкой цене, поэтому правило оптимального распределения можно описать как уравнение (12). Решение этой формулы более сложное, но при определенных условиях мы можем легко найти оптимальное решение.

q^*=arg\; max_qU_0(q,\; p) \\ =arg\; max_q\sum\limits_{i\in N}E_v\left[q_i(v)(v_i-v_0-\frac{1-F_i(v_i)}{f_i(v_i)})\right]+v_0-\sum\limits_{i\in N}U_i(q,p,\underline{v_i}) \\ =arg\; max_q E_v\left[ \sum\limits_{i\in N}q_i(v)(v_i-v_0-\frac{1-F_i(v_i)}{f_i(v_i)})\right] \tag{12}

Оптимальный механизм аукциона при обычном аукционе по отдельным позициям

Сначала определите функцию виртуального значения: $c(v_i)=v_i-\frac{1-F_i(v_i)}{f_i(v_i)}$ ,в соответствии ссвойства, легко получить c(v_i) существует $[\underline v_i,\overline v_i]$ непрерывна и ограничена. если c(v_i) является строго монотонно возрастающей функцией, о которой говорят, что она удовлетворяет предположению о регулярности, которое выполняется для многих функций распределения.

Рассмотрим аукцион единичного предмета при общем предположении: выставленный на аукцион предмет является единственным и выигрывает не более одного покупателя. На данный момент оптимальное решение (12) имеет вид: «Назначить элементы c(v_i) Крупнейший неотрицательный покупатель». Неотрицательное требование $v_i\ge \frac{1-F_i(v_i)}{f_i(v_i)}$ , но в то же время он должен удовлетворять допустимым ограничениям механизма, особенно уравнению (7). Поскольку это аукцион, который удовлетворяет общепринятым предположениям, а именно v_i чем больше соответствующий c(v_i) Чем больше вероятность выигрыша Q_i(v_i) Также больше, удовлетворяют (7).

Соответствующая функция ценообразования в настоящее время такова:

\begin{align} & p_i(v)=v_i q_i(v)-\int_{\underline{v_i}}^{v_i}q_i(s,v_{-i})ds \\ & =\begin{cases} 0,\quad q_i(v)=0 \\ v_i-\int^{v_i}_{v_i^\land}1ds,\quad q_i(v)=1 \end{cases} \\ & =\begin{cases} 0,\quad q_i(v)=0 \\ c^{-1}(max_{j,j\ne i}c(v_j)),\quad q_i(v)=1 \end{cases} \end{align}

в $v_i^\land = inf\{s_i|c_i(s_i)\ge v_0 \; and \; c_j(s_i)\ge c_j(v_j),\quad \forall i\ne j\}$ , то есть в покупателевыше точки выигрышной оценки.

Из вышеизложенного видно, что этот оптимальный аукционный механизм фактически является модифицированным аукционом Викери, который эквивалентен использованию $\frac{1-F_i(v_i)}{f_i(v_i)}$ Чтобы зарезервировать цену, в соответствии с правилом распределения «получает самую высокую цену» и в соответствии с правилом выставления счетов с двумя ценами.

Для аукционов с несколькими позициями и несколькими покупателями математическое выражение ожидаемого дохода продавца и каждого покупателя станет очень сложным, и будет трудно дать формальное решение.Как правило, для получения приближенного оптимального решения даются некоторые сильные предположения. .

использованная литература

Optimal Auction Design, Myersion, 1981, Mathematics of Operations Reseach

Кроме того, процесс вывода прилагаемой формулы (10)