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
المعرِّفات الرقمية للأشياء
حالة النشرنُشِر - 12 يوليو 2022
الحدث23rd ACM Conference on Economics and Computation, EC 2022 - Boulder, الولايات المتّحدة
المدة: ١١ يوليو ٢٠٢٢١٥ يوليو ٢٠٢٢

سلسلة المنشورات

الاسمEC 2022 - Proceedings of the 23rd ACM Conference on Economics and Computation


!!Conference23rd ACM Conference on Economics and Computation, EC 2022
الدولة/الإقليمالولايات المتّحدة

All Science Journal Classification (ASJC) codes

  • !!Computer Science (miscellaneous)
  • !!Economics and Econometrics
  • !!Computational Mathematics
  • !!Statistics and Probability


أدرس بدقة موضوعات البحث “Bayesian and Randomized Clock Auctions'. فهما يشكلان معًا بصمة فريدة.

قم بذكر هذا