ICML 2026 paper cracks budget procurement for welfare and utility

Procurement under a fixed budget is a classic challenge: a buyer wants to purchase services from sellers, each with a private cost, but cannot exceed a total budget. Prior work focused on maximizing the buyer's total value—the sum of values for procured items. This paper, accepted at ICML 2026, generalizes the objective to include buyer utility (value minus payments), social welfare (value minus production costs), and any convex combination. The authors solve for optimal and approximately-optimal mechanisms in both prior-free (worst-case) and Bayesian (distribution known) settings.

For welfare maximization, they present a simple prior-free mechanism that guarantees a constant-factor approximation without any knowledge of seller costs. For utility maximization, where prior-free guarantees are impossible even with one seller, they turn to Bayesian settings. They first derive a utility-optimal mechanism that respects the budget in expectation, then show how to adjust it so the budget is never exceeded ex-post, while preserving near-optimal expected utility. Finally, they extend the approach to handle arbitrary convex objectives, offering a unified framework for budget-feasible procurement design.