Toward Complexity Measures for Systems Involving Human Computation


  • R. Jordan Crouser Tufts University
  • Benjamin Hescott Tufts University
  • Remco Chang Tufts University



Human Computation, Complexity Theory


This paper introduces the Human Oracle Model as a method for characterizing and quantifying the use of human processing power as part of an algorithmic process. The utility of this model is demonstrated through a comparative algorithmic analysis of several well-known human computation systems, as well as the definition of a preliminary characterization of the space of human computation under this model. Through this research, we hope to gain insight about the challenges unique to human computation and direct the search for efficient human computation algorithms.


Bertini, E and Lalanne, D. (2010). Investigating and reflecting on the integration of automatic data analysis and visualization in knowledge discovery. SIGKDD Explorations Newsletter 11, 2 (2010), 9–18.

Cooper, S, Khatib, F, Treuille, A, Barbero, J, Lee, J, Beenen, M, Leaver-Fay, A, Baker, D, Popovic, Z, and others, . (2010). Predicting protein structures with a multiplayer online game. Nature 466, 7307 (2010), 756–760.

Crouser, R and Chang, R. (2012). An Affordance-Based Framework for Human Computation and Human-Computer Collaboration. Visualization and Computer Graphics, IEEE Trans. on 18, 12 (2012), 2859–2868.

Donmez, P and Carbonell, J. (2008). Proactive learning: cost-sensitive active learning with multiple imperfect oracles. In Proc. 17th ACM Conf. on Information and knowledge management. ACM, 619–628.

Girouard, A, Solovey, E, Hirshfield, L, Chauncey, K, Sassaroli, A, Fantini, S, and Jacob, R. (2009). Distinguishing difficulty levels with non-invasive brain activity measurements. In Human-Computer Interaction. Springer, 440–452.

Ho, C, Chang, T, Lee, J, Hsu, J, and Chen, K. (2009). KissKissBan: a competitive human computation game for image annotation. In Proc. SIGKDD Workshop on Human Computation. ACM, 11–14.

Law, E and von Ahn, L. (2009). Input-agreement: a new mechanism for collecting data using human computation games. In Proc. 27th SIGCHI Conf. on Human factors in computing systems. 1197–1206.

Law, E, von Ahn, L, Dannenberg, R, and Crawford, M. (2007). Tagatune: A game for music and sound annotation. Proc. of ISMIR (Vienna, Austria) (2007).

Mason, W and Watts, D. (2010). Financial incentives and the performance of crowds. ACM SigKDD Explorations Newsletter 11, 2 (2010), 100–108.

Quinn, A and Bederson, B. (2011). Human computation: a survey and taxonomy of a growing field. In Proc. 29th SIGCHI Conf. on Human factors in computing systems. ACM, 1403–1412.

Shahaf, D and Amir, E. (2007). Towards a theory of AI completeness.. In Logical Formalizations of Commonsense Reasoning. 150– 155.

Singer, Y and Mittal, M. (2011). Pricing Tasks in Online Labor Markets.. In Proc. Workshop on Human Computation at the 25th AAAI Conf. on AI.

Turing, A. (1938). Systems of logic based on ordinals: a dissertation. Ph.D. Dissertation. Cambridge.

von Ahn, L. (2006). Games with a purpose. Computer 39, 6 (2006), 92–94.

von Ahn, L and Dabbish, L. (2004). Labeling images with a computer game. In Proc. 22nd SIGCHI Conf. on Human factors in computing systems. ACM, 319–326.

von Ahn, L, Liu, R, and Blum, M. (2006). Peekaboom: a game for locating objects in images. In Proc. 24th SIGCHI Conf. on Human factors in computing systems. ACM, 55–64.

von Ahn, L, Maurer, B, McMillen, C, Abraham, D, and Blum, M. (2008). reCAPTCHA: human-based character recognition via web security measures. Science 321, 5895 (2008), 1465–1468.

Wallace, B, Small, K, Brodley, C, and Trikalinos, T. (2011). Who Should Label What? Instance Allocation in Multiple Expert Active Learning. In SDM. 176–187.




How to Cite

Crouser, R. J., Hescott, B., & Chang, R. (2014). Toward Complexity Measures for Systems Involving Human Computation. Human Computation, 1(1).