A budget-limited mechanism for category-aware crowdsourcing systems

Abstract

Crowdsourcing harnesses human effort to solve computer-hard problems. Such tasks often have different levels of difficulty and workers have varying levels of skill at completing them. With a limited budget, it is important to wisely allocate the spend among the tasks and workers such that the overall outcome is as good as possible. Most existing work addresses this budget allocation problem by assuming that workers have a single level of ability for all tasks. However, this neglects the fact that tasks can belong to a variety of diverse categories and workers may have varying abilities across them. To incorporating such category-awareness, we model the interaction between the crowdsource campaign initiator and the workers as a procurement auction and propose a computationally efficient mechanism, INCARE, to achieve high-quality outcomes given a limited budget. We prove that INCARE is budget feasible, incentive compatible and individually rational. Finally, our experiments on a standard real-world data set show that, compared to the state of the art, INCARE: (i) can improve the accuracy by up to 40%, given a limited budget; and (ii) is significantly more robust to inaccuracies in prior information about each task's difficulty.