  Campaigners are increasingly using online social networking platforms for
promoting products, ideas and information. A popular method of promoting a
product or even an idea is incentivizing individuals to evangelize the idea
vigorously by providing them with referral rewards in the form of discounts,
cash backs, or social recognition. Due to budget constraints on scarce
resources such as money and manpower, it may not be possible to provide
incentives for the entire population, and hence incentives need to be allocated
judiciously to appropriate individuals for ensuring the highest possible
outreach size. We aim to do the same by formulating and solving an optimization
problem using percolation theory. In particular, we compute the set of
individuals that are provided incentives for minimizing the expected cost while
ensuring a given outreach size. We also solve the problem of computing the set
of individuals to be incentivized for maximizing the outreach size for given
cost budget. The optimization problem turns out to be non trivial; it involves
quantities that need to be computed by numerically solving a fixed point
equation. Our primary contribution is, that for a fairly general cost
structure, we show that the optimization problems can be solved by solving a
simple linear program. We believe that our approach of using percolation theory
to formulate an optimization problem is the first of its kind.
