We have been conducting behavioral experiments in which human subjects attempt to solve challenging graph-theoretic optimization problems through only local interactions and incentives. The primary goal is to shed light on the relationships between network structure and the behavioral and computational difficulty of different problem types.
To date, we have conducted experiments in which subjects are incentivized to solve problems of graph coloring, consensus, independent set, networked trade, biased voting, and networked bargaining. I will report on thought-provoking findings at both the collective and individual behavioral levels, and contrast them with theories from theoretical computer science, sociology, and economics.
Michael Kearns is a professor in the Computer and Information Science department at the University of Pennsylvania. He has published widely in machine learning, algorithmic game theory, and a variety of other topics. More information can be found at www.cis.upenn.edu/~mkearns.