Computer Science – Social and Information Networks
Scientific paper
2012-02-10
Computer Science
Social and Information Networks
22 pages
Scientific paper
We study the consequences of adopting products by agents who form a social network. To this end we use the threshold model introduced in Apt and Markakis, arXiv:1105.2434, in which the nodes influenced by their neighbours can adopt one out of several alternatives, and associate with such each social network a strategic game between the agents. 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. The situation changes when the underlying graph of the social network is a DAG, a simple cycle, or has no source nodes. For these three classes we determine the complexity of an existence of (a special type of) Nash equilibria and clarify the status of the finite improvement property (FIP). We also introduce the property of the uniform FIP which is satifisfied when the underlying graph is a simple cycle. Finally, we explain how these results can be used to analyze consequences of the addition of new products to a social network. In particular we show that in some cases such an addition can permanently destroy market stability.
Apt Krzysztof R.
Simon Sunil
No associations
LandOfFree
Choosing Products in Social Networks does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Choosing Products in Social Networks, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Choosing Products in Social Networks will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-275362