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 (Apt and Markakis (2011, Lecture Notes in Computer Science, pp. 212-223)) introduced a threshold model, in which the no...

Full description

Saved in:
Bibliographic Details
Published in:Journal of logic and computation 2015-02, Vol.25 (1), p.207-242
Main Authors: Simon, S., Apt, K. R.
Format: Article
Language:English
Subjects:
Complexity
Games
Graphs
Mathematical analysis
Mathematical models
Players
Social networks
Strategy
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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 (Apt and Markakis (2011, Lecture Notes in Computer Science, pp. 212-223)) introduced a threshold model, in which the nodes influenced by their neighbours can adopt one out of several alternatives. To analyse 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 directed acyclic graph, 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 complexity of the finite best response property and the finite improvement property (FIP). Further, we introduce a new property of the uniform FIP which is satisfied when the underlying graph is a simple cycle, 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.
ISSN:0955-792X
1465-363X
DOI:10.1093/logcom/ext012