Parallel Task Routing for Crowdsourcing

Authors

  • Jonathan Bragg University of Washington
  • Andrey Kolobov Microsoft Research
  • Mausam Mausam Indian Institute of Technology, Delhi
  • Daniel Weld University of Washington

DOI:

https://doi.org/10.1609/hcomp.v2i1.13170

Keywords:

Crowdsourcing, AI, machine learning, planning under uncertainty

Abstract

An ideal crowdsourcing or citizen-science system would route tasks to the most appropriate workers, but the best assignment is unclear because workers have varying skill, tasks have varying difficulty, and assigning several workers to a single task may significantly improve output quality. This paper defines a space of task routing problems, proves that even the simplest is NP-hard, and develops several approximation algorithms for parallel routing problems. We show that an intuitive class of requesters' utility functions is submodular, which lets us provide iterative methods for dynamically allocating batches of tasks that make near-optimal use of available workers in each round. Experiments with live oDesk workers show that our task routing algorithm uses only 48% of the human labor compared to the commonly used round-robin strategy. Further, we provide versions of our task routing algorithm which enable it to scale to large numbers of workers and questions and to handle workers with variable response times while still providing significant benefit over common baselines.

Downloads

Published

2014-09-05

How to Cite

Bragg, J., Kolobov, A., Mausam, M., & Weld, D. (2014). Parallel Task Routing for Crowdsourcing. Proceedings of the AAAI Conference on Human Computation and Crowdsourcing, 2(1), 11-21. https://doi.org/10.1609/hcomp.v2i1.13170