Kearns NAS 2006

This a Paper discussed in Social Media Analysis 10-802 in Spring 2011.

Citation

Kearns, M., S. Suri, and N. Montfort. 2006. An experimental study of the coloring problem on human subject networks. Science 313, no. 5788: 824.

Online version

An experimental study of the coloring problem on human subject networks

Summary

This paper is addresses the notion of social problem-solving and applies this to the famous graph coloring problem. Given a graph, each vertex is controlled by a human where the collective goal for every player is to select a color for their vertex that differs from that of their neighbors. The graphs size in their experiments consists of 38 vertices and the number of colors available to the humans equals the chromatic number of the graph.

Graph coloring has many practical applications, including the scheduling of departmental events (e.g. classes). Each event can be seen as a vertex in a network, which are connected when there is temporally overlap. Two overlapping events must be scheduled in different rooms, hence they need to have different colors, which gives us the graph coloring problem. Humans attempt to solve this problem by first-come first-serve sign-up sheets for the rooms and possibly negotiate with others to switch rooms.

During the majority of the experiments each subject could only observe part of the network, namely their own vertex and that of their neighbors. Furthermore there was no communication beyond the network information they could see. 31 out of 38 experiments resulted in an optimal coloring in less than 5 minutes with a mean completion time of 82 seconds and median of only 44 seconds. The network structure played an important role, it turned out that cycle-based networks were easier to solve than those generated by preferential attachment.

An interesting observation is that the human behavior is difficult from that of a heuristic that attempts to act similar, i.e. randomly pick initial colors and solve conflicts. It is also worth mentioning that being able to observe more than the local information did not help at all for more complicated graph structures.

Remarks

The experiments were only conducted on relatively small graphs and it would be interesting to see how well this scales. Furthermore the results do not seem to be very promising for any practical applications, because the social problem-solving did not really work out for more complicated graph structures.