Алгоритмы онлайн-ставок для рекламодателей с ограниченной отдачей от расходов

В последнее время онлайн-реклама превратилась в высококонкурентную, сложную индустрию стоимостью в несколько миллиардов долларов, где рекламодатели делают ставки на рекламные места в больших масштабах и с высокой частотой. Это привело к растущей потребности в эффективных алгоритмах `автоматического выставления ставок" для определения ставок по входящим запросам, чтобы максимизировать целевые показатели рекламодателей с учетом установленных ими ограничений. Наша работа сосредоточена на разработке эффективных онлайн-алгоритмов для одного рекламодателя, стремящегося максимизировать ценность в условиях часто встречающегося ограничения: отдачи от расходов (RoS). Мы оцениваем эффективность в терминах \ emph {сожаление} по сравнению с оптимальным алгоритмом, который знает все запросы априори.

Наш основной вклад - это алгоритм, который обеспечивает почти оптимальное снижение затрат при соблюдении указанного ограничения RoS. Мы также можем объединить наши результаты с уже существующими работами Балсейро, Лу и Миррокни ~\cite{BLM20} для достижения почти оптимального сожаления при соблюдении {подчеркнем {как} RoS, так и фиксированных бюджетных ограничений. Наша основная техническая идея заключается в использовании идей из литературы по (автономным) упаковочным линейным программам в дополнение к общим структурным свойствам, вытекающим из нашей аукционной модели.