Limits of efficiency in sequential auctions

Michal Feldman, Brendan Lucier, Vasilis Syrgkanis

نتاج البحث: فصل من :كتاب / تقرير / مؤتمرمنشور من مؤتمرمراجعة النظراء

ملخص

We study the efficiency of sequential first-price item auctions at (subgame perfect) equilibrium. This auction format has recently attracted much attention, with previous work establishing positive results for unit-demand valuations and negative results for submodular valuations. This leaves a large gap in our understanding between these valuation classes. In this work we resolve this gap on the negative side. In particular, we show that even in the very restricted case in which each bidder has either an additive valuation or a unit-demand valuation, there exist instances in which the inefficiency at equilibrium grows linearly with the minimum of the number of items and the number of bidders. Moreover, these inefficient equilibria persist even under iterated elimination of weakly dominated strategies. Our main result implies linear inefficiency for many natural settings, including auctions with gross substitute valuations, capacitated valuations, budget-additive valuations, and additive valuations with hard budget constraints on the payments. For capacitated valuations, our results imply a lower bound that equals the maximum capacity of any bidder, which is tight following the upper-bound technique established by Paes Leme et al. [20].

اللغة الأصليةالإنجليزيّة
عنوان منشور المضيفWeb and Internet Economics - 9th International Conference, WINE 2013, Proceedings
الصفحات160-173
عدد الصفحات14
المعرِّفات الرقمية للأشياء
حالة النشرنُشِر - 2013
منشور خارجيًانعم
الحدث9th International Conference on Web and Internet Economics, WINE 2013 - Cambridge, MA, الولايات المتّحدة
المدة: ١١ ديسمبر ٢٠١٣١٤ ديسمبر ٢٠١٣

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

الاسمLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
مستوى الصوت8289 LNCS

!!Conference

!!Conference9th International Conference on Web and Internet Economics, WINE 2013
الدولة/الإقليمالولايات المتّحدة
المدينةCambridge, MA
المدة١١/١٢/١٣١٤/١٢/١٣

All Science Journal Classification (ASJC) codes

  • !!Theoretical Computer Science
  • !!General Computer Science

بصمة

أدرس بدقة موضوعات البحث “Limits of efficiency in sequential auctions'. فهما يشكلان معًا بصمة فريدة.

قم بذكر هذا