Lune

ICML2026Top-tier venue

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

Alon Eden, Kira Goldner, Eldar Kerner, Thodoris Tsilivis

Abstract

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.

Ask Lune

Know this paper in minutes, not an afternoon.

Lune can read every page of it and the top-tier papers that cite it, and gives you its claims, its evidence and its limits, each one cited to the paper it comes from. No skimming, no AI slop.

1 top-tier paper has cited it since. Know what they found before your reviewers do.

Questions to start from

Lune can draw on

the full paper · the top-tier papers that cite it · related work

Get the answer

Free to start. No credit card required.

Lineage

  • Knowing Who, Not How Much: Learning-Augmented Mechanisms for Consumer Utility Maximization cites Multidimensional Bayesian Utility Maximization: Tight Approximations to Welfare
  • Knowing Who, Not How Much: Learning-Augmented Mechanisms for Consumer Utility Maximization cites Multi-parameter Mechanisms for Consumer Surplus Maximization
Builds onCited byLeft to right by year; the more cited, the higher.

Cited by top-tier papers1

  1. Knowing Who, Not How Much: Learning-Augmented Mechanisms for Consumer Utility MaximizationKira Goldner, Divyarthi Mohan, Thodoris TsilivisICML 2026 · 2 citations

Builds on7

  1. Incentive Mechanism for Horizontal Federated Learning Based on Reputation and Reverse AuctionJingwen Zhang, Yuezhou Wu, Rong PanWWW 2021 · 176 citations
  2. Tight Guarantees for Multi-unit Prophet Inequalities and Online Stochastic KnapsackJiashuo Jiang, Will Ma, Jiawei ZhangSODA 2022 · 20 citations
  3. Multidimensional Bayesian Utility Maximization: Tight Approximations to WelfareKira Goldner, Taylor LundyNeurIPS 2025 · 3 citations
  4. Knowing Who, Not How Much: Learning-Augmented Mechanisms for Consumer Utility MaximizationKira Goldner, Divyarthi Mohan, Thodoris TsilivisICML 2026 · 2 citations
  5. Multi-parameter Mechanisms for Consumer Surplus MaximizationTomer Ezra, Daniel Schoepflin, Ariel ShaulkerSTOC 2025 · 2 citations

Related papers

  1. Prior-Free Mechanism with Welfare GuaranteesGuru Guruganesh, Jon Schneider, Joshua R. WangWWW 2024
  2. Budget-Feasible Mechanisms for Submodular Welfare Maximization in Procurement AuctionsShuang Cui, He Huang, Yu-e Sun, Chen XueICML 2026
  3. Deterministic Budget-Feasible Clock AuctionsEric Balkanski, Pranav Garimidi, Vasilis Gkatzelis, Daniel Schoepflin et al.SODA 2022 · 12 citations
  4. Bulow-Klemperer-Style Results for Welfare Maximization in Two-Sided MarketsMoshe Babaioff, Kira Goldner, Yannai A. GonczarowskiSODA 2020 · 12 citations
  5. Fixed-Price Approximations in Bilateral TradeZi Yang Kang, Francisco Pernice, Jan VondrákSODA 2022 · 13 citations
Dusk over the sea between two cliffs drawn in fine vertical lines