CS Talk
March 22, 2012
10:30 a.m., AKW 200

Speaker: Yaron Singer
Title: Incentives and Computation: The Limitations and Possibilities of Algorithmic Mechanism Design

Abstract: Algorithmic mechanism design is an emerging field on the borderline of computer science and economics, which addresses the challenge of designing manipulation-resilient algorithms for strategic computational environments such as the internet. I will present several results on the inherent limitations and the promising possibilities of this field.

I will first present an impossibility result which settles the main open question in algorithmic mechanism design: showing the existence of a canonically hard problem for which computational efficiency cannot be reconciled with incentive compatibility. I will then present a general theoretical framework for designing computationally-efficient, incentive-compatible algorithms in budget-constrained domains, which relies on the notion of approximation to circumvent impossibility results from classical microeconomic theory. I will also give experimental evidence for the practical implications of this framework to word-of-mouth advertising in social networks and crowdsourcing markets. I will conclude with several open theoretical and practical challenges for the coming decade.

Bio: Yaron Singer is a postdoctoral researcher at Google. He recently obtained his PhD from UC Berkeley where he was advised by Christos Papadimitriou, and before that he completed his undergraduate studies in Mathematics and Computer Science at Tel Aviv University in 2007. He is the recipient of the 2012 Best Student Paper Award at the ACM conference on Web Search and Data Mining, the 2010 Facebook Fellowship, the 2009 Microsoft Research Fellowship, the 2010 UC Berkeley Venture Lab Award, the 2010 UC Berkeley IT&Web Startup Competition Award, and a 2010 Qualcomm Innovation Finalist Prize.