Budget Feasible Procurement Auctions

We consider a simple and well-studied model for procurement problems and solve it to optimality. A buyer with a fixed budget wants to procure, from a set of available workers, a budget feasible subset that maximizes her utility: Any worker has a private reservation price and provides a publicly known utility to the buyer in case of being procured. The buyer's utility function is additive over items. The goal is designing a direct revelation mechanism that solicits workers' reservation prices and decides which workers to recruit and how much to pay them. Moreover, the mechanism has to maximize the buyer's utility without violating her budget constraint. We study this problem in the prior-free setting; our main contribution is finding the optimal mechanism in this setting, under the "small bidders" assumption. This assumption, also known as the "small bid to budget ratio assumption," states that the bid of each seller is small compared with the buyer's budget. We also study a more general class of utility functions: submodular utility functions. For this class, we improve the existing mechanisms significantly under our assumption.