2025-11-22T09:19:16.214677

Approximately Bisubmodular Regret Minimization in Billboard and Social Media Advertising

Ali, Benerjee, Prasad
In a typical \emph{billboard advertisement} technique, a number of digital billboards are owned by an \emph{influence provider}, and several commercial houses approach the influence provider for a specific number of views of their advertisement content on a payment basis. If the influence provider provides the demanded or more influence, then he will receive the full payment else a partial payment. In the context of an influence provider, if he provides more or less than the advertisers demanded influence, it is a loss for him. This is formalized as 'Regret', and naturally, in the context of the influence provider, the goal will be to allocate the billboard slots among the advertisers such that the total regret is minimized. In this paper, we study this problem as a discrete optimization problem and propose two solution approaches. The first one selects the billboard slots from the available ones in an incremental greedy manner, and we call this method the Budget Effective Greedy approach. In the second one, we introduce randomness in the first one, where we do it for a sample of slots instead of calculating the marginal gains of all the billboard slots. We analyze both algorithms to understand their time and space complexity. We implement them with real-life datasets and conduct a number of experiments. We observe that the randomized budget effective greedy approach takes reasonable computational time while minimizing the regret.
academic

Approximately Bisubmodular Regret Minimization in Billboard and Social Media Advertising

基本信息

  • 论文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 (Game Theory), cs.DB (Databases), cs.DS (Data Structures and Algorithms)
  • 发表时间: 2025年10月 (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)

  • 基于Lovász扩展的连续优化方法
  • 使用分数向量表示时段和种子的软选择
  • 通过子梯度下降和投影步骤迭代更新
  • 时间复杂度：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.4-2014.1）
    • 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个广告牌时段和种子节点

关键参数

参数含义取值范围
α需求-供给比40%-120%
λ平均个体需求比1%-20%
γ未满足惩罚比0-1
δ基数惩罚比0-1
ε遗憾容忍参数0-0.1
ρ交互参数0-1

实验结果

主要结果

1. 不同需求场景下的性能

Case 1 (低α，低λ)：α ≤ 80%, λ ≤ 2%

  • PGM和ABLS显著优于基线方法
  • 满足的广告商数量更多
  • 遗憾减少30-40%

Case 2 (低α，高λ)：α ≤ 80%, λ ≥ 5%

  • 个体需求高时，过度供给减少
  • 所提方法仍保持优势
  • 遗憾减少25-35%

Case 3 (高α，低λ)：α ≥ 100%, λ ≤ 2%

  • 供给不足导致整体遗憾增加
  • PGM和ABLS仍优于基线
  • 遗憾减少15-25%

Case 4 (高α，高λ)：α ≥ 100%, λ ≥ 5%

  • 所有方法都面临较高遗憾
  • 少数高需求广告商不如多数低需求广告商有利

2. 计算效率分析

  • ABLS在大多数情况下计算时间更短
  • PGM在广告商数量较多时计算开销显著增加
  • 随着需求-供给比α增加，所有方法的计算时间都增加

3. 参数敏感性分析

  • ε增加：运行时间减少但遗憾增加
  • δ增加：惩罚大分配，导致紧凑但效果较差的解
  • γ增加：强调需求满足，以更高资源使用换取更低遗憾
  • ρ增加：广告牌和种子节点间交互强度增加

消融实验

  1. 交互效应的影响：
    • 考虑交互效应时总遗憾从341.37降至295.14
    • 证明了交互效应建模的重要性
  2. 概率设置的影响：
    • 三价概率设置（trivalency）表现最佳
    • 更好地模拟了现实中个体间影响力的变化

可扩展性测试

  • 大规模场景：λ = 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篇相关文献，涵盖了影响力最大化、子模优化、广告分配等多个研究领域的重要工作，为本研究提供了坚实的理论基础。

总体评价：这是一篇高质量的研究论文，在理论创新和实际应用之间取得了良好平衡。虽然存在一些局限性，但其开创性的研究方向和严谨的方法设计使其具有重要的学术价值和实用意义。