互補品之影響力最大化:為什麼雙方會合作失敗?

Abstract

我們考慮提供不同種類商品的不同公司想要通過病毒式營銷來推廣自己產品的問題，之前的研究大多假定產品間的關係是完全競爭的，和它們不同，我們考慮產品與產品間的兩兩關係可以由強烈的替代品到強烈的互補品連續變化。這個問題的目的是要在存在與自己產品不同關係之對手產品的網路上最大化自己產品的影響力，我們提出互動式影響力最大化賽局來模型化這個問題，這個賽局是藉由擴展之前研究的競爭式影響力最大化賽局而來的，而這些研究都僅考慮完全競爭的產品關係。理論部分，我們證明了即使不同公司間的產品為高度的互補品。它們在賽局上的納許均衡仍舊有可能因為他們的自私而非常不效率。我們藉由引入一個廣為人知的賽局概念，也就是在展開形式賽局上的Price of Stability (PoS)來證明這件事。我們證明在k名自私的玩家對稱互補的互動式影響力最大化賽局下，整體的影響力有可能下降到最佳情況的1/k，而既然公司間會因為自私而合作失敗，我們提出此問題的不同目標函數並且分開處理。我們提出一個叫做TOPBSS的可擴展策略來最大化與對手間的影響力差異，這個策略能夠保證在兩名玩家單輪後動的賽局中獲勝。而實驗中，我們提出了我們互動式影響力最大化賽局中ILT模型的學習方法，接著我們藉由合成與真實資料來驗證該方法的有效性。接著，我們展示多個傳統上影響力最大化問題的啟發式策略能夠藉由獲知其他互補或替代品存在的知識；在互動式影響力最大化賽局上提升表現。最後，我們將TOPBOSS與其他啟發式演算法進行比較來展示 TOPBOSS的優點。

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 prod-ucts are purely competitive. Different from them, our work considers that each product has a pair-wise 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 theo-retical 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 cooper-ate with one another, we propose different competitive objective functions that companies may con-sider 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 sec-ond-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 competi-tive/complementary products in the network. Finally, we compare the TOPBOSS with different heuristic algorithms in real data and demonstrate the merits of TOPBOSS.