Human Computation and Multiagent Systems:An Algorithmic PerspectiveAndrew MaoHarvard [email protected] C. ParkesHarvard [email protected] D. ProcacciaHarvard [email protected] ZhangHarvard [email protected]“Best. HIT. Ever.”Anonymous Amazon Mechanical Turk workerreflecting on our human intelligence taskAbstractHuman computation systems such as online task markets pro-vide platforms that allow us to harness the abilities of manyhuman problem solvers to accomplish a variety of tasks. Weargue that such platforms share some of the features of mul-tiagent systems, and ask whether algorithms originally de-signed for multiagent systems can be leveraged for coordi-nating the problem solving process among human computers.We study this question in the context of the graph coloringproblem where each human controls the color of one vertex,and compare the performance of humans using adaptations oftwo well-known distributed constraint satisfaction algorithmsto the performance of humans that were asked to simply colorthe graph. We find that people provided with algorithmic in-structions achieve significantly better performance than peo-ple who are left to their own devices.1. IntroductionHuman computation is a recently popular computationalparadigm that outsources problem solving steps that are dif-ficult for computers to many human computers connectedby the Internet. Over the last few years, there have beentwo prominent streams to advance human computation. Thefirst stream focuses on online applications that are often de-scribed as games with a purpose (von Ahn and Dabbish2008), which are craftily designed so that people can con-tribute useful computations as a by-product of playing anenjoyable game. A well-known example is the ESP game,in which two players who cannot communicate see the sameimage and must agree on a suitable label, hence leadingplayers to identify relevant labels. Another well-known ex-ample is Foldit (Cooper et al. 2010), where players collabo-rate in folding proteins into their stable shape.The second stream is represented by online labor mar-kets, where the paradigmatic example is Amazon Mechani-cal Turk (AMT).1AMT has two types of participants: re-Copyright © 2011, Association for the Advancement of ArtificialIntelligence (www.aaai.org). All rights reserved.1http://www.mturk.comquesters and workers. The requesters post human intelli-gence tasks (HIT), that specify a task to be carried out, re-quirements for workers, and a payment for successful com-pletion. The workers can view the available HITs and se-lect the ones that best fit their objectives (usually makingmoney, having fun, or both). Typical HITs are quite tedious,and often involve data entry or generating training data forvarious algorithms; common examples include labeling im-ages, transcribing audio, and finding information on web-sites. Both the name and the amusing slogan of AMT, “ar-tificial artificial intelligence,” allude to the fact that humansare solving problems that still challenge the best AI systemstoday.In general, online labor markets differ from games with apurpose in that they are significantly more generic and versa-tile. In fact, one can view platforms like AMT as a new typeof multiagent system, where software agents are replacedby human computers.2Much like classic non-cooperativemultiagent systems, these platforms are distributed and theagents (in an ironic reversal of roles) are autonomous, het-erogeneous, and self-interested (at least to some extent). Todate, most tasks on AMT are simple and request indepen-dent effort, and few tasks aim to coordinate problem solvingamong many actors within the system.In this paper, we look at human computation through analgorithmic lens, and seek to leverage the connection be-tween human computation and multiagent systems. Ourmain research question is:Can successful algorithmic ideas from multiagent sys-tems be adapted to effectively coordinate human com-puters to contribute jointly to a problem solving effort?There are obvious difficulties and challenges. First, a hu-man agent may not understand a complicated algorithm, andadditionally needs sufficient context to effectively performits role in the computations. In addition, information mustbe conveyed, through good user interface design, in a waythat is intuitive for humans to understand and process. Fi-nally, humans make errors, and unless a computer algorithmis somewhat robust to such errors, the performance of hu-mans attempting to execute an algorithm can be poor. How-ever, humans also have the ability to use instincts and make2We might also expect hybrid systems that aim to harness therespective abilities of both software agents and human computers.decisions in ways that a straightforward algorithm cannot,and a well-designed system should allow for this potential.Overview of methodology and results. We focus on thedistributed graph coloring problem, where agents must colorthe vertices of a graph such that no two adjacent verticesshare the same color. Our focus on graph coloring is notbecause we expect human computation approaches to pro-vide faster solutions than a computer. Rather, we view graphcoloring as a paradigmatic computational problem, and onefrom which we hope insights will carry over to other prob-lems. An advantage of the graph coloring problem is thatnon-algorithmic, human computation has been previouslystudied (Kearns, Suri, and Montfort 2006).For our study, we conducted a series of 90 experimentson AMT. In each experiment, fifteen people are instructedto color a fifteen node graph. Each person can view the en-tire graph but controls only one vertex, and can change itscolor at any time. To our knowledge, this is the first time ex-periments with real-time user interaction were carried out inan online labor market. Our methodology is detailed in Sec-tion 3, and may be of independent interest to the reader.We test two adaptations of well-known distributed con-straint satisfaction algorithms (Yokoo and Hirayama 2000):distributed breakout and weak commitment search. In eachcase, we provide normative but not fully prescriptive adviceabout how to participate in the task, in the spirit of the under-lying algorithm. This approach centers on conveying algo-rithmic ideas in an intuitive way, while also allowing peopleroom to differ from the precise mechanistic approach.Our results show that instructions based on both algo-rithms yield a