  Computational advertising has been studied to design efficient marketing
strategies that maximize the number of acquired customers. In an increased
competitive market, however, a market leader (a leader) requires the
acquisition of new customers as well as the retention of her loyal customers
because there often exists a competitor (a follower) who tries to attract
customers away from the market leader. In this paper, we formalize a new model
called the Stackelberg budget allocation game with a bipartite influence model
by extending a budget allocation problem over a bipartite graph to a
Stackelberg game. To find a strong Stackelberg equilibrium, a standard solution
concept of the Stackelberg game, we propose two algorithms: an approximation
algorithm with provable guarantees and an efficient heuristic algorithm. In
addition, for a special case where customers are disjoint, we propose an exact
algorithm based on linear programming. Our experiments using real-world
datasets demonstrate that our algorithms outperform a baseline algorithm even
when the follower is a powerful competitor.
