Social Network Games with Obligatory Product Selection

Krzysztof R. Apt
Sunil Simon

Recently, Apt and Markakis introduced a model for product adoption in social networks with multiple products, where the agents, influenced by their neighbours, can adopt one out of several alternatives (products). To analyze these networks we introduce social network games in which product adoption is obligatory.

We show that when the underlying graph is a simple cycle, there is a polynomial time algorithm allowing us to determine whether the game has a Nash equilibrium. In contrast, in the arbitrary case this problem is NP-complete. We also show that the problem of determining whether the game is weakly acyclic is co-NP hard.

Using these games we analyze various types of paradoxes that can arise in the considered networks. One of them corresponds to the well-known Braess paradox in congestion games. In particular, we show that social networks exist with the property that by adding an additional product to a specific node, the choices of the nodes will unavoidably evolve in such a way that everybody is strictly worse off.

In Gabriele Puppis and Tiziano Villa: Proceedings Fourth International Symposium on Games, Automata, Logics and Formal Verification (GandALF 2013), Borca di Cadore, Dolomites, Italy, 29-31th August 2013, Electronic Proceedings in Theoretical Computer Science 119, pp. 180–193.
Published: 16th July 2013.

ArXived at: https://dx.doi.org/10.4204/EPTCS.119.16 bibtex PDF
References in reconstructed bibtex, XML and HTML format (approximated).
Comments and questions to: eptcs@eptcs.org
For website issues: webmaster@eptcs.org