Abstract
The budget allocation problem is an optimization problem arising from advertising planning. In the problem, an advertiser has limited budgets to allocate across media, and seeks to optimize the allocation such that the largest fraction of customers can be influenced. It is known that this problem admits a (1-1/e)-approximation algorithm. However, no previous studies on this problem considered adjusting the allocation adaptively based upon the effect of the past campaigns, which is a usual strategy in the real setting. Our main contribution in this paper is to analyze adaptive strategies for the budget allocation problem. We define a greedy strategy, referred to as the insensitive policy, and then give a provable performance guarantee. This result is obtained by extending the adaptive submodularity, which is a concept studied in the context of active learning and stochastic optimization, to the functions over an integer lattice.
Introduction
In advertising planning, the budget allocation problem involves distributing a fixed financial resource across various media channels—such as television, social media, and print—to maximize the total number of influenced customers. While traditional approaches treat this as a static, one-shot optimization, real-world marketing is inherently dynamic. Advertisers frequently adjust their strategies based on real-time feedback from ongoing campaigns.
The core challenge in this domain is the principle of diminishing marginal returns, mathematically known as submodularity. As more resources are allocated to a single channel, the incremental benefit of each additional dollar typically decreases. While existing literature provides robust (1-1/e)-approximation algorithms for static sets, a theoretical framework for adaptive allocation over integer values (e.g., the number of ad slots) has been missing.
Theoretical Framework: Adaptive Submodularity over Integer Lattices
This paper bridges the gap between static and dynamic allocation by extending the concept of adaptive submodularity to functions defined over an integer lattice. Unlike standard submodularity, which deals with binary selections, this extension allows for the optimization of multi-unit resource allocations.
The "Insensitive" Policy
A key theoretical insight is the "Paradox of Sensitivity." A naive greedy strategy that reacts immediately to every piece of feedback (a "sensitive" greedy policy) can be suboptimal, as it may overreact to short-term noise. To counter this, the authors propose "insensitive" policies. These strategies wait until a significant portion of the budget is expended before re-evaluating the next allocation step, ensuring more stable and globally optimal decisions.
Proposed Algorithms
- Policy 1 (Bicriteria): This algorithm achieves the optimal (1 - 1/e) approximation ratio but may occasionally exceed the budget constraint by a factor of two.
- Policy 2: This policy strictly adheres to the budget while maintaining a provable approximation ratio of (e - 1)/2e.
Experimental Methodology
The proposed policies were evaluated against non-adaptive and sensitive greedy baselines using both synthetic and real-world datasets:
- Synthetic Bipartite Graphs: A simulated environment with 100 media outlets and 10,000 customers, utilizing power-law degree distributions to model realistic social structures.
- Twitter Follower Graph: A real-world dataset from KONECT (23,370 nodes, 33,101 arcs) used to test a general influence model where influence propagates through a network.
Results and Analysis
The experimental results consistently demonstrate that the proposed adaptive policies significantly outperform traditional methods.
Performance and Adaptivity Gap
In both synthetic and real-world scenarios, Policy 1 and Policy 2 achieved substantially higher objective values than the non-adaptive baseline. The "adaptivity gap"—the performance gain from being adaptive—was found to be as high as 58% in certain cases.
The Failure of Sensitivity
As shown in the figures, the "sensitive" greedy policy often performs worse than even the non-adaptive baseline. This confirms the theoretical intuition that being too reactive to immediate feedback can lead to poor long-term allocation decisions. By waiting to spend a certain proportion of the budget, the "insensitive" policies avoid being distracted by short-term noise.
Practical Consistency
While Policy 1 has a superior theoretical guarantee, Policy 2 performed almost identically in practice. This suggests that Policy 2 is a robust and practical choice for real-world applications where budget constraints must be strictly honored.
Conclusion
By extending adaptive submodularity to integer lattices, this work provides the first provable guarantees for dynamic budget allocation in advertising. The proposed insensitive policies offer a powerful tool for advertisers to maximize influence in uncertain, real-time environments. Beyond advertising, this framework has broad potential applications in fields such as sensor management and data summarization.
Summary updated