  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 the
budget distribution among the individuals at a finite number of campaign times
to maximize their overall payoff given as a function of individuals' opinions.
We show that i) the optimal investment strategy for the case of 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 the earlier work on the static version of the problem to a
dynamic multistage game.
