In this paper we address the problem of budget allocation for redundantly crowdsourcing a set of classification tasks where a key challenge is to find a trade–off between the total cost and the accuracy of estimation. We propose CrowdBudget, an agent–based budget allocation algorithm, that efficiently divides a given budget among different tasks in order to achieve low estimation error. In particular, we prove that CrowdBudget can achieve at most max{0, K/2 ? O (?B)} estimation error with high probability, where K is the num- ber of tasks and B is the budget size. This result significantly outperforms the current best theoretical guarantee from Karger et al. In addition, we demonstrate that our algorithm outperforms existing methods by up to 40% in experiments based on real–world data from a prominent database of crowdsourced classification responses.
展开▼
