商科assignment代写-Online Task Assignment in Crowdsourcing Markets
Online Task Assignment in Crowdsourcing Markets
We explore the problem of assigning heterogeneous tasks to workers with different, unknown skill sets in crowdsourcing markets such as Amazon Mechanical Turk. We ﬁrst formal- ize theonline task assignment problem, in which a requester has a ﬁxed set of tasks and a budget that speciﬁes 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 beneﬁt 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 ofﬂine 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 ﬁrst work to extend the online primal-dual technique used in the online adwords problem to a scenario with unknown parameters, and the ﬁrst to offer an empirical validation of an online primal-dual algo-rithm.