Fundamental Limits of Budget-Fidelity Trade-off in Label Crowdsourcing
This work provides foundational theoretical insights for crowdsourcing systems, addressing the trade-off between cost and accuracy in human-in-the-loop computation.
The paper tackles the problem of maximizing label accuracy in crowdsourcing under a fixed budget by modeling it as an information-theoretic rate-distortion problem, establishing fundamental limits on achievable fidelity and analyzing a specific query scheme with optimized pricing.
Digital crowdsourcing (CS) is a modern approach to perform certain large projects using small contributions of a large crowd. In CS, a taskmaster typically breaks down the project into small batches of tasks and assigns them to so-called workers with imperfect skill levels. The crowdsourcer then collects and analyzes the results for inference and serving the purpose of the project. In this work, the CS problem, as a human-in-the-loop computation problem, is modeled and analyzed in an information theoretic rate-distortion framework. The purpose is to identify the ultimate fidelity that one can achieve by any form of query from the crowd and any decoding (inference) algorithm with a given budget. The results are established by a joint source channel (de)coding scheme, which represent the query scheme and inference, over parallel noisy channels, which model workers with imperfect skill levels. We also present and analyze a query scheme dubbed $k$-ary incidence coding and study optimized query pricing in this setting.