Simple yet Effective Budget-Feasible Procurement Auctions for Submodular Welfare Maximization

We study budget-feasible procurement auctions for social-welfare maximization under submodular valuations. In this setting, a buyer with a limited payment budget seeks to procure goods or services from strategic sellers, with the objective of maximizing the buyer's value for the selected sellers minus their true costs. We propose a simple yet effective single-round clock auction in which each seller receives at most one price offer. The mechanism satisfies desirable economic properties, including truthfulness, individual rationality, budget feasibility, and non-negative auctioneer surplus. Moreover, it achieves approximation ratios of 8.52 for monotone submodular valuations, 23.2 in expectation for non-monotone submodular valuations, and 24.52 deterministically for non-monotone submodular valuations, using only a linear number of value-oracle queries. These guarantees improve over the recent independent work of Cui et al. (ICML 2026) on the same problem in approximation ratio, value-oracle complexity, and number of pricing rounds. Experiments on influence maximization in social networks and crowdsourcing further demonstrate the effectiveness and efficiency of our approach.