Bayesian and Randomized Clock Auctions

Michal Feldman (), Vasilis Gkatzelis (), Nick Gravin () and Daniel Schoepflin ()
Additional contact information
Michal Feldman: Blavatnik School of Computer Science, Tel Aviv University, Tel Aviv 6997801, Israel; and Microsoft Research, Herzliya 4672415, Israel
Vasilis Gkatzelis: Department of Computer Science, Drexel University, Philadelphia, Pennsylvania 19104
Nick Gravin: Institute for Theoretical Computer Science, Shanghai University of Finance and Economics, Shanghai 6997801, China
Daniel Schoepflin: Center for Discrete Mathematics and Theoretical Computer Science, Rutgers University, Piscataway, New Jersey 08854

Operations Research, 2025, vol. 73, issue 4, 1965-1982

Abstract: 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 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.

Keywords: Market; Analytics; and; Revenue; Management; clock auctions; obvious strategy-proofness; welfare maximization (search for similar items in EconPapers)
Date: 2025
References: Add references at CitEc
Citations:

Downloads: (external link)
http://dx.doi.org/10.1287/opre.2022.0421 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:oropre:v:73:y:2025:i:4:p:1965-1982

Access Statistics for this article

More articles in Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().