Budget-Feasible Mechanisms for Submodular Welfare Maximization in Procurement Auctions

Budget-feasible procurement auctions play a pivotal role in various AI-driven marketplaces, such as data acquisition and crowdsourcing, where a buyer with a limited budget seeks to procure services from strategic sellers with private costs. While numerous budget-feasible mechanisms have been proposed for the classic objective of maximizing the buyer's valuation, the more challenging and economically significant objective of social welfare maximization has only recently been studied, and existing approaches still sacrifice budget feasibility, thereby limiting their practical applicability. In this paper, we bridge this gap by proposing BFM-SWM, the first budget-feasible mechanism with provable approximation guarantees for submodular welfare maximization in procurement auctions. Our mechanism satisfies standard economic properties, including truthfulness, individual rationality, and non-negative auctioneer surplus. As a by-product, we develop BFM-VM, a variant tailored for valuation maximization, which achieves a deterministic approximation ratio of $1/(12+4\sqrt{3})$ for general submodular functions, substantially improving upon the best-known deterministic ratio of $1/64$ established by [Balkanski et al., SODA 2022], while reducing the running time from $\mathcal{O}(n^2\log n)$ to $\mathcal{O}(n\log n)$. Extensive experiments demonstrate the efficiency and effectiveness of our mechanisms.

Many AI-powered marketplaces rely on procurement: a buyer with a limited budget wants to purchase useful services, data, or labor from many sellers. These sellers may have private costs, so a good auction rule must encourage them to report honestly while also keeping the buyer within budget. Existing methods mainly focus on getting high value for the buyer, but this can sometimes lead to purchases that are too expensive relative to their benefit. In this paper, we study a more balanced goal: maximizing the overall social benefit, measured as the value created minus the cost of obtaining it. We design a new auction mechanism that is budget-feasible, encourages honest behavior, and avoids a deficit for the buyer. This is important for practical settings such as data acquisition, crowdsourcing, and influence maximization, where resources are limited and participants act strategically. We also show that a variant of our method improves the best known deterministic guarantee for a classic version of the problem. Experiments demonstrate that our mechanisms are both effective and efficient.