Seminar by Sunil Easaw Simon
Social Network Games
Sunil Easaw Simon
CWI, Amsterdam
Date: Saturday, January 5th, 2013
Time: 11AM
Venue: CS101.Abstract:
Modern game theory, whose foundations lie in the intersection of mathematics and economics has become an important tool in computer science. Game theoretic techniques turned out to provide a fruitful approach to fundamental issues in several areas including logic, verification and the study of distributed systems.
In this work, we use game theory to better understand the spread of products in a social network. We consider the threshold model of social networks in which the nodes influenced by their neighbours can adopt one out of several alternatives, and associate with each social network a strategic game between the agents. Like certain classes of potential games, these games exhibit the "join the crowd" property where the payoff of each player weakly increases if more players choose the same strategy. However, these games need not always have a Nash equilibrium and determining the existence of a Nash equilibrium is NP-complete. We look at some natural subclasses in which an equilibrium profile can be efficiently computed. We also study the notion of improvement paths and restrictions under which improvement paths are guaranteed to terminate.
This is joint work with Krzysztof Apt.