On Optimality of Jury Selection in Crowdsourcing
Yudian Zheng, Reynold C. K. Cheng, Silviu Maniu, Luyi Mo · The HKU Scholars Hub (University of Hong Kong) · 2015
Recent advances in crowdsourcing technologies enable computa-tionally challenging tasks (e.g., sentiment analysis and entity reso-lution) to be performed by Internet workers, driven mainly by mon-etary incentives. A fundamental question is: how should work-ers be selected, so that the tasks in hand can be accomplished successfully and economically? In this paper, we study the Jury Selection Problem (JSP): Given a monetary budget, and a set of decision-making tasks (e.g., “Is Bill Gates still the CEO of Mi-crosoft now?”), return the set of workers (called jury), such that their answers yield the highest “Jury Quality ” (or JQ). Existing JSP solutions make use of the Majority Voting (MV) strategy, which uses the answer chosen by the largest number of workers. We show that MV does not yield the best solution for JSP. We further prove that among all voting strategies (including deterministic and ran-domized strategies), Bayesian Voting (BV) can optimally solve JSP. We then examine how to solve JSP based on BV. This is technically challenging, since computing the JQ with BV is NP-hard. We solve this problem by proposing an approximate algorithm that is com-putationally efficient. Our approximate JQ computation algorithm is also highly accurate, and its error is proved to be bounded within 1%. We extend our solution by considering the task owner’s “be-lief ” (or prior) on the answers of the tasks. Experiments on syn-thetic and real datasets show that our new approach is consistently better than the best JSP solution known. 1.