The pioneering work of Travers and Milgram in 1969 established the now-familiar folklore of "six degrees" of separation in natural social networks. More recently, researchers including Jon Kleinberg and Duncan Watts have explored the algorithmic aspects of how messages are forwarded in such networks. Perhaps the computer science view of this fascinating line of thought can be best summarized as follows: Using relatively local information, distributed human organizations can compute good approximations to the all-pairs shortest paths problem. What other sorts of distributed optimization problems can humans solve?

In this talk, I will first overview our more mathematical research at the intersection of computer science, economics and social networks that led us to be interested in the empirical question above. I will then describe the preliminary findings of a behavioral study we held recently at Penn. Human subjects attempted to perform distributed graph coloring using a system that controlled network structure, information conditions, and a variety of other variables of interest. The experiments shed early light on whether such problems can be solved by humans, under what conditions, and what algorithms they seem to adopt.

The behavioral experiments are joint work with Nick Montfort, Huanlei Ni, and Siddharth Suri.

BIO

Michael Kearns is a professor of Computer and Information Science at the University of Pennsylvania, where he holds the National Center Chair in Resource Management and Technology, and is co-director of Penn's Institute for Research in Cognitive Science. He has published extensively in the theory of machine learning, probabilistic artificial intelligence, and related disciplines. His most recent interests lie at the intersections of computer science with economics, game theory, and finance.