SAFE GAME OF COMPETITIVE DIFFUSION

Abstract

Competitive Diffusion is a recently introduced game-theoretic model for the spread of information through social networks. The model is a game on a graph with external players trying to reach the most vertices. In this thesis, we consider the safe game of Competitive Diffusion. This is the game where one player tries to optimize his gain as before, while his opponents' objectives are to minimize the first player's gain. This leads to a safety value for the player, i.e. an optimal minimal expected gain no matter the strategies of the opponents.

We discuss safe strategies and present some bounds on the safety value in the two-player version of the game on various graphs. The results are almost entirely on the safe game on trees, including the special cases of paths, spiders and complete trees but also consist of some preliminary studies of the safe game on three other simple graphs. Our main result consists of a Centroidal Safe Strategy (CSS) Algorithm which suggests a safe strategy for a player on any centroidal tree, a tree which has one vertex as centroid, and gives its associated guaranteed gain.