Bayesian and Randomized Clock Auctions

Michal Feldman, Vasilis Gkatzelis, Nick Gravin, Daniel Schoepflin

פרסום מחקרי: פרק בספר / בדוח / בכנספרסום בספר כנסביקורת עמיתים


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, and some feasibility constraint restricts which subsets of buyers can be served simultaneously. Recent work in economics introduced (deferred-acceptance) clock auctions as a superior class of auctions for this problem, due to their transparency, simplicity, and very strong incentive guarantees. Subsequent work in computer science focused on evaluating these auctions with respect to their social welfare approximation guarantees, leading to strong impossibility results: in the absence of prior information regarding the buyers' values, no deterministic clock auction can achieve a bounded approximation, even for simple feasibility constraints with only two maximal feasible sets. We show that these negative results can be circumvented either by using access to prior information or by leveraging randomization. In particular, we provide clock auctions that give a O(log log k) approximation for general downward-closed feasibility constraints with k maximal feasible sets, for three different information models, ranging from full access to the value distributions to complete absence of information. The more information the seller has, the simpler and more practical these auctions are. Under full access, we use a particularly simple deterministic clock auction, called a single-price clock auction, which is only slightly more complex than posted price mechanisms. In this auction, each buyer is offered a single price, then a feasible set is selected among those who accept their offers. In the other extreme, where no prior information is available, this approximation guarantee is obtained using a complex randomized clock auction. In addition to our main results, we propose a parameterization that interpolates between single-price clock auctions and general clock auctions, paving the way for an exciting line of future research.

שפה מקוריתאנגלית
כותר פרסום המארחEC 2022 - Proceedings of the 23rd ACM Conference on Economics and Computation
מספר עמודים26
מסת"ב (אלקטרוני)9781450391504
מזהי עצם דיגיטלי (DOIs)
סטטוס פרסוםפורסם - 12 יולי 2022
אירוע23rd ACM Conference on Economics and Computation, EC 2022 - Boulder, ארצות הברית
משך הזמן: 11 יולי 202215 יולי 2022

סדרות פרסומים

שםEC 2022 - Proceedings of the 23rd ACM Conference on Economics and Computation


כנס23rd ACM Conference on Economics and Computation, EC 2022
מדינה/אזורארצות הברית

ASJC Scopus subject areas

  • ???subjectarea.asjc.1700.1701???
  • ???subjectarea.asjc.2000.2002???
  • ???subjectarea.asjc.2600.2605???
  • ???subjectarea.asjc.2600.2613???

טביעת אצבע

להלן מוצגים תחומי המחקר של הפרסום 'Bayesian and Randomized Clock Auctions'. יחד הם יוצרים טביעת אצבע ייחודית.

פורמט ציטוט ביבליוגרפי