  In this paper we consider a mechanism design problem in the context of
large-scale crowdsourcing markets such as Amazon's Mechanical Turk,
ClickWorker, CrowdFlower. In these markets, there is a requester who wants to
hire workers to accomplish some tasks. Each worker is assumed to give some
utility to the requester. Moreover each worker has a minimum cost that he wants
to get paid for getting hired. This minimum cost is assumed to be private
information of the workers. The question then is - if the requester has a
limited budget, how to design a direct revelation mechanism that picks the
right set of workers to hire in order to maximize the requester's utility.
  We note that although the previous work has studied this problem, a crucial
difference in which we deviate from earlier work is the notion of large-scale
markets that we introduce in our model. Without the large market assumption, it
is known that no mechanism can achieve an approximation factor better than
0.414 and 0.5 for deterministic and randomized mechanisms respectively (while
the best known deterministic and randomized mechanisms achieve an approximation
ratio of 0.292 and 0.33 respectively). In this paper, we design a
budget-feasible mechanism for large markets that achieves an approximation
factor of 1-1/e (i.e. almost 0.63). Our mechanism can be seen as a
generalization of an alternate way to look at the proportional share mechanism
which is used in all the previous works so far on this problem. Interestingly,
we also show that our mechanism is optimal by showing that no truthful
mechanism can achieve a factor better than 1-1/e; thus, fully resolving this
setting. Finally we consider the more general case of submodular utility
functions and give new and improved mechanisms for the case when the markets
are large.
