YIELD OPTIMIZATION FOR THE AD NETWORKS

Full Text

Для монетизации контента интернет-сайтов владельцы управляют ходом рекламных кампаний, каждая из которых может быть показана на рекламных площадках (сайтах) [1]. Каждая рекламная кампания обладает набором параметров и характеристик (стоимость, расписание доставки), изменяя которые, можно управлять доставкой этих кампаний, тем самым изменяя величину дохода и прибыли, которые могут быть получены в данной интернет-сети. У каждого сайта также есть ряд параметров (размер баннеров, которые могут быть показаны на этом сайте, величина издержек, которую должны заплатить владельцу данного сайта в случае, если показы перепродаются третьим лицом, например медийным агенством, и т. д.). Основной задачей владельца интернет-сети является максимизация прибыли за счет повышения суммарного дохода с показов/кликов/действий идущих рекламных кампаний. Данная статья описывает метод, повышающий доходность кампаний за счет совокупной оптимизации сети. Постановка задачи и описание исходных данных Предположим, что в рассматриваемой нами замкнутой сети существуют паблишеры Pi, каждому из которых принадлежат сайты SPij: паблишер P1 содержит сайты SP11, SP12, SP13; паблишер P2 содержит сайты SP21, SP22, SP23; паблишер P3 содержит сайты SP31, SP32, SP33. Каждый из этих паблишеров не принадлежит владельцу рассматриваемой нами интернет-сети, поэтому владелец вынужден платить паблишерам за все показы, сделанные на их сайтах. Для каждого паблишера характерна собственная модель взимания платы, информацию о которой можно найти в табл. 1. Таблица Модели взимания платы паблишерами с владельца интернет-сети Паблишер Сайт Модель Число доступных показов () P1 SP11 Владелец интернет-сети платит 0,3 условной единицы (у. е.) за каждую тысячу показов данному паблишеру 5 000 SP12 Владелец интернет-сети платит 0,7 у. е. за каждую тысячу показов данному паблишеру 20 000 SP13 Владелец интернет-сети отдает паблишеру 60 % всех доходов, полученных на данном сайте 30 000 P2 SP21 0,4 у. е. за каждую тысячу показов 10 000 SP22 0,5 у. е. за каждую тысячу показов 20 000 SP23 60 % всех доходов 10 000 P3 SP31 50 % всех доходов 5 000 SP32 0,5 у. е. за каждую тысячу показов 5 000 SP33 60 % всех доходов 0 В рассматриваемой нами сети существует совокупность рекламных кампаний Ci, каждая из которых может идти только на определенных сайтах: кампания C1 на SP11, SP12, SP21; кампания C2 на SP12, SP13, SP21, SP31; кампания C3 на SP11, SP22, SP32. Таблица Состояние кампаний на рассматриваемый j-й момент времени Кампания Стоимость за 1000 показов (T), у. е. Запланированное кол-во показов по контракту Число показов, набранное к j-му моменту времени () Число показов, которое осталось набрать () Число показов, которое должно быть набрано к j-му моменту времени согласно плану () C1 0,5 20000 5000 15000 3000 C2 0,6 30000 10000 20000 10000 C3 1 9000 8000 1000 9000 Предположим, что мы рассматриваем сеть не в 0-й момент времени, когда ни одна из кампаний еще не успела сделать ни единого показа, а в некоторый j-й момент времени, когда каждая из кампаний набрала определенное количество показов и обладает статистикой, достаточной для того, чтобы судить о поведении кампании в сети. Каждая из рассматриваемых нами кампаний оплачивается за 1000 показов (т. н. CPM-кампания). Совокупность характеристик i-й кампании к данному моменту j может быть найдена в табл. 2. Количество показов, которое каждая из кампаний набрала на соответствующем сайте, может быть найдено в табл. 3. Таблица 3 Статистика распределения первоначальных показов кампаний по сайтам Сайт (число доступных показов) Кампания (остаток показов) - 1500 - 20000 - 1000 - 5000 2000 0,2 4000 0,7 - 20000 1000 -0,2 5000 -0,1 - 30000 3000 0,24 - 10000 2000 0,1 1500 0,2 - 20000 3000 0,5 - 10000 - 5000 500 0,3 - 5000 1000 0,5 - 0 Введение понятия относительной прибыльности Данная задача оптимизации очень схожа с транспортной задачей, которая может быть решена методами линейного программирования [2] (напр., симплекс-метод [3]). Основное отличие заключается в том, что в классической транспортной задаче в качестве веса указывались затраты на перевозку i-го груза в j-й пункт назначения. В случае оптимизации прибыли интернет-сети мы вводим понятие нормы прибыльности (или относительной прибыльности) i-кампании на j м сайте (). Норма прибыльности - это относительная величина прибыли, получаемая владельцем интернет-сети с тысячи показов, которые будут набраны i-й кампанией на j-м сайте и которая вычисляется согласно формуле , (1) где - это доход, который получает i-я кампания на j-м сайте. Для случая CPM кампаний - это расходы, которые владелец интернет-сети вынужден заплатить владельцу j-го сайта (паблишеру) за число показов, набранных i-й кампанией на этом сайте. Данная величина зависит от модели, по которой владелец сети рассчитывается с паблишером; - это число показов, набранных i-й кампанией на j-м сайте. Тогда задача максимизации прибыли интернет-сети сводится к максимизации целевой функции вида (2) при условиях, что - сумма показов i-й кампании не превосходит число показов, которое осталось набрать кампании по контракту; - сумма показов кампаний на j-м сайте не превосходит величины свободных показов на этом сайте. Согласно (1) рассчитаем нормы прибыльности для каждой i-й кампании на j м сайте. В табл. 3 рассчитанные данные даны курсивом. При этом ожидаемое число показов можно прогнозировать, например, на основе метода, изложенного авторами в [4]. Построение оптимального плана сети Существует множество способов построения опорного и оптимального плана для решения транспортной задачи. В данном случае рассмотрим самый простой из них, который является достаточно быстрым и позволяет решать задачи большой размерности, что наиболее актуально для задач оптимизации интернет-сети. Алгоритм следующий. Ищем ячейку ij с максимальным значением нормы прибыльности . Полагаем, что число показов выбирается как максимум из числа показов, которое осталось набрать i-й кампании (с учетом предыдущих итераций), и числа свободных показов j-го сайта (с учетом предыдущих итераций). Из числа оставшихся показов i-й кампании вычитаем число показов , полученное на 2-м шаге. Из числа доступных показов j-го сайта вычитаем число показов , полученное на 2-м шаге. Переходим к пункту 1 - ищем ячейку с максимальным значением нормы прибыльности, за исключением ячеек, найденных на предыдущих шагах. Повторяем поиск до тех пор, пока не распределится число показов для всех кампаний либо не закончится число свободных показов всех сайтов. Рассмотрим алгоритм, описанный выше, на конкретном примере, согласно табл. 3. Ищем ячейку ij с максимальным значением нормы прибыльности - . Число показов . а) - кампания C3 набрала все свои показы. б) . Ищем следующую ячейку ij с максимальным значением нормы прибыльности - . Число показов . а) б) - сайт SP31 исчерпал все свободные показы. Ищем следующую ячейку ij с максимальным значением нормы прибыльности - . Число показов . а) - кампания C2 набрала все свои показы. б) . Ищем следующую ячейку ij с максимальным значением нормы прибыльности - . Число показов . а) . б) - сайт SP11 исчерпал все свободные показы. Таблица 4 Распределение числа показов, необходимое для построения оптимального плана Сайт (число доступных показов) Кампания (остаток показов) - 1500 - 20000 - 1000 - 5000 4000 0,2 1000 0,7 - 20000 1000 -0,2 -0,1 - 30000 15000 0,24 - 10000 10000 0,1 0,2 - 20000 0,5 - 10000 - 5000 5000 0,3 - 5000 0,5 - 0 Ищем следующую ячейку ij с максимальным значением нормы прибыльности - Число показов . а) . б) - сайт SP21 исчерпал все свободные показы. Ищем следующую ячейку ij с максимальным значением нормы прибыльности - . Число показов . а) - кампания C1 набрала все свои показы. б) . Таким образом, оптимальная прибыль для владельца интернет-сети - это величина целевой функции, рассчитываемая по (2), Детали распределения представлены в табл. 4 Определение прироста прибыли за счет построения оптимального плана Зная оптимальное распределение показов, полученное в предыдущем пункте, сравним величину прибыли, которую сможет получить владелец интернет-сети при оптимальном распределении показов, с прибылью, которую получил бы этот же владелец при условии, что в сети ничего бы не изменилось и кампании продолжили бы набирать показы на сайтах пропорционально тому, что они уже набрали на этих сайтах ранее. Предположим, что кампания Сi наберет оставшиеся свои показы на сайте Sj согласно формуле , (3) где - число свободных показов на сайте Sj с учетом предыдущих итераций распределения показов, - число показов, которое осталось набрать кампании Сi; - число показов, которое не удалось распределить на предыдущих итерациях для кампании Сi; - число показов, которое набрала кампания Сi на сайте Sj; - сумма показов, которую набрала кампания Сi на своих сайтах на момент распределения; - сумма показов, которую набрала кампания Сi на своих сайтах на момент распределения, за исключением сайтов, на которых не удалось полностью распределить показы Ci на предыдущих итерациях. Согласно (3) и данным табл. 3 рассчитаем оставшееся число показов на каждом сайте Sj. Так как формула (3) зависит от числа доступных показов на каждом сайте Sj, то будем исходить из предположения, что абстрактный рекламный сервер в первую очередь будет доставлять более дорогие кампании. Тогда получим следующее распределение (табл. 5). Таблица 5 Итог перераспределения показов Кампания Сайт Число оставшихся показов (с учетом ) (с учетом ) (с учетом ) Таким образом, прибыль для владельца интернет-сети без отсутствия оптимизации и при условии, что кампании набирают показы на сайтах пропорционально тому, что они набирали ранее, определяется величиной целевой функции. Прибыль, которую получит владелец интернет-сети в результате оптимального распределения, будет в ~2,7 раз выше по сравнению с прибылью, которую получил бы владелец, если бы не предпринимал попытки оптимизации. Способы исполнения оптимального плана средствами рекламных серверов После построения оптимального плана основной сложностью является приведение его в жизнь с помощью средств, которые предоставляет рекламный сервер, используемый владельцем интернет-сети. Другими словами, если для достижения оптимальности необходимо, чтобы кампания C1 набрала 4000 показов на сайте SP11, а кампания C2 - 15000 показов на сайте SP13, то с помощью средств рекламного сервера нам необходимо так настроить расписание каждой кампании, чтобы оптимальное количество показов было набрано данной кампанией строго на определенном сайте. Иногда это непросто реализовать на практике, так как не каждый рекламный сервер предоставляет возможность задания точного количества показов, которые могут быть набраны определенной кампанией на определенном сайте. Тогда существует несколько основных способов: 1) более общий подход - создание дополнительных кампаний от исходной родительской кампании Ci, так называемых sweet spot кампаний, каждая из которых будет идти строго на определенном сайте со строго определенной целью согласно оптимальному плану; 2) задание доли показов от общего числа оставшихся показов данной кампании Ci, определенной для каждого из сайтов. Так, например, рекламный сервер Open Ad Stream (OAS) предоставляет функциональность Site Tiers, когда любые сайты кампании можно объединить в группы и указать долю показов, которую будет набирать каждая группа от общего числа всех показов кампании. Выводы Для того чтобы составить оптимальный план, максимизирующий прибыль, которую может получить владелец интернет-сети, необходимо: вычислить норму прибыльности для каждого сайта и кампании, запущенных в этой сети; посчитать количество доступных показов, которое может быть набрано на каждом сайте. Количество доступных показов может считаться как в общем для всех кампаний, идущих на каждом конкретном сайте, так и для каждой кампании по отдельности, учитывая ее специфику (приоритет, размер баннеров и специфику таргетинга). Оптимальный план должен считаться для всех кампаний и сайтов, имеющихся в сети. В противном случае план будет неоптимальным и тяжело приводимым в действительность. Для того чтобы реализовать оптимальный план в жизнь, нужно: в первую очередь (если рекламный сервер поддерживает механизм Site Tiers) использовать механизм Site Tiers, так как сложность сети в этом случае увеличиваться не будет за счет создания дополнительных кампаний; если механизм Site Tiers недоступен на уровне рекламного сервера, то реализовать оптимальный план за счет создания дополнительных кампаний, но при этом сложность сети будет увеличиваться. В том случае, если мы имеем большую и сложную сеть, в которой необходимо изменить все кампании за раз, чтобы достигнуть оптимального расписания, необходимо начинать оптимизацию: с кампаний, которые вносят наибольший вклад в оптимальный план, так как в этом случае достигнутая прибыль будет наибольшей; либо с паблишеров/сайтов, которые вносят наибольший вклад в оптимальный план. Число кампаний и сайтов, которые могут изменяться первоначально, может варьироваться, при этом потенциальная прибыль возрастает в случае, если есть больше возможностей для изменения.

About the authors

Dmitry A Elkin

OOO Maxifier Development

Email: cscmp@iccs.ru
Director of optimization. 349, Novo-Sadovaya st., Samara, 443125, Russia

Igor A Minakov

Institution of the Russian Academy of Sciences Institute for the Control of Complex Systems of RAS

Email: cscmp@iccs.ru
(Dr. Sci. (Techn.)), Senior Scientist. 61, Sadovaya st., Samara, 443020, Russia

Simon I Volman

OOO Maxifier Development

Email: cscmp@iccs.ru
Director of Technology. 349, Novo-Sadovaya st., Samara, 443125, Russia

References

Supplementary files