Security Games on Social Networks


Thanh H. Nguyen, Jason Tsai, Albert Jiang, Emma Bowring, Rajiv Maheswaran, and Milind Tambe. 2012. “Security Games on Social Networks .” In AAAI Fall Symposium, 2012 .


Many real-world problems exhibit competitive situations in which a defender (a defending agent, agency, or organization) has to address misinformation spread by its adversary, e.g., health organizations cope with vaccination-related misinformation provided by anti-vaccination groups. The rise of social networks has allowed misinformation to be easily and quickly diffused to a large community. Taking into account knowledge of its adversary’s actions, the defender has to seek efficient strategies to limit the influence of the spread of misinformation by the opponent. In this paper, we address this problem as a blocking influence maximization problem using a game-theoretic approach. Two players strategically select a number of seed nodes in the social network that could initiate their own influence propagation. While the adversary attempts to maximize its negative influence, the defender tries to minimize this influence. We represent the problem as a zero-sum game and apply the Double Oracle algorithm to solve the game in combination with various heuristics for oracle phases. Our experimental results reveal that by using the game theoretic approach, we are able to significantly reduce the negative influence in comparison to when the defender does not do anything. In addition, we propose using an approximation of the payoff matrix, making the algorithms scalable to large real-world networks.
See also: 2012