CUNY Seminar in Logic and Games
Thursday, September 20, 2012, room 4421
1 PM to 2:30 PM
Choosing Products in Social Networks
Krzysztof R. Apt
CWI and University of Amsterdam
Abstract: Social networks have become a huge interdisciplinary research area with important links to sociology, economics, epidemiology, computer science, and mathematics. We introduce a new threshold model of social networks, in which the nodes influenced by their neighbours can adopt one out of several alternatives (products). We study various algorithmic questions concerning these networks, for example the problem of computing the minimum (resp. maximum) possible spread of a product. Also, using game-theoretic concepts, we analyze the consequences of adopting products by the agents who form the network. In particular, we prove that determining an existence of a (pure) Nash equilibrium is NP-complete. We explain how these results can be used to analyze consequences of the addition of new products to a social network. We show that in some cases such an addition can permanently destroy market stability.
Based on joint works with Vangelis Markakis and Sunil Simon.
Formal Philosophy 