Approximately Bisubmodular Regret Minimization in Billboard and Social Media Advertising

Basic Information

• Paper ID: 2510.09084
• Title: Approximately Bisubmodular Regret Minimization in Billboard and Social Media Advertising
• Authors: Dildar Ali, Suman Banerjee, Yamuna Prasad (Indian Institute of Technology Jammu)
• Classification: cs.GT (Game Theory), cs.DB (Databases), cs.DS (Data Structures and Algorithms)
• Publication Date: October 2025 (arXiv preprint)
• Paper Link: https://arxiv.org/abs/2510.09084

Abstract

This paper investigates regret minimization in multi-modal advertising environments, where influence providers must simultaneously allocate billboard slots and social media seed nodes to multiple advertisers. The authors propose a novel interaction effect model to capture both individual and combined effects of two distinct advertising media, and design two solution approaches: Projected Gradient Method (PGM) and Approximately Bisubmodular Local Search (ABLS). Experiments demonstrate that the proposed methods effectively reduce total regret across various demand settings.

Research Background and Motivation

Problem Definition

1. Core Problem: How should influence providers jointly allocate resources between billboard and social media advertising to minimize total regret?
2. Practical Scenario: Commercial companies submit daily proposals to influence providers containing influence requirements covering both online and offline modes, with conditional payments based on demand satisfaction.

Research Significance

• Commercial companies typically allocate 7-10% of annual revenue to advertising
• Existing research primarily focuses on advertisers' perspectives, lacking joint optimization from influence providers' viewpoint
• Traditional approaches overlook interaction effects between billboard and social media advertising

Limitations of Existing Methods

• Existing literature addresses billboard and social media advertising regret models separately
• Lacks a unified framework considering interaction effects between two advertising modes
• Existing regret models are non-monotonic and non-submodular, making performance guarantees unattainable

Core Contributions

1. First Joint Modeling: Proposes regret minimization problem simultaneously considering billboard and social network advertising
2. Theoretical Analysis: Proves the problem is NP-hard and inapproximable within any constant factor
3. Algorithm Design: Proposes two solution approaches: Projected Gradient Method (PGM) and Approximately Bisubmodular Local Search (ABLS)
4. Interaction Effect Model: Mathematically models interaction effects between billboard and social media advertising
5. Experimental Validation: Verifies method effectiveness on real datasets

Methodology Details

Task Definition

Input:

• Billboard slot set BS = {bs₁, bs₂, ..., bsₘ}
• Social network seed node set P = {p₁, p₂, ..., pᵣ}
• Advertiser set A = {a₁, a₂, ..., aₙ}, where each advertiser has influence requirement σᵢ and budget Kᵢ

Output:

• Allocation scheme L = {(S₁,P₁), (S₂,P₂), ..., (Sₙ,Pₙ)} minimizing total regret

Constraints:

• Mutual exclusivity constraint: Allocations to different advertisers cannot overlap
• Budget constraint: Allocation cost cannot exceed advertiser budget

Core Model

1. Influence Model

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

Where:

• I(S): Influence of billboard slot set S
• IG(P): Influence of seed node set P
• Ψ(S,P): Interaction effect

2. Interaction Effect Model

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

Where ρ ∈ 0,1 controls interaction intensity

3. Regret Model

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

Algorithm Design

1. Projected Gradient Method (PGM)

• Continuous optimization method based on Lovász extension
• Uses fractional vectors representing soft selection of slots and seeds
• Iteratively updates through subgradient descent and projection steps
• Time Complexity: O(T·m³·n·r·t + Tm²·n·r²·t + m⁴·n·r·t + m³·n·r²·t + m²·n·r³·t)

2. Approximately Bisubmodular Local Search (ABLS)

• Greedy local search method
• Orders advertisers by budget-to-requirement ratio in descending order
• Selects elements with maximum regret reduction per unit influence
• Time Complexity: O(m·r²·t + m²·r·t)

Technical Innovations

1. ε-Approximate Bisubmodularity: Extends traditional bisubmodular functions, allowing bounded deviation
2. Unified Framework: First to jointly model billboard and social media advertising
3. Interaction Effect Quantification: Provides mathematical method for calculating interaction effects
4. Theoretical Guarantees: Provides performance bounds for approximately bisubmodular functions

Experimental Setup

Datasets

1. Trajectory Data: Foursquare check-in data (April 2012 - January 2014)
   • 124,539 check-ins, 51,318 unique users
   • Covers major U.S. cities
2. Social Network Data: User social network snapshots
   • Old network: 95,994 friendship connections
   • New network: 129,864 friendship connections
3. Billboard Data: LAMAR dataset
   • New York: 716 billboards, 1,031,040 slots
   • Los Angeles: 1,483 billboards, 2,135,520 slots

Evaluation Metrics

• Total Regret: Sum of regrets across all advertisers
• Number of Satisfied Advertisers: Count of advertisers with satisfied demands
• Computation Time: Algorithm runtime

Comparison Methods

• Random Allocation (RA): Randomly selects billboard slots and seed nodes
• Top-k Allocation: Selects k most influential billboard slots and seed nodes

Key Parameters

Experimental Results

Main Results

1. Performance Under Different Demand Scenarios

Case 1 (Low α, Low λ): α ≤ 80%, λ ≤ 2%

• PGM and ABLS significantly outperform baselines
• Higher number of satisfied advertisers
• 30-40% regret reduction

Case 2 (Low α, High λ): α ≤ 80%, λ ≥ 5%

• Reduced oversupply when individual demands are high
• Proposed methods maintain advantage
• 25-35% regret reduction

Case 3 (High α, Low λ): α ≥ 100%, λ ≤ 2%

• Supply shortage increases overall regret
• PGM and ABLS still outperform baselines
• 15-25% regret reduction

Case 4 (High α, High λ): α ≥ 100%, λ ≥ 5%

• All methods face higher regret
• Multiple low-demand advertisers more favorable than few high-demand ones

2. Computational Efficiency Analysis

• ABLS generally has shorter computation time
• PGM shows significant computational overhead with increasing advertiser count
• Computation time increases for all methods as demand-to-supply ratio α increases

3. Parameter Sensitivity Analysis

• Increasing ε: Reduces runtime but increases regret
• Increasing δ: Penalizes large allocations, resulting in compact but less effective solutions
• Increasing γ: Emphasizes demand satisfaction, trading higher resource usage for lower regret
• Increasing ρ: Increases interaction intensity between billboard and seed nodes

Ablation Studies

1. Impact of Interaction Effects:
   • Total regret decreases from 341.37 to 295.14 when considering interaction effects
   • Demonstrates importance of interaction effect modeling
2. Impact of Probability Settings:
   • Trivalent probability setting performs best
   • Better simulates real-world variation in individual influence

Scalability Testing

• Large-scale scenario: λ = 1%, |A| = 100
• Small-scale scenario: λ = 20%, |A| = 5
• PGM and ABLS outperform baselines in both scenarios

Related Work

Influence Maximization Research

• Influence maximization in billboard advertising 6, 33, 36
• Influence maximization in social network advertising 17, 19, 24
• Joint label and slot selection problems 7

Regret Minimization Research

• Regret minimization in social networks 13, 30
• Regret minimization in billboard advertising 37
• Regret minimization under regional influence constraints 2, 4

Contribution of This Work

This is the first study addressing regret minimization considering both billboard and social network advertising simultaneously, filling a gap in the field.

Conclusions and Discussion

Main Conclusions

1. Problem Complexity: Proves multi-modal advertising regret minimization is NP-hard and inapproximable
2. Algorithm Effectiveness: PGM and ABLS effectively reduce regret across various settings
3. Importance of Interaction Effects: Considering interaction effects between billboard and social media significantly improves results
4. Practical Guidance: Multiple low-demand advertisers more favorable than few high-demand ones

Limitations

1. Computational Complexity: PGM has high computational overhead in large-scale scenarios
2. Parameter Sensitivity: Multiple parameters require careful tuning
3. Simplified Interaction Model: Interaction effect model may not fully capture real-world complexity
4. Static Setting: Does not consider dynamic advertiser arrival scenarios

Future Directions

1. Online Algorithms: Develop online algorithms handling dynamic advertiser arrivals
2. Parallel Optimization: Design parallel and distributed optimization frameworks for improved scalability
3. More Complex Interaction Models: Explore more accurate interaction effect modeling methods
4. Other Application Domains: Extend framework to other domains such as cloud computing resource allocation

In-Depth Evaluation

Strengths

1. Problem Novelty: First to study joint regret minimization in multi-modal advertising with significant practical importance
2. Theoretical Rigor: Provides comprehensive theoretical analysis including complexity proofs and approximation guarantees
3. Method Innovation:
   • Introduces ε-approximate bisubmodularity concept
   • Designs mathematical model for interaction effects
   • Develops two complementary algorithms
4. Comprehensive Experiments:
   • Uses real large-scale datasets
   • Considers multiple parameter settings and scenarios
   • Provides detailed ablation studies and sensitivity analysis

Weaknesses

1. Interaction Model Limitations: Linear combination assumption for interaction effects may be oversimplified
2. Computational Efficiency: PGM's high time complexity may pose challenges in practical applications
3. Parameter Dependency: Algorithm performance sensitive to multiple parameters, requiring careful tuning for deployment
4. Evaluation Limitations: Lacks comparison with more advanced baseline methods

Impact

1. Academic Contribution:
   • Initiates new research direction in multi-modal advertising optimization
   • Extends submodular optimization theory to approximately bisubmodular functions
   • Provides theoretical foundation for related optimization problems
2. Practical Value:
   • Directly applicable to digital advertising industry
   • Framework extensible to other resource allocation problems
   • Provides decision support tools for influence providers
3. Reproducibility: Paper provides detailed algorithm descriptions and experimental settings facilitating reproduction

Applicable Scenarios

1. Digital Advertising Platforms: Suitable for platforms managing both online and offline advertising resources
2. Resource Allocation Systems: Extensible to resource allocation in cloud computing, logistics, etc.
3. Influence Marketing: Applicable to joint optimization of social media marketing and traditional advertising

References

The paper cites 37 relevant references covering important works in influence maximization, submodular optimization, and advertising allocation, providing solid theoretical foundation for this research.

Overall Assessment: This is a high-quality research paper achieving good balance between theoretical innovation and practical application. Despite some limitations, its pioneering research direction and rigorous methodology design provide significant academic value and practical significance.