Published:
2013-11-10
Proceedings:
Proceedings of the AAAI Conference on Human Computation and Crowdsourcing, 1
Volume
Issue:
Vol. 1 (2013): First AAAI Conference on Human Computation and Crowdsourcing
Track:
Full Papers
Downloads:
Abstract:
We introduce and consider the problem of effectively organizing a population of workers of varying abilities. We assume that arriving tasks for the workforce are homogeneous, and that each is characterized by an unknown and one- dimensional difficulty value x ∈ [0, 1]. Each worker i is characterized by their ability wi ∈ [0, 1], and can solve the task if and only if x ≤ wi. If a worker is unable to solve a given task it must be forwarded to a worker of greater ability. For a given set of worker abilities W and a distribution P over task difficulty, we are interested in the problem of designing efficient forwarding structures for W and P. We give efficient algorithms and structures that simultaneously (approximately) minimize both the maximum workload of any worker, and the number of workers that need to attempt a task. We identify broad conditions under which workloads diminish rapidly with the workforce size, yet only a constant number of workers attempt each task.
DOI:
10.1609/hcomp.v1i1.13086
HCOMP
Vol. 1 (2013): First AAAI Conference on Human Computation and Crowdsourcing
ISBN 978-1-57735-607-3