Technical Program

Paper Detail

Paper Title Adversarial Influence Maximization
Paper IdentifierTU2.R7.1
Authors Justin Khim, University of Pennsylvania, United States; Varun Jog, Po-Ling Loh, University of Wisconsin - Madison, United States
Session Game Theory
Location Bièvre, Level 5
Session Time Tuesday, 09 July, 11:40 - 13:00
Presentation Time Tuesday, 09 July, 11:40 - 12:00
Manuscript  Click here to download the manuscript
Abstract We consider the problem of influence maximization in fixed networks for contagion models in an adversarial setting. The goal is to select an optimal set of nodes to seed the influence process, such that the number of influenced nodes at the conclusion of the campaign is as large as possible. We formulate the problem as a repeated game between a player and adversary, where the adversary specifies the edges along which the contagion may spread, and the player chooses sets of nodes to influence in an online fashion. We establish upper and lower bounds on the minimax pseudo-regret in both undirected and directed networks.