2015
Social network games
Publication
Publication
Journal of Logic and Computation , Volume 25 - Issue 1 p. 207- 242
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]
Additional Metadata | |
---|---|
Oxford U.P. | |
doi.org/10.1093/logcom/ext012 | |
Journal of Logic and Computation | |
Organisation | Directie |
Simon, S., & Apt, K. (2015). Social network games. Journal of Logic and Computation, 25(1), 207–242. doi:10.1093/logcom/ext012 |