We study procurement games where each seller supplies multiple units of his item, with a cost per unit known only to him. The buyer can purchase any number of units from each seller, values different combinations of the items differently, and has a budget for his total payment. For a special class of procurement games, the bounded knapsack problem, we show that no universally truthful budget-feasible mechanism can approximate the optimal value of the buyer within @math , where @math is the total number of units of all items available. We then construct a polynomial-time mechanism that gives a @math -approximation for procurement games with concave additive valuations , which include bounded knapsack as a special case. Our mechanism is thus optimal up to a constant factor. Moreover, for the bounded knapsack problem, given the well-known FPTAS, our results imply there is a provable gap between the optimization domain and the mechanism design domain. Finally, for procurement games with sub-additive valuations , we construct a universally truthful budget-feasible mechanism that gives an @math -approximation in polynomial time with a demand oracle.
In this paper we consider a mechanism design problem in the context of large-scale crowdsourcing markets such as Amazon's Mechanical Turk mturk, ClickWorker clickworker, CrowdFlower 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 on getting hired. 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 (Singer (2010) (2011)) 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 a competitive ratio 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 a competitive ratio of 1 -- 1 e = 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 can 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 market is large.  This paper discusses two advancements in the theory of designing truthful randomized mechanisms. Our first contribution is a new framework for developing truthful randomized mechanisms. The framework enables the construction of mechanisms with polynomially small failure probability. This is in contrast to previous mechanisms that fail with constant probability. Another appealing feature of the new framework is that bidding truthfully is a stronglydominant strategy. The power of the framework is demonstrated by an @math -mechanism for combinatorial auctions that succeeds with probability @math . The other major result of this paper is an O(logmloglogm) randomized truthful mechanism for combinatorial auction with subadditivebidders. The best previously-known truthful mechanism for this setting guaranteed an approximation ratio of @math . En route, the new mechanism also provides the best approximation ratio for combinatorial auctions with submodularbidders currently achieved by truthful mechanisms.