Abstract We study the two-player safe game of Competitive Diffusion, a game-theoretic model for the diffusion of technologies or influence through a social network. In game theory, safe strategies are mixed strategies with a minimum expected gain against unknown strategies of the opponents. Safe strategies for competitive diffusion lead to maximum spread of influence in the presence of uncertainty about the other players. We study the safe game on two specific classes of trees, spiders and complete trees, and give tight bounds on the minimum expected gain. We then use these results to give an algorithm that suggests a safe strategy for a player on any tree. We test this algorithm on randomly generated trees and show that it finds strategies that are close to optimal.
We introduce a game-theoretic model of diffusion of technologies, advertisements, or influence through a social network. The novelty in our model is that the players are interested parties outside the network. We study the relation between the diameter of the network and the existence of pure Nash equilibria in the game. In particular, we show that if the diameter is at most two then an equilibrium exists and can be found in polynomial time, whereas if the diameter is greater than two then an equilibrium is not guaranteed to exist. We consider the game theoretic model of competitive information diffusion recently introduced in (2010) [1]. We show that for the case of 2 competing agents, there exists a Nash Equilibrium for this game on any tree. We also present an example to show that this is not necessarily true for 3 or more agents. We study a game based on a model for the spread of influence through social networks. In game theory, a Nash-equilibrium is a strategy profile in which each player’s strategy is optimized with respect to her opponents’ strategies. Here we focus on a specific two player case of the game. We show that there always exists a Nash-equilibrium for paths, cycles, trees, and Cartesian grids. We use the centroid of trees to find a Nash-equilibrium for a tree with a novel approach, which is simpler compared to previous works. We also explore the existence of Nash-equilibriums for uni-cyclic graphs, and offer some open problems.  We study a recently introduced deterministic model of competitive information diffusion on the Iterated Local Transitivity (ILT) model of Online Social Networks (OSNs). In particular, we show that, for 2 competing agents, an independent Nash Equilibrium (N.E.) on the initial graph remains a N.E. for all subsequent times. We also describe an example showing that this conclusion does not hold for general N.E. in the ILT process. In [N. Alon, M. Feldman, A.D. Procaccia, M. Tennenholtz, A note on competitive diffusion through social networks, Inform. Process. Lett. 110 (2010) 221-225], the authors introduced a game-theoretic model of diffusion process through a network. They showed a relation between the diameter of a given network and existence of pure Nash equilibria in the game. Theorem 1 of their paper says that a pure Nash equilibrium exists if the diameter is at most two. However, we have an example which does not admit a pure Nash equilibrium even if the diameter is two. Hence we correct the statement of Theorem 1 of their paper.