2014/05/10 by Nima Anari, Anari, Nima, Gagan Goel +3 · 2 citations
Computer Science · Decision Sciences · #91B26 #Auction Theory and Applications #Blockchain Technology Applications and Security #Computer Science and Game Theory (cs.GT) #FOS: Computer and information sciences #Mobile Crowdsensing and Crowdsourcing #Privacy-Preserving Technologies in Data
paper · pdf · doi:10.48550/arxiv.1405.2452
openalex publication_date 2014/05/10 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
In this paper we consider a mechanism design problem in the context of\nlarge-scale crowdsourcing markets such as Amazon's Mechanical Turk,\nClickWorker, CrowdFlower. In these markets, there is a requester who wants to\nhire workers to accomplish some tasks. Each worker is assumed to give some\nutility to the requester. Moreover each worker has a minimum cost that he wants\nto get paid for getting hired. This minimum cost is assumed to be private\ninformation of the workers. The question then is - if the requester has a\nlimited budget, how to design a direct revelation mechanism that picks the\nright set of workers to hire in order to maximize the requester's utility.\n We note that although the previous work has studied this problem, a crucial\ndifference in which we deviate from earlier work is the notion of large-scale\nmarkets that we introduce in our model. Without the large market assumption, it\nis known that no mechanism can achieve an approximation factor better than\n0.414 and 0.5 for deterministic and randomized mechanisms respectively (while\nthe best known deterministic and randomized mechanisms achieve an approximation\nratio of 0.292 and 0.33 respectively). In this paper, we design a\nbudget-feasible mechanism for large markets that achieves an approximation\nfactor of 1-1/e (i.e. almost 0.63). Our mechanism can be seen as a\ngeneralization of an alternate way to look at the proportional share mechanism\nwhich is used in all the previous works so far on this problem. Interestingly,\nwe also show that our mechanism is optimal by showing that no truthful\nmechanism can achieve a factor better than 1-1/e; thus, fully resolving this\nsetting. Finally we consider the more general case of submodular utility\nfunctions and give new and improved mechanisms for the case when the markets\nare large.\n