From Welfare to Utility: Generalized Objectives in Budget-Feasible Procurement

We study mechanism design for the budget-feasible procurement problem, a natural problem that arises when a buyer wants to procure goods or services from multiple strategic sellers who each have a cost to provide that service, the buyer has a value for each service procured, but is constrained by a budget. In contrast to prior work, which has focused on buyer value maximization for this problem, we solve for optimal and approximately-optimal mechanisms for the objectives of buyer utility (value of procured services minus payments), welfare (value minus production costs), and generalizations of the two. For welfare, we design a simple mechanism that obtains a constant-factor approximation for the prior-free (worst-case) setting. As prior-free mechanisms fail to provide any guarantee for utility, even for a single seller, we consider Bayesian settings, where the buyer has distributional knowledge over sellers' costs. We first provide a utility-optimal mechanism that satisfies the buyer's budget constraint in expectation, then we show how to modify the mechanism to satisfy the budget constraint ex-post, for every realization of seller costs, while still obtaining near-optimal utility guarantees. Finally, we generalize our mechanisms to other objectives.

Budget-feasible procurement concerns an organization that seeks to buy services from multiple providers, but cannot spend more than a fixed budget. The bulk of prior work studies the design of mechanisms that maximize the total value the buyer obtains from these purchases, hence using as much of the budget as possible. Our work studies two alternative goals: i) maximizing the overall welfare of the system, which accounts for both the buyer’s total value obtained and the providers’ production costs incurred, and ii) maximizing the buyer’s utility, which is the organization’s net gain after the payments to the providers. The systems we aim to design must adhere to the given budget constraint and must ensure that providers do not benefit from acting strategically and/or lying. We provide a simple mechanism that achieves approximately-optimal welfare (without any prior statistical information about the providers needed), as well as a simple mechanism that achieves approximately-optimal buyer utility (but with the extra requirement of statistical information about the providers costs). This work is relevant to the many systems and organizations that must allocate a limited budget while balancing efficiency, cost, and incentives, and in particular, provides a solution using simple, understandable, and computationally tractable mechanisms.