Dynamic Influence Maximization Under Increasing Returns to Scale

摘要

Influence maximization is a problem of maximizing the aggregate adoption of products, technologies, or even beliefs. Most past algorithms leveraged an assumption of submodularity that captures diminishing returns to scale. While submodularity is natural in many domains, early stages of innovation adoption are often better characterized by convexity, which is evident for renewable technologies, such as rooftop solar. We formulate a dynamic influence maximization problem under increasing returns to scale over a finite time horizon, in which the decision maker faces a budget constraint. We propose a simple algorithm in this model which chooses the best time period to use up the entire budget (called Best-Stage), and prove that this policy is optimal in a very general setting. We also propose a heuristic algorithm for this problem of which Best-Stage decision is a special case. Additionally, we experimentally verify that the proposed "best-time" algorithm remains quite effective even as we relax the assumptions under which optimality can be proved. However, we find that when we add a "learning-by-doing" effect, in which the adoption costs decrease not as a function of time, but as a function of aggregate adoption, the "best-time" policy becomes suboptimal, and is significantly outperformed by our more general heuristic.