How to win Friends and Influence People, Truthfully

February 25, 2011
Yaron Singer | UC Berkeley

Throughout the past decade there has been extensive research on algorithmic and data mining techniques for solving the problem of influence maximization in social networks: if one can convince a subset of individuals to influence their friends to adopt a new product or technology, which subset should be selected so that the spread of influence in the social network is maximized?

Despite the progress in modeling and techniques, the incomplete information aspect of problem has been largely overlooked. While the network structure is often available, the inherent cost individuals have for influencing friends is difficult to extract.

In this talk we will discuss mechanisms that extract individuals’ costs in well studied models of social network influence. We follow the mechanism design framework which advocates for truthful mechanisms that use allocation and payment schemes that incentivize individuals to report their true information. Beyond their provable theoretical guarantees, the mechanisms work well in practice. To show this we will use results from experiments performed on the mechanical turk platform and social network data that provide experimental evidence of the mechanisms’ effectiveness.

Speaker Details

Yaron Singer is a PhD candidate in the Computer Science Division at UC Berkeley, advised by Christos Papadimitirou. His main research interests are in algorithmic game theory, social networks and electronic commerce. Yaron received the Microsoft Research fellowship in 2009 and the Facebook fellowship in 2010.