Timezone: »

 
Poster
Achieving budget-optimality with adaptive schemes in crowdsourcing
Ashish Khetan · Sewoong Oh

Tue Dec 06 09:00 AM -- 12:30 PM (PST) @ Area 5+6+7+8 #123
in Tuesday Posters »

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.

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

Author Information

Ashish Khetan (University of Illinois Urbana-)
Sewoong Oh (University of Washington)

More from the Same Authors