Optimizing Marketing Budgets for Social Influence: A Generalized Fractional Incentives Framework
Authors: Abhishek K. Umrawal, Akhil Bhimaraju, Eliot W. Robson, Lav R. Varshney
Organizations: University of Illinois Urbana-Champaign, Urbana, IL 61801, USA · Narmi, New York, NY 10016, USA · Stony Brook University, Stony Brook, NY 11794 USA
Marketing managers routinely allocate limited budgets across individuals in social networks whose responsiveness and influence vary substantially. We study the problem of Budgeted Generalized Fractional Influence Maximization (BGFIM), which captures the allocation of continuous levels of marketing spend across users in the presence of heterogeneous response and network spillovers. In this framework, adoption probabilities are governed by user-specific response functions that capture both baseline propensity and marginal responsiveness, while incentive costs vary across users. We propose a scalable solution approach based on a discrete greedy procedure with provable approximation guarantees, enabling tractable optimization under realistic budget constraints. Our formulation generalizes prior influence maximization models by allowing heterogeneous response and cost structures, providing a more flexible representation of targeted marketing interventions. Using experiments on multiple large-scale networks, we show that continuous allocation strategies can outperform standard heuristics and improve influence outcomes under heterogeneous conditions, and we illustrate how the framework can support profit-oriented decision making by identifying budget levels that balance marginal returns and costs. Overall, our results highlight the value of fine-grained budget allocation in networked marketing environments and offer a scalable approach for data-driven marketing resource allocation.
Figures & tables
Network Name
Type
Node Count
Edge Count
Wikipedia ( Leskovec et al. 2010b , Leskovec et al. 2010a )
Directed
7,115
201,524
Facebook ( Leskovec and Mcauley 2012 )
Undirected
4,039
176,468
Deezer ( Rozemberczki and Sarkar 2020 )
Undirected
28,281
185,504
DBLP ( Yang and Leskovec 2012 )
Undirected
317,080
2,099,732
Amazon ( Yang and Leskovec 2012 )
Undirected
334,863
1,851,744
Table 1: Basic information about each network. The data was retrieved from Leskovec and Krevl (2014) .
Figure 1: Influence vs. Budget ( K ) for different networks.
Figure 2: Runtime (in seconds) vs. Budget ( K ) for different networks.
Graph
Budget
Payoff
Search Time
Initial Computation Time
Wikipedia
2.82
275.54
63.21
212.30
Facebook
1.58
45.57
25.94
61.99
Deezer
0.59
29.90
9.12
39.34
DBLP
7.65
250.41
75.13
265.84
Amazon
7.14
295.35
60.50
219.26
Table 2: Results of optimal budget selection across networks. Experiments used a maximum budget of K=8.00 , price per unit p=0.5 , cost per unit c=80.0 , and ϵ=0.1 .
We introduce a new budgeted framework for online influence maximization, considering the total cost of an advertising campaign instead of the common cardinality constraint on a chosen influencer set. Our approach better models the real-world setting where the cost of influencers varies and advertisers want to find the best value for their overall social advertising budget. We propose an algorithm assuming an independent cascade diffusion model and edge level semi-bandit feedback, and provide both theoretical and experimental results. Our analysis is also valid for the cardinality constraint setting and improves the state of the art regret bound in this case.
Pierre Perrault, Jennifer Healey, Zheng Wen +1
Adobe Research, San Jose, CA · ENS Paris-Saclay · DeepMind +1
We study a graph bandit setting where the objective of the learner is to detect the most influential node of a graph by requesting as little information from the graph as possible. One of the relevant applications for this setting is marketing in social networks, where the marketer aims at finding and taking advantage of the most influential customers. The existing approaches for bandit problems on graphs require either partial or complete knowledge of the graph. In this paper, we do not assume any knowledge of the graph, but we consider a setting where it can be gradually discovered in a sequential and active way. At each round, the learner chooses a node of the graph and the only information it receives is a stochastic set of the nodes that the chosen node is currently influencing. To address this setting, we propose BARE, a bandit strategy for which we prove a regret guarantee that scales with the detectable dimension, a problem dependent quantity that is often much smaller than the number of nodes.
Alexandra Carpentier, Michal Valko
Universität Potsdam · SequeL team, Inria Lille - Nord Europe
We study the dynamic allocation of indivisible resources to strategic agents under long-term constraints, where the planner aims to maximize social welfare, satisfy multiple constraints, and elicit near-truthful reports. We find standard primal-dual methods fragile in this setting: agents easily manipulate their reports to distort dual variables, sacrificing social efficiency for individual utility. To address this, we propose the Incentive-Aware Primal-Dual (IAPD) framework. On the primal side, we integrate three components to suppress manipulation: a VCG-based payment neutralizes immediate misreporting benefits, while epoch-based lazy updates and random exploration together ensure potential future gains are outweighed by immediate penalties. On the dual side, to overcome a learning barrier due to lazy updates -- which we call the "price of incentives" -- we design a novel optimistic online learning algorithm, O-FTRL-FP. It utilizes a fixed-point oracle to resolve the circular dependency between optimistic dual variables and the resulting allocations. Ultimately, our mechanism attains O~(T) social welfare regret, satisfies all long-term constraints, and induces a near-truthful equilibrium. It also smoothly generalizes to multi-unit multi-demand allocation problems. Notably, this O~(T) regret near-matches the non-strategic Ω(T) lower bound, demonstrating that incentive-awareness can be accommodated at nearly no cost.
Yan Dai, Negin Golrezaei, Patrick Jaillet
Operations Research Center, MIT. · Sloan School of Management, MIT. · Department of EECS, MIT.