A budget-limited mechanism for category-aware crowdsourcing of multiple-choice tasks

摘要

Crowdsourcing harnesses human effort to solve computer-hard problems such as photo tagging, entity resolution and sentiment analysis. 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 and each task involves a choice between just two alternatives. However, this neglects the fact that many crowdsourcing applications ask workers to choose between multiple alternatives and that different tasks can belong to a variety of diverse categories. Moreover, workers may have varying abilities across these categories. For example, a science enthusiast is likely to do better than a cinephile when answering a question such as “selecting the melting point of Copper from 1) 327 degrees Celcius, 2) 1085 degrees Celcius and 3) 1495 degrees Celcius”. And a cinephile is likely to perform better in tasks related to movies such as “how many episodes of Fooly Cooly were ever made? 1) 6 2) 7 and 3) 8”. To incorporate such category-aware crowdsourcing of multiple-choice tasks, 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. We also prove that INCARE can achieve a bounded approximation ratio for the optimal budget allocation mechanism with full knowledge of workers' true costs. Finally, our numerical simulations, on both real and synthetic data, show that, compared to the state of the art, INCARE: (i) can improve the accuracy by up to 98%, given a limited budget; and (ii) is significantly more robust to inaccuracies in prior information about each worker's ability and each task's difficulty.