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 as well as on a realistic case study of Wikipedia translation project using Mechanical Turk workers. Our results demonstrate the practical applicability of our mechanisms for realistic crowdsourcing markets on the web.

@inproceedings{goel14mechanismdesign,
	author = {Gagan Goel and Afshin Nikzad and Adish Singla},
	booktitle = {AAAI Conference on Human Computation and Crowdsourcing (HCOMP)},
	month = {November},
	title = {Mechanism Design for Crowdsourcing Markets with Heterogeneous Tasks},
	year = {2014}}