Budget-Optimal Task Allocation for Reliable Crowdsourcing Systems

By David R Karger, Sewoong Oh, Devavrat Shah. Operational Research, 2011

394 citations recorded by the source corpus.

Crowdsourcing systems, in which numerous tasks are electronically distributed to numerous “information pieceworkers,” have emerged as an effective paradigm for human-powered solving of large-scale problems in domains such as image classification, data entry, optical character recognition, recommendation, and proofreading. Because these low-paid workers can be unreliable, nearly all such systems must devise schemes to increase confidence in their answers, typically by assigning each task multiple times and combining the answers in an appropriate manner, e.g., majority voting. In this paper, we consider a general model of such crowdsourcing tasks and pose the problem of minimizing the total price i.e., number of task assignments that must be paid to achieve a target overall reliability. We give a new algorithm for deciding which tasks to assign to which workers and for inferring correct answers from the workers' answers. We show that our algorithm, inspired by belief propagation and low-rank matrix approximation, significantly outperforms majority voting and, in fact, is optimal through comparison to an oracle that knows the reliability of every worker. Further, we compare our approach with a more general class of algorithms that can dynamically assign tasks. By adaptively deciding which questions to ask to the next set of arriving workers, one might hope to reduce uncertainty more efficiently. We show that, perhaps surprisingly, the minimum price necessary to achieve a target reliability scales in the same manner under both adaptive and nonadaptive scenarios. Hence, our nonadaptive approach is order optimal under both scenarios. This strongly relies on the fact that workers are fleeting and cannot be exploited. Therefore, architecturally, our results suggest that building a reliable worker-reputation system is essential to fully harnessing the potential of adaptive designs.

Subfields: Computer Networks and Communications, Computer Science Applications, Management Science and Operations Research

View Paper: https://www.semanticscholar.org/paper/ede8c5a37a78f004d7fa8df443b22098f0579f0b

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Computer Networks and Communications

In Computer Science Applications

In Management Science and Operations Research

Citations in the corpus

Avoiding Imposters and Delinquents: Adversarial Crowdsourcing and Peer Prediction (2016, background): “…agents maximizing a payoff function (Dasgupta and Ghosh, 2013; Kamble et al., 2015; Shnayder et al., 2016), that the workers follow a simple statistical model (Karger et al., 2014; Zhang et al., 2014; Zhou et al., 2015), or some combination of the above (Shah and Zhou, 2015; Shah et al., 2015).”
Lean Multiclass Crowdsourcing (2018, methodology): “Alternate inference algorithms for the DS model are based on spectral methods [7, 4, 12, 13, 14, 40], belief propagation [20, 23], expectation maximization [20, 40], maximum entropy [41, 42], weighted majority voting [19, 17] and max-margin [32].”
Efficient Learning for Crowdsourced Regression (2017, methodology): “Formally, from Lemma 5 in Karger et al. (2014), it is straightforward to check that P[Gρ,2k is not a tree] ≤ 3 n (`r)2k+1 (20) where we letGρ,2k = (Vρ,2k,Wρ,2k, Eρ,2k) denote the subgraph ofG induced by all the nodes within (graph) distance 2k from root ρ.”
Crowdsourcing large scale wrapper inference (2014, background): “There have been several attempts to frame the learning from noisy workers [15,22] within theoretical guaranteed properties.”
Learning From Noisy Singly-labeled Data (2017, methodology): “Karger et al. (2014) introduces a message-passing algorithm for estimating binary labels under the Dawid-Skene model, showing that it performs strictly better than majority voting when the number of labels per example exceeds some threshold.”
Spectral Methods Meet EM: A Provably Optimal Algorithm for Crowdsourcing (2014, methodology): “Several alternative approaches have been developed that aim to circumvent the theoretical deficiencies of the EM algorithm, still in the context of the one-coin model [14, 15, 11, 7].”