  We study a natural model of coordinated social ad campaigns over a social
network, based on models of Datta et al. and Aslay et al. Multiple advertisers
are willing to pay the host - up to a known budget - per user exposure, whether
the exposure is sponsored or orgain (i.e. shared by a friend). Campaigns are
seeded with sponsored ads to some users, but no user must be exposed to too
many sponsored ads. Thus, while ad campaigns proceed independently over the
network, they need to be carefully coordinated with respect to their seed sets.
  We study the objective of maximizing host's total ad revenue. Our main result
is to show that under a broad class of influence models, the problem can be
reduced to maximizing a submodular function subject to two matroid constraints;
it can therefore be approximated within a factor essentially 1/2 in polynomial
time. When there is no bound on the individual seed set sizes of advertisers,
the constraints correspond only to a single matroid, and the guarantee can be
improved to 1-1/e; in that case, a factor 1/2 is achieved by a practical greedy
algorithm. The 1-1/e approximation algorithm for matroid-constrained problem is
far from practical; however, we show that specifically under the Independent
Cascade model, LP rounding and Reverse Reachability techniques can be combined
to obtain a 1-1/e approximation algorithm.
  Our theoretical results are complemented by experiments evaluating the extent
to which the coordination of multiple ad campaigns inhibits the revenue
obtained from each individual campaign, as a function of the similarity of the
influence networks and strength of ties in the networks. Our experiments
suggest that as networks for different advertisers become less similar, the
harmful effect of competition decreases. With respect to tie strengths, we show
that the most harm is done in an intermediate range.
