How to win Friends and Influence People, Truthfully

Опубликовано 17 августа 2016, 0:55

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.