Приблизительная минимизация сожаления двойной субмодулярности в рекламе на билбордах и социальных сетях

Основная информация

• ID статьи: 2510.09084
• Название: Approximately Bisubmodular Regret Minimization in Billboard and Social Media Advertising
• Авторы: Dildar Ali, Suman Banerjee, Yamuna Prasad (Indian Institute of Technology Jammu)
• Классификация: cs.GT (Теория игр), cs.DB (Базы данных), cs.DS (Структуры данных и алгоритмы)
• Дата публикации: Октябрь 2025 г. (препринт arXiv)
• Ссылка на статью: https://arxiv.org/abs/2510.09084

Аннотация

В данной работе исследуется проблема минимизации сожаления в многомодальной рекламной среде, где поставщики влияния должны одновременно распределять временные слоты на билбордах и узлы-семена в социальных сетях между несколькими рекламодателями. Авторы предлагают новую модель эффектов взаимодействия для захвата индивидуальных и комбинированных эффектов двух различных рекламных средств и разрабатывают два решения: метод проектируемого субградиента (PGM) и приблизительный локальный поиск двойной субмодулярности (ABLS). Экспериментальные результаты показывают, что предложенные методы эффективно снижают общее сожаление при различных параметрах спроса.

Исследовательский контекст и мотивация

Определение проблемы

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

Значимость исследования

• Коммерческие компании обычно тратят 7-10% годового дохода на рекламу
• Существующие исследования в основном сосредоточены на перспективе рекламодателя, отсутствует совместная оптимизация с точки зрения поставщика влияния
• Традиционные методы игнорируют эффекты взаимодействия между билбордами и социальными сетями

Ограничения существующих подходов

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

Основные вклады

1. Первое совместное моделирование: Предложена проблема минимизации сожаления, одновременно рассматривающая рекламу на билбордах и в социальных сетях
2. Теоретический анализ: Доказано, что проблема является NP-трудной и не поддается приблизительному решению в пределах любого постоянного коэффициента
3. Разработка алгоритмов: Предложены два решения: метод проектируемого субградиента (PGM) и приблизительный локальный поиск двойной субмодулярности (ABLS)
4. Модель эффектов взаимодействия: Математическое моделирование эффектов взаимодействия между билбордами и социальными сетями
5. Экспериментальная верификация: Проверка эффективности методов на реальных наборах данных

Подробное описание методов

Определение задачи

Входные данные:

• Множество временных слотов на билбордах BS = {bs₁, bs₂, ..., bsₘ}
• Множество узлов-семян в социальной сети P = {p₁, p₂, ..., pᵣ}
• Множество рекламодателей A = {a₁, a₂, ..., aₙ}, каждый с требованием по охвату σᵢ и бюджетом Kᵢ

Выходные данные:

• Схема распределения L = {(S₁,P₁), (S₂,P₂), ..., (Sₙ,Pₙ)}, минимизирующая общее сожаление

Ограничения:

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

Основная модель

1. Модель охвата

Φ(S,P) = I(S) + IG(P) + Ψ(S,P)

где:

• I(S): охват множества временных слотов на билбордах S
• IG(P): охват множества узлов-семян P
• Ψ(S,P): эффект взаимодействия

2. Модель эффекта взаимодействия

Ψ(S,P) = ρ · Σᵤ∈U (1 - ∏ᵦ∈S(1 - Pr(u,b))) · Σᵥ∈P Pr'(u,v)

где ρ ∈ 0,1 контролирует интенсивность взаимодействия

3. Модель сожаления

R(Naᵢ) = Kaᵢ · (1 - γ · min(Φ(Saᵢ,Paᵢ),σaᵢ)/σaᵢ) + δ · log(1 + |Saᵢ| + |Paᵢ|)

Разработка алгоритмов

1. Метод проектируемого субградиента (PGM)

• Метод непрерывной оптимизации на основе расширения Ловаша
• Использует дробные векторы для представления мягкого выбора слотов и семян
• Итеративное обновление через спуск по субградиенту и шаги проектирования
• Временная сложность: O(T·m³·n·r·t + Tm²·n·r²·t + m⁴·n·r·t + m³·n·r²·t + m²·n·r³·t)

2. Приблизительный локальный поиск двойной субмодулярности (ABLS)

• Метод жадного локального поиска
• Упорядочивание рекламодателей по убыванию отношения требования к бюджету
• Выбор элементов с максимальным сокращением сожаления на единицу охвата
• Временная сложность: O(m·r²·t + m²·r·t)

Технические инновации

1. ε-приблизительная двойная субмодулярность: Расширение традиционных функций двойной субмодулярности с допуском ограниченного отклонения
2. Единая структура: Первое единое моделирование рекламы на билбордах и в социальных сетях
3. Количественная оценка эффектов взаимодействия: Математический метод расчета эффектов взаимодействия
4. Теоретические гарантии: Гарантии производительности для приблизительно двойных субмодулярных функций

Экспериментальная установка

Наборы данных

1. Данные траектории: Данные регистрации Foursquare (апрель 2012 - январь 2014)
   • 124 539 регистраций, 51 318 уникальных пользователей
   • Охватывает основные города США
2. Данные социальной сети: Снимок социальной сети пользователей
   • Старая сеть: 95 994 связи дружбы
   • Новая сеть: 129 864 связи дружбы
3. Данные билбордов: Набор данных LAMAR
   • Нью-Йорк: 716 билбордов, 1 031 040 временных слотов
   • Лос-Анджелес: 1 483 билборда, 2 135 520 временных слотов

Метрики оценки

• Общее сожаление: Сумма сожаления всех рекламодателей
• Количество удовлетворённых рекламодателей: Количество рекламодателей, требования которых удовлетворены
• Время вычисления: Время выполнения алгоритма

Методы сравнения

• Random Allocation (RA): Случайный выбор временных слотов на билбордах и узлов-семян
• Top-k Allocation: Выбор k наиболее влиятельных временных слотов на билбордах и узлов-семян

Ключевые параметры

Экспериментальные результаты

Основные результаты

1. Производительность при различных сценариях спроса

Случай 1 (низкий α, низкий λ): α ≤ 80%, λ ≤ 2%

• PGM и ABLS значительно превосходят базовые методы
• Большее количество удовлетворённых рекламодателей
• Сокращение сожаления на 30-40%

Случай 2 (низкий α, высокий λ): α ≤ 80%, λ ≥ 5%

• При высоком индивидуальном спросе избыточное предложение снижается
• Предложенные методы сохраняют преимущество
• Сокращение сожаления на 25-35%

Случай 3 (высокий α, низкий λ): α ≥ 100%, λ ≤ 2%

• Недостаточное предложение приводит к увеличению общего сожаления
• PGM и ABLS остаются лучше базовых методов
• Сокращение сожаления на 15-25%

Случай 4 (высокий α, высокий λ): α ≥ 100%, λ ≥ 5%

• Все методы сталкиваются с высоким сожалением
• Несколько рекламодателей с высоким спросом менее выгодны, чем множество с низким спросом

2. Анализ вычислительной эффективности

• ABLS обычно имеет более короткое время вычисления
• PGM имеет значительные вычислительные затраты при большом количестве рекламодателей
• Время вычисления всех методов увеличивается с ростом отношения спроса к предложению α

3. Анализ чувствительности параметров

• Увеличение ε: Время выполнения снижается, но сожаление увеличивается
• Увеличение δ: Штрафует большие распределения, приводя к компактным, но менее эффективным решениям
• Увеличение γ: Подчёркивает удовлетворение спроса, обменивая более высокое использование ресурсов на более низкое сожаление
• Увеличение ρ: Усиливает интенсивность взаимодействия между билбордами и узлами-семенами

Абляционные эксперименты

1. Влияние эффектов взаимодействия:
   • При учёте эффектов взаимодействия общее сожаление снижается с 341.37 до 295.14
   • Доказывает важность моделирования эффектов взаимодействия
2. Влияние вероятностных установок:
   • Трёхзначная вероятностная установка показывает лучшие результаты
   • Лучше моделирует вариативность влияния между индивидами в реальности

Тестирование масштабируемости

• Крупномасштабный сценарий: λ = 1%, |A| = 100
• Маломасштабный сценарий: λ = 20%, |A| = 5
• PGM и ABLS превосходят базовые методы в обоих сценариях

Связанные работы

Исследования максимизации охвата

• Максимизация охвата в рекламе на билбордах 6, 33, 36
• Максимизация охвата в рекламе социальных сетей 17, 19, 24
• Проблема совместного выбора меток и временных слотов 7

Исследования минимизации сожаления

• Минимизация сожаления в социальных сетях 13, 30
• Минимизация сожаления в рекламе на билбордах 37
• Минимизация сожаления при ограничениях территориального охвата 2, 4

Вклад данной работы

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

Заключение и обсуждение

Основные выводы

1. Сложность проблемы: Доказано, что проблема минимизации сожаления в многомодальной рекламе является NP-трудной и не поддаётся приблизительному решению
2. Эффективность алгоритмов: PGM и ABLS эффективно снижают сожаление при различных параметрах
3. Важность эффектов взаимодействия: Учёт эффектов взаимодействия между билбордами и социальными сетями значительно улучшает результаты
4. Практические рекомендации: Множество рекламодателей с низким спросом более выгодно, чем несколько с высоким спросом

Ограничения

1. Вычислительная сложность: PGM имеет высокие вычислительные затраты в крупномасштабных сценариях
2. Чувствительность параметров: Множество параметров требуют тщательной настройки
3. Упрощение модели взаимодействия: Модель эффектов взаимодействия может не полностью захватить сложность реальности
4. Статическая установка: Не рассматривается сценарий динамического поступления рекламодателей

Направления будущих исследований

1. Онлайн-алгоритмы: Разработка онлайн-алгоритмов для обработки динамического поступления рекламодателей
2. Параллельная оптимизация: Разработка параллельных и распределённых оптимизационных структур для повышения масштабируемости
3. Более сложные модели взаимодействия: Исследование более точных методов моделирования эффектов взаимодействия
4. Другие области применения: Расширение структуры на распределение ресурсов облачных вычислений и другие области

Глубокая оценка

Преимущества

1. Новизна проблемы: Первое исследование совместной минимизации сожаления в многомодальной рекламе с важным практическим значением
2. Теоретическая строгость: Полный теоретический анализ, включая доказательства сложности и гарантии приблизительности
3. Инновационность методов:
   • Введение концепции ε-приблизительной двойной субмодулярности
   • Разработка математической модели эффектов взаимодействия
   • Разработка двух взаимодополняющих алгоритмов
4. Полнота экспериментов:
   • Использование реальных крупномасштабных наборов данных
   • Рассмотрение множества параметрических установок и сценариев
   • Подробные абляционные эксперименты и анализ чувствительности

Недостатки

1. Ограничения модели взаимодействия: Предположение о линейной комбинации эффектов взаимодействия может быть чрезмерно упрощённым
2. Вычислительная эффективность: Высокая временная сложность PGM может создать проблемы при практическом применении
3. Зависимость от параметров: Производительность алгоритма чувствительна к множеству параметров, требующих тщательной настройки при развёртывании
4. Ограничения оценки: Отсутствие сравнения с большим количеством передовых базовых методов

Влияние

1. Академический вклад:
   • Открытие нового направления исследований в оптимизации многомодальной рекламы
   • Расширение теории субмодулярной оптимизации на приблизительно двойные субмодулярные функции
   • Теоретическая основа для связанных задач оптимизации
2. Практическая ценность:
   • Прямое применение в индустрии цифровой рекламы
   • Расширяемость структуры на другие задачи распределения ресурсов
   • Инструмент поддержки принятия решений для поставщиков влияния
3. Воспроизводимость: Статья содержит подробное описание алгоритмов и экспериментальных установок, облегчающих воспроизведение

Области применения

1. Платформы цифровой рекламы: Применимо к платформам, требующим одновременного управления ресурсами онлайн и офлайн рекламы
2. Системы распределения ресурсов: Расширяемо на задачи распределения ресурсов в облачных вычислениях, логистике и других областях
3. Маркетинг влияния: Применимо к совместной оптимизации маркетинга в социальных сетях и традиционной рекламы

Библиография

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

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