LAUSR

We consider the problem of budget allocation for competitive influence maximization over social networks. In this problem, multiple competing parties (players) want to distribute their limited advertising resources over a set of social individuals to maximize their long-run cumulative payoffs. It is assumed that the individuals are connected via a social network and update their opinions based on the classical DeGroot model. The players must decide on the budget distribution among the individuals at a finite number of campaign times to maximize their overall payoff as a function of individuals’ opinions. Under some assumptions, we show that i) the optimal investment strategy for a single player can be found in polynomial time by solving a concave program, and ii) the open-loop equilibrium strategies for the multiplayer dynamic game can be computed efficiently by following natural regret-minimization dynamics. Our results extend earlier work on the static version of the problem to a dynamic multistage game.