Recent advances in crowdsourcing technologies enable computationally challenging tasks (e.g., sentiment analysis and entity resolution) to be performed by Internet workers. Upon finishing a task, the worker is given a monetary reward. A fundamental question is: how should workers be selected, so that the tasks in hand can be accomplished successfully and economically? In this paper, we study the Jury Selection Problem, or JSP: Given a monetary budget, and a set of decision-making tasks (e.g., “Is Bill Gates the CEO of Microsoft 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 decides the answer chosen by the largest number of jurors. We show that MV does not yield the best solution for JSP. We further show that among various voting strategies, Bayesian Voting (BV) facilitates JSP to be answered optimally. 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 computationally efficient. We extend our solution by considering the task owner’s “belief” (or prior) on the answers of the tasks. Experiments on synthetic and real datasets show that our new approach is consistently better than the best JSP solution known. Our approximate JQ computation algorithm is also highly accurate, yielding an error of 1% or less.

For the Jury Quality (JQ), as it is closely related to voting strategies and given a jury set, different strategies may have different JQ. We first systematically classify all strategies into two categories (Page 1), and then prove the existence of the optimal strategy, which is the Bayesian Voting (BV) Strategy (Page 2). Even though computing JQ for BV is NP-hard (Page 3), we give a bucket-based approximation algorithm (Page 4), and the approximation error bound of the polynomial algorithm is bounded within 1% (Page 5).