Optimizing budget allocation among channels and influencers

Noga Alon, Iftah Gamzu, Moshe Tennenholtz

Research output: Chapter in Book/Report/Conference proceedingConference contribution

68 Scopus citations


Brands and agencies use marketing as a tool to influence customers. One of the major decisions in a marketing plan deals with the allocation of a given budget among media channels in order to maximize the impact on a set of potential customers. A similar situation occurs in a social network, where a marketing budget needs to be distributed among a set of potential influencers in a way that provides high-impact. We introduce several probabilistic models to capture the above scenarios. The common setting of these models consists of a bipartite graph of source and target nodes. The objective is to allocate a fixed budget among the source nodes to maximize the expected number of influenced target nodes. The concrete way in which source nodes influence target nodes depends on the underlying model. We primarily consider two models: a source-side influence model, in which a source node that is allocated a budget of k makes k independent trials to influence each of its neighboring target nodes, and a target-side influence model, in which a target node becomes influenced according to a specified rule that depends on the overall budget allocated to its neighbors. Our main results are an optimal (1 - 1/e)-approximation algorithm for the source-side model, and several inapproximability results for the target-side model, establishing that influence maximization in the latter model is provably harder.

Original languageEnglish (US)
Title of host publicationWWW'12 - Proceedings of the 21st Annual Conference on World Wide Web
Number of pages8
StatePublished - 2012
Externally publishedYes
Event21st Annual Conference on World Wide Web, WWW'12 - Lyon, France
Duration: Apr 16 2012Apr 20 2012

Publication series

NameWWW'12 - Proceedings of the 21st Annual Conference on World Wide Web


Other21st Annual Conference on World Wide Web, WWW'12

All Science Journal Classification (ASJC) codes

  • Computer Networks and Communications


  • Approximation algorithms
  • Budget allocation
  • Influence models


Dive into the research topics of 'Optimizing budget allocation among channels and influencers'. Together they form a unique fingerprint.

Cite this