Задача о рюкзаке в контекстной рекламе для досок объявлений

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

Это мой первый опыт написания публичных статей (но вторая попытка), так что сорри, если что не так. Буду рад конструктивным комментариям.

Почему с не прямой монетизацией?

Потому что компании у которых монетизация прямая и достаточно хорошо вычисляется ROI могут себе позволить инвестировать в рекламный источник до предела его емкости, до тех пор пока инвестиции окупаются. А вот сайты типа досок объявлений зачастую не могут себе этого позволить. Т.к. не имеют жесткой связи с возвратом инвестиций, т.к. сами не продают товары и услуги, а работают по рекламной модели. Проще говоря: сегодня можно потратить очень много денег в контексте, но завтра от этого у classified сайта не появится больше рекламных контрактов.

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


В рамках данного эссе предположим, что нас уже есть медиаплан с бюджетом на следующий месяц и работающие рекламные аккаунты. Что дальше?

Как обычно выглядят рекламные аккаунты таких компаний?

1. Скорее всего рекламных аккаунтов будет минимум два. Яндекс Директ и Google Ads и в этом плане нам сильно повезло, потому что конкуренция всегда лучше ее отсутствия, и это прекрасное поле для здоровой оптимизации
2. Возможно рекламных аккаунтов будет еще больше, например из-за того что по разным аккаунтам разделены кампании по конверсии, проекту, команде сопровождения или по другому признаку
3. Внутри каждого рекламного аккаунта будет набор рекламных кампании (РК), допустим их названия будут указывать на некоторый способ классификации кампаний (например, по регионам, по проектам, по типам размещения, по платформе)

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


С таким большим набором РК довольно сложно рассчитывать и назначать дневные бюджеты в ручную. Описанием автоматизации этого процесса мы и займемся.

Взглянем в медиаплан на следующий месяц

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

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

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

Постановка задачи

Мало ли что в этом мире бывает, почти наверняка я уверен в следующем утверждении:

Количество узлов медиаплана будет всегда меньше или равно количеству рекламных кампаний во всех аккаунтах.

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

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

Кажется, это очень похоже на формулировку классической задачи о рюкзаке. В качестве объема рюкзака выступает размер бюджета, в качестве ценности камней выступают данные о стоимости конверсии. Но это так только отчасти. Дело в том что бюджет для рекламных кампаний может быть выбран любым дробным образом (до пределов емкости РК), а камни в задаче о рюкзаке не разделимы. Существует разновидность данной задачи — непрерывная задача о рюкзаке. Видимо ее формулировка больше подходит, наверно даже это именно она (если у вас будут комментарии по этому поводу буду рад их прочитать).

Так же мне кажется, что ошибившись в первоначальном названии задачи я тем не менее выбрал годное решение с помощью жадного алгоритма. Когда я разбирался с подходами к решению и методами решения задачи о рюкзаке я не смог применить метод динамического программирования для решения своего кейса (видимо причина именно в дробности). А вот жадный алгоритм по моим выкладкам подходил, собственно им и решается continuous knapsack problem.

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

Сильные стороны подхода

• Не важно из-за чего отдельная рекламная кампания стала вести себя лучше или хуже, как там поменялись настройки, ставки или рынок. Если такой бюджетировщик проходит по аккаунтам несколько раз в неделю со временем показатели такой кампании будут взвешены относительно других кампаний в пакете и ей будет назначен справедливый дневной бюджет.
• Можно перестать думать о бюджетировании кампаний и сосредоточить фокус внимания на заведении качестве и сопровождении РК
• Реализуется конкуренция между кампаниями Яндекс и Google. :)

Слабые стороны подхода

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

Особенности

• бюджеты между пакетами (узлами медиаплана) не перетекают

Комментарии по реализации

1. очевидно по кампаниям должен происходить ежедневный сбор статистики из аккаунтов контекстной рекламы и из систем счетчиков, например Google Analytics или Яндекс Метрика
2. результирующий отчет должен где-то храниться, в данном случае подходит любая БД, но удобнее всего на мой вкус Google BigQuery
3. Для анализа данных и построения отчетов можно использовать Jupyter блокнот. Так же на мой вкус лучше Google Colab, т.к. легко организуется совместная работа в команде (как в Google Docs)
4. Нужен сервер, на котором будет периодически запускать перебюджетировщик и происходить сбор статистики, обычно для такой задачи достаточно почти любого стандартного облачного сервера AWS или Google Cloud
5. Возможны варианты, для кампаний в нижней части списка, он назначения минимального бюджета, до приостановки. Но нужно продумать механизм периодической «реабилитации» таких кампаний и ответить на вопрос откуда брать данные по стоимости конверсии, если кампания давно остановлена

Пока у меня все.

Спасибо за внимание.