Social network games

One of the natural objectives of the field of the social networks is to predict agents’ behaviour. To better understand the spread of various products through a social network [2] introduced a threshold model, in which the nodes influenced by their neighbours can adopt one out of sev- eral alternatives. To analyze the consequences of such product adoption we associate here with each such social network a natural strategic game between the agents. In these games the payoff of each player weakly increases when more players choose his strategy, which is exactly opposite to the congestion games. The possibility of not choosing any product results in two special types of (pure) Nash equilibria. We show that such games may have no Nash equilibrium and that determining an existence of a Nash equilibrium, also of a special type, is NP-complete. This implies the same result for a more general class of games, namely polymatrix games. The situation changes when the underlying graph of the social network is a DAG, a simple cycle, or, more generally, has no source nodes. For these three classes we determine the complexity of an existence of (a special type of) Nash equilibria. We also clarify for these categories of games the status and the com- plexity of the finite best response property (FBRP) and the finite im- provement property (FIP). Further, we introduce a new property of the uniform FIP which is satisfied when the underlying graph is a simple cy- cle, but determining it is co-NP-hard in the general case and also when the underlying graph has no source nodes. The latter complexity results also hold for the property of being a weakly acyclic game. A preliminary version of this paper appeared as [19]