2015/08/05 by Noa Avigdor-Elgrabli, Avigdor-Elgrabli, Noa, Gideon Blocq +5
Computer Science · Decision Sciences · Mathematics · #Auction Theory and Applications #Bounded function #Budget constraint #Computer Science and Game Theory (cs.GT) #Computer science #Data Structures and Algorithms (cs.DS) #Economics #FOS: Computer and information sciences #Function (biology) #Game Theory and Applications #Knapsack problem #Mathematical economics #Mathematical optimization #Mathematics #Maximization #Microeconomics #Monotone polygon #Optimization and Search Problems #Set (abstract data type) #Social and Information Networks (cs.SI) #Submodular set function #Viral marketing #cs.DS #cs.GT #cs.SI
paper · pdf · doi:10.48550/arxiv.1508.01059
published in arXiv (Cornell University) (Cornell University)
openalex publication_date 2015/08/05 · arxiv created 2018/03/12 · arxiv updated 2018/03/13 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
The research of influence propagation in social networks via word-of-mouth processes has been given considerable attention in recent years. Arguably, the most fundamental problem in this domain is influence maximization, where the goal is to identify a seed set of individuals that can trigger a large cascade of influence in the network. While there has been significant progress regarding this problem and its variants, one basic shortcoming of the models is that they lack the flexibility in the way the budget is allocated to individuals. Indeed, budget allocation is a critical issue in advertising and viral marketing. Taking the other point of view, known models allowing flexible budget allocation do not take into account the influence spread in the network. We introduce a generalized model that captures both budgets and influence propagation simultaneously. For the offline setting, we identify a large family of budget-based propagation functions that admit tight approximation guarantee. This family extends most of the previously studied influence models, including the well-known Triggering model. We establish that any function in this family implies an instance of a monotone submodular function maximization over the integer lattice subject to a knapsack constraint. This problem is known to admit an optimal (1-1/e)-approximation. We also study the price of anarchy of the multi-player game that extends the model and establish tight results. For the online setting, in which an unknown subset of agents arrive in a random order and the algorithm needs to make an irrevocable budget allocation in each step, we develop a 1/(15e)-competitive algorithm. This setting extends the secretary problem, and its variant, the submodular knapsack secretary problem. Notably, our algorithm improves over the best known approximation for the latter problem, even though it applies to a more general setting.