Online Task Assignment in Crowdsourcing Markets

By Chien-Ju Ho, Jennifer Wortman Vaughan. AAAI Conference on Artificial Intelligence, 2012

361 citations recorded by the source corpus.

We explore the problem of assigning heterogeneous tasks to workers with different, unknown skill sets in crowdsourcing markets such as Amazon Mechanical Turk. We first formalize the online task assignment problem, in which a requester has a fixed set of tasks and a budget that specifies how many times he would like each task completed. Workers arrive one at a time (with the same worker potentially arriving multiple times), and must be assigned to a task upon arrival. The goal is to allocate workers to tasks in a way that maximizes the total benefit that the requester obtains from the completed work. Inspired by recent research on the online adwords problem, we present a two-phase exploration-exploitation assignment algorithm and prove that it is competitive with respect to the optimal offline algorithm which has access to the unknown skill levels of each worker. We empirically evaluate this algorithm using data collected on Mechanical Turk and show that it performs better than random assignment or greedy algorithms. To our knowledge, this is the first work to extend the online primal-dual technique used in the online adwords problem to a scenario with unknown parameters, and the first to offer an empirical validation of an online primal-dual algorithm.

Subfields: Computer Networks and Communications, Computer Science Applications, Management Science and Operations Research

View Paper: https://www.semanticscholar.org/paper/bbae5c682d800fbdc7d4db0b1b50258e870d9130

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Computer Networks and Communications

In Computer Science Applications

In Management Science and Operations Research

Citations in the corpus

Online mobile Micro-Task Allocation in spatial crowdsourcing (2016, background): “[22] propose online task assignment in crowdsourcing, where only tasks are dynamic.”
Learning to Hire Teams (2015, methodology): “Kalyanakrishnan et al. (2012) design an adaptive ( , δ)-PAC algorithm LUCB-1 for selecting m best actions, using upper and lower confidence bounds.”
Crowdsourced Data Management: A Survey (2016, background): “Themodel in [54], [55] assumes that each task is related to a specific domain, which is known in advance.”
Artificial Intelligence and Collective Intelligence (2014, background): “Ho et al. (Ho and Vaughan 2012; Ho, Jabbari, and Vaughan 2013) and Tran-Thanh et al. (Tran-Thanh et al. 2012) assume constraints on the number of tasks that may be assigned to any single worker, and divide the control problem into two explicit phases of exploration and exploitation.”
Online Matching and Ad Allocation (2013, background): “Recently, the online matching algorithms from this survey have found applications [54] in crowdsourcing markets.”
Mobile Crowd Sensing and Computing (2015, background): “Successful approaches to task assignment in online crowdsourcing markets can be explored [Ho and Vaughan 2012].”