Journal article
Deterministic Budget-Feasible Clock Auctions
Operations research, v 73(6), pp 2972-2985
01 Nov 2025
Featured in Collection : UN Sustainable Development Goals @ Drexel
Abstract
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.
Metrics
1 Record Views
Details
- Title
- Deterministic Budget-Feasible Clock Auctions
- Creators
- Eric Balkanski - Columbia UniversityPranav Garimidi - a16z Crypto, New York, NY 10012 USAVasilis Gkatzelis - Drexel UniversityDaniel Schoepflin - Rutgers, The State University of New JerseyXizhi Tan - Drexel University
- Publication Details
- Operations research, v 73(6), pp 2972-2985
- Publisher
- Informs
- Number of pages
- 15
- Grant note
- 820931 / Simons Foundation 1928930 / Division of Mathematical Sciences; National Science Foundation (NSF); NSF - Directorate for Mathematical & Physical Sciences (MPS) 1755955; 2008280 / Division of Computing and Communication Foundations; National Science Foundation (NSF); NSF - Directorate for Computer & Information Science & Engineering (CISE) G-2021-16778 / Alfred P. Sloan Foundation
- Resource Type
- Journal article
- Language
- English
- Academic Unit
- Computer Science
- Web of Science ID
- WOS:001423485700001
- Scopus ID
- 2-s2.0-105024749130
- Other Identifier
- 991022197335504721
UN Sustainable Development Goals (SDGs)
This publication has contributed to the advancement of the following goals:
Source: SDGs in the Output
InCites Highlights
Data related to this publication, from InCites Benchmarking & Analytics tool:
- Collaboration types
- Domestic collaboration
- Web of Science research areas
- Management
- Operations Research & Management Science