Skip to yearly menu bar Skip to main content


Achieving budget-optimality with adaptive schemes in crowdsourcing

Ashish Khetan · Sewoong Oh

Area 5+6+7+8 #123

Keywords: [ (Application) Web Applications and Internet Data ] [ (Other) Probabilistic Models and Methods ] [ Matrix Factorization ] [ Spectral Methods ]


Adaptive schemes, where tasks are assigned based on the data collected thus far, are widely used in practical crowdsourcing systems to efficiently allocate the budget. However, existing theoretical analyses of crowdsourcing systems suggest that the gain of adaptive task assignments is minimal. To bridge this gap, we investigate this question under a strictly more general probabilistic model, which has been recently introduced to model practical crowdsourcing data sets. Under this generalized Dawid-Skene model, we characterize the fundamental trade-off between budget and accuracy, and introduce a novel adaptive scheme that matches this fundamental limit. We further quantify the gain of adaptivity, by comparing the trade-off with the one for non-adaptive schemes, and confirm that the gain is significant and can be made arbitrarily large depending on the distribution of the difficulty level of the tasks at hand.

Live content is unavailable. Log in and register to view live content