Bayesian and Randomized Clock Auctions
成果类型：
Article
署名作者：
Feldman, Michal; Gkatzelis, Vasilis; Gravin, Nick; Schoepflin, Daniel
署名单位：
Tel Aviv University; Drexel University; Shanghai University of Finance & Economics; Rutgers University System; Rutgers University New Brunswick
刊物名称：
OPERATIONS RESEARCH
ISSN/ISSBN：
0030-364X
DOI：
10.1287/opre.2022.0421
发表日期：
2025
页码：
1965-1982
关键词：
摘要：
In a single-parameter mechanism design problem, a provider is looking to sell some service to a group of potential buyers. Each buyer i has a private value vi for receiving this service, but a feasibility constraint restricts which buyers can be simultaneously served. Recent work in economics introduced (deferred-acceptance) clock auctions as a superior class of auctions for this problem due to their transparency, simplicity, and strong incentive guarantees. Subsequent work focused on evaluating these auctions in terms of worst-case social welfare approximation, leading to strong impossibility results: Without prior information regarding buyers' values, deterministic clock auctions cannot achieve bounded approximations, even for feasibility constraints comprising two maximal feasible sets. We demonstrate how to circumvent these negative results by leveraging prior information or randomization. In particular, we provide clock auctions that give an O(log log k)-approximation for arbitrary downward-closed feasibility constraints with k maximal feasible sets for three different information regimes. The more prior information we have access to, the simpler the proposed auctions. In addition, we propose a parametrization of the complexity of clock auctions, paving the way for exciting future research.