On the Cost Complexity of Crowdsourcing

On the Cost Complexity of Crowdsourcing

Yili Fang, Hailong Sun, Pengpeng Chen, Jinpeng Huai

Proceedings of the Twenty-Seventh International Joint Conference on Artificial Intelligence
Main track. Pages 1531-1537. https://doi.org/10.24963/ijcai.2018/212

Existing efforts mainly use empirical analysis to evaluate the effectiveness of crowdsourcing methods, which is often unreliable across experimental settings. Consequently, it is of great importance to study theoretical methods. This work, for the first time, defines the cost complexity of crowdsourcing, and presents two theorems to compute the cost complexity. Our theorems provide a general theoretical method to model the trade-off between costs and quality, which can be used to evaluate and design crowdsourcing algorithms, and characterize the complexity of crowdsourcing problems. Moreover, following our theorems, we prove a set of corollaries that can obtain existing theoretical results for special cases. We have verified our work theoretically and empirically.
Keywords:
Machine Learning: Learning Theory
Humans and AI: Human Computation and Crowdsourcing