Behavioral Graph Coloring

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, I will describe the preliminary but thought-provoking findings of a series of behavioral experiments we have been performing 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 Nick Montfort and Siddharth Suri.