Bayesian and Randomized Clock Auctions

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.

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.