Matching Workers Expertise with Tasks: Incentives in Heterogeneous

Designing optimal pricing policies and mechanisms for allocating tasks to workers is central to the online crowdsourcing markets. In this paper, we consider the following realistic setting of online crowdsourcing markets - we are given a heterogeneous set of tasks requiring certain skills; each worker has certain expertise and interests which define the set of tasks she is interested in and willing to do. Given this bipartite graph between workers and tasks, we design our mechanism TM-UNIFORM which does the allocation of tasks to workers, while ensuring budget feasibility, incentive-compatibility and achieves near-optimal utility. We further extend our results by exploiting a link with online Adwords allocation problem and present a randomized mechanism TM-RANDOMIZED with improved approximation guarantees. Apart from strong theoretical guarantees, we carry out extensive experimentation using simulations on a realistic case study ofWikipedia translation project using Mechanical Turk. Our results demonstrate the practical applicability of our mechanisms for realistic crowdsourcing markets on the web. We note that this is the first paper that addresses this setting of matching tasks to workers from a mechanism design perspective. Previous work either made a simplifying assumption that tasks are homogeneous or didn’t consider the matching constraints given by the bipartite graph.