Efficient Budget Allocation with Accuracy Guarantees for Crowdsourcing Classification Tasks

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 number 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. Copyright © 2013, International Foundation for Autonomous Agents and Multiagent Systems (www.ifaamas.org). All rights reserved