Yaron Singer (CS, UC Berkeley)
Thursday, 5.5.2011, 14:30
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.