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 networks solve?

In this talk, Kearns described the preliminary but thought-provoking findings of a series of behavioral experiments he has performed at Penn. Human subjects attempt to perform distributed graph coloring using a system that controls network structure, information conditions, incentives, and a variety of other variables of interest. The experiments shed early light on whether such problems can be solved by human networks, under what conditions, and on what algorithms they seem to adopt.

Joint work with Siddharth Suri and Nick Montfort.