2026/07/31 by Alon Eden, Eldar Kerner, Kira Goldner +1
Computer Science · #cs.GT
Accepted at the Forty-third International Conference on Machine Learning (ICML 2026). Version 2: Corrected alphabetical author order, changed proofs of Proposition 1 and Lemma 6; Main conclusions unchanged
arxiv created 2026/08/04 · arxiv updated 2026/08/06
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.