Efficient Budget Allocation and Task Assignment in Crowdsourcing

Abstract

Requesters in crowdsourcing marketplaces would like to efficiently allocate a fixed budget, among the set of tasks to be completed, which are of varying difficulty levels. The uncertainty in the arrival and departure of workers and the diversity in their skill levels add to the challenge, as minimizing the overall completion time is also an important concern. Current literature focuses on sequential allocation of tasks, i.e., task assignment to one worker at a time, or assumes the task difficulties to be known in advance. In this paper, we study the problem of efficient budget allocation under dynamic worker pool in crowdsourcing. Specifically, we consider binary labeling tasks for which the budget allocation problem can be cast as one of finding the optimal policy for a Markov decision process. We present a mathematical framework for modeling the problem and propose a class of algorithms for obtaining its solution. Experiments on simulated as well as real data demonstrate the capability of these algorithms to achieve performance very close to sequential allocation in much less time and their superiority over naive allocation strategies.