Bayes-Optimal Effort Allocation in Crowdsourcing: Bounds and Index Policies
This addresses the challenge of efficiently allocating tasks to imperfect crowd workers, which is incremental as it builds on existing Lagrangian relaxation and index policy techniques.
The paper tackles the problem of Bayes-optimal effort allocation in crowdsourcing to maximize labeling accuracy under budget and time constraints, providing a computationally tractable upper bound and an index policy that outperforms state-of-the-art methods and performs close to optimal in numerical demonstrations.
We consider effort allocation in crowdsourcing, where we wish to assign labeling tasks to imperfect homogeneous crowd workers to maximize overall accuracy in a continuous-time Bayesian setting, subject to budget and time constraints. The Bayes-optimal policy for this problem is the solution to a partially observable Markov decision process, but the curse of dimensionality renders the computation infeasible. Based on the Lagrangian Relaxation technique in Adelman & Mersereau (2008), we provide a computationally tractable instance-specific upper bound on the value of this Bayes-optimal policy, which can in turn be used to bound the optimality gap of any other sub-optimal policy. In an approach similar in spirit to the Whittle index for restless multiarmed bandits, we provide an index policy for effort allocation in crowdsourcing and demonstrate numerically that it outperforms other stateof- arts and performs close to optimal solution.