What do the theory of computation, economics and related fields have to say about the emerging phenomena of crowdsourcing and social computing? Most successful applications of crowdsourcing to date have been on problems we might consider "embarrassingly parallelizable" from a computational perspective. But the power of the social computation approach is already evident, and the road cleared for applying it to more challenging problems.
In part towards this goal, for a number of years we have been conducting controlled human-subject experiments in distributed social computation in networks with only limited and local communication. These experiments cast a number of traditional computational problems --- including graph coloring, consensus, independent set, market equilibria, biased voting and network formation --- as games of strategic interaction in which subjects have financial incentives to collectively "compute" global solutions. I will overview and summarize the many behavioral findings from this line of experimentation, and draw broad comparisons to some of the predictions made by the theory of computation and microeconomics.
Michael Kearns is a professor of Computer and Information Science at the University of Pennsylvania, where he is the director of the new Penn program in Market and Social Systems Engineering (www.mkse.upenn.edu). His research interests include topics in machine learning, algorithmic game theory, social networks, computational finance and artificial intelligence. More information is available at www.cis.upenn.edu/~mkearns.