Bayesian and randomized clock auctions (Q6903483)

This paper is devoted to the problem of designing a single-parameter mechanism in which a supplier seeks to sell a service to a group of potential buyers. It is assumed that each buyer \(i\) has a private value \(v_i\) for receiving this service, but a feasibility constraint restricts which buyers can be simultaneously served. It is known that without prior information regarding buyers' values, deterministic clock auctions cannot achieve bounded approximations, even for feasibility constraints comprising two maximal feasible sets. These negative results can be overcome by using a priori information or randomization. More precisely, the authors, 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.