Deterministic Budget-Feasible Clock Auctions

• 成果类型: Article; Early Access
• 署名作者: Balkanski, Eric; Garimidi, Pranav; Gkatzelis, Vasilis; Schoepflin, Daniel; Tan, Xizhi
• 署名单位: Columbia University; Drexel University; Rutgers University System; Rutgers University New Brunswick
• 刊物名称: OPERATIONS RESEARCH
• ISSN/ISSBN: 0030-364X
• DOI: 10.1287/opre.2023.0526
• 发表日期: 2025

摘要

We revisit the well-studied problem of budget-feasible procurement, where a buyer with a strict budget constraint seeks to acquire services from a group of strategic providers (the sellers). During the last decade, several strategy-proof budget-feasible procurement auctions have been proposed, aiming to maximize the value of the buyer while eliciting each seller's true cost for providing their service. Our main result in this paper is a novel method for designing budget-feasible auctions, leading to solutions that outperform the previously proposed auctions in multiple ways. First, our solutions take the form of descending clock auctions, rather than sealed-bid auctions, and thus satisfy a list of very appealing properties, making these auctions much more likely to be used in practice. Second, in contrast to previous results that heavily depend on randomization, our auctions are deterministic. In fact, our deterministic auctions achieve a O(1)-approximation for submodular valuations, resolving a main open question in this literature. Finally, we improve the previous best-known approximation factor for monotone submodular valuations, the focus of most of the prior work.