Logo image
Back
Bayesian and Randomized Clock Auctions
Journal article   Open access   Peer reviewed

Bayesian and Randomized Clock Auctions

Michal Feldman, Vasilis Gkatzelis, Nick Gravin and Daniel Schoepflin
Operations research, v 73(4)
06 Feb 2025
DOI: https://doi.org/10.1287/opre.2022.0421
url
http://arxiv.org/abs/2202.09291View
Submitted Open arXiv.org - Non-exclusive license to distribute

Abstract

clock auctions obvious strategy-proofness welfare maximization
The recently introduced and highly practical class of deferred acceptance clock auctions offers a unique combination of desirable properties, including obvious strategy-proofness, unconditional winner privacy, and transparency. Early excitement around these auctions was dampened due to a result demonstrating that no deterministic and prior-free clock auction can guarantee better than a logarithmic approximation of the optimal social welfare, even in simple settings. In “Bayesian and Randomized Clock Auctions,” Feldman, Gkatzelis, Gravin, and Schoepflin reignite this excitement by demonstrating that one can achieve improved results for a wide class of instances if a clock auction can either use randomization or has access to prior information. The authors provide three different clock auctions that achieve these improved guarantees given access to different amounts of prior information, exhibiting how additional information can further simplify the auction design. 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 v i 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 [Formula: see text]-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. Funding: This work was supported by the Simons Foundation [Grant 820931], the Science and Technology Innovation 2030 [Grant 2018AAA0100903], the National Natural Science Foundation of China [Grant 62150610500], the Central University Basic Research Fund of China, the National Science Foundation [Grants CCF-1755955 and CCF-2008280], the H2020 European Research Council [Grant 866132], and the Israel Science Foundation [Grant 317/17]. Supplemental Material: The online appendices are available at https://doi.org/10.1287/opre.2022.0421 .

Metrics

10 Record Views

Details

InCites Highlights

Data related to this publication, from InCites Benchmarking & Analytics tool:

Collaboration types
Domestic collaboration
International collaboration
Web of Science research areas
Management
Operations Research & Management Science
Logo image