Influence maximization for complementary goods: Why parties fail to cooperate?
Journal
International Conference on Information and Knowledge Management, Proceedings
Journal Volume
24-28-October-2016
Pages
1713-1722
Date Issued
2016
Author(s)
Abstract
We consider the problem where companies provide different types of products and want to promote their products through viral marketing simultaneously. Most previous works assume products are purely competitive. Different from them, our work considers that each product has a pairwise relationship which can be from strongly competitive to strongly complementary to each other's product. The problem is to maximize the spread size with the presence of different opponents with different relationships on the network. We propose Interacting Influence Maximization (IIM) game to model such problems by extending the model of the Competitive Influence Maximization (CIM) game studied by previous works, which considers purely competitive relationship. As for the theoretical approach, we prove that the Nash equilibrium of highly complementary products of different companies may still be very inefficient due to the selfishness of companies. We do so by introducing a well-known concept in game theory, called Price of Stability (PoS) of the extensive-form game. We prove that in any k selfish players symmetric complementary IIM game, the overall spread of the products can be reduced to as less as 1/k of the optimal spread. Since companies may fail to cooperate with one another, we propose different competitive objective functions that companies may consider and deal with separately. We propose a scalable strategy for maximizing influence differences, called TOPBOSS that is guaranteed to beat the first player in a single-round two-player second-move game. In the experiment, we first propose a learning method to learn the ILT model, which we propose for IIM game, from both synthetic and real data to validate the effectiveness of ILT. We then exhibit that the performance of several heuristic strategies in the traditional influence maximization problem can be improved by acquiring the knowledge of the existence of competitive/complementary products in the network. Finally, we compare the TOPBOSS with different heuristic algorithms in real data and demonstrate the merits of TOPBOSS.
Type
conference paper