done to investigate the possibility that the formation subjects built good networks for the task, but either ran out of time to reach unanimity, or included subjects who behaved very stubbornly because they had significant edge expenditures and thus strongly held out for their preferred color.

Performance on the control experiments was even worse. The surprising conclusion seems to be that despite the fact that subjects clearly understood the task, and were now given the opportunity to solve it not on an arbitrary network, but one collectively designed by the population in service of the task, they were unable to do so. One candidate for a structural property of the subject-built networks that might account for their difficulty in the biased voting task is ( betweenness) centrality, a standard measure of a vertex’s importancee in a network. Compared to the networks used in the original, exogenous-network biased voting experiments, the distribution (across vertices) of centrality in the subject-built networks is considerably more skewed. 16 This means that in the network formation experiments, there was effectively more reliance on a small number of high-centrality vertices or players, making performance less robust to stubbornness or other non-coordinating behaviors by these players. Indeed, there was moderately positive and highly significant correlation between centrality and earnings, indicating that players with high centrality tended to use their position for financial gain rather than global coordination and information aggregation.

Despite their demonstrated ability to solve a diverse range of computational problems on a diverse set of networks, human subjects seem poor at building networks, at least within the limited confines of our experiments so far. Further investigation of this phenomenon is clearly warranted.

 

Concluding Remarks
Despite their diversity, our experi-
ments have established a number of
rather consistent facts. At least in mod-
e The betweenness centrality of vertex v is aver-
age, over all pairs of other vertices u and w, of
the fraction of shortest paths between u and w
in which v appears.

erate population sizes, human subjects can perform a computationally wide range of tasks from only local interaction. Network structure has strong but task-dependent effects. Notions of social fairness and inequality play important roles, despite the anonymity of our networked setting. Behavioral traits of individual subjects are revealed despite the highly simplified and stylized interactions; with language removed, subjects persistently try to invent signaling mechanisms.

There are a number of recent efforts related to the research described here. Some compelling new coloring experiments7, 20 have investigated the conditions under which increased connectivity improves performance. Our experimental approach has thus far aimed for breadth, but studies such as these are necessary to gain depth of understanding. We have also usually done only the most basic statistical analyses of our data, but others have begun to attempt more sophisticated models. 6

Perhaps the greatest next frontier is to conduct similar experiments on the Web, where a necessary loss of control over subjects and the experimental environment may be compensated by orders of magnitude greater scale, both in population size and the number of experimental conditions investigated. Recent efforts using both the open web and Amazon’s Mechanical Turk online labor market have started down this important path. 2, 19, 23

Acknowledgments

Many thanks to the stellar colleagues who have been my coauthors on the various papers summarized here: Tan-moy Chakraborty, Stephen Judd, Nick Montfort, Sid Suri, Jinsong Tan, Jennifer Wortman Vaughan, and Eugene Vorobeychik. I give especially warm acknowledgments to Stephen Judd, who has been my primary collaborator throughout the project. Thanks also to Colin Camerer and Duncan Watts, who both encouraged me to start and continue this line of work, and who made a number of important conceptual and methodological suggestions along the way.

 

References

1. Camerer, C. Behavioral Game Theory. Princeton university Press, Princeton, nJ, 2003.

2. Centola, d. the spread of behavior in an online social
network experiment. Science 329, 5996 (2010),
1194–1197.

 

Michael Kearns ( [e-mail]) is a professor in the Computer and Information science department of the university of Pennsylvania. his research interests include machine learning, social networks, algorithmic game theory, and computational finance.