ABStract

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 formal- ize theonline 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 to-tal 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 theoptimal offline algorithm which  has access to the unknown skill levels of each worker.  We empirically evaluate this al-gorithm using data collected on  Mechanical Turk and show that it performs better than random assignment or greedy al- gorithms.  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 algo-rithm.