Liquid price of anarchy

Yossi Azar, Michal Feldman, Nick Gravin, Alan Roytman

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

ملخص

Incorporating budget constraints into the analysis of auctions has become increasingly important, as they model practical settings more accurately. The social welfare function, which is the standard measure of efficiency in auctions, is inadequate for settings with budgets, since there may be a large disconnect between the value a bidder derives from obtaining an item and what can be liquidated from her. The Liquid Welfare objective function has been suggested as a natural alternative for settings with budgets. Simple auctions, like simultaneous item auctions, are evaluated by their performance at equilibrium using the Price of Anarchy (PoA) measure – the ratio of the objective function value of the optimal outcome to the worst equilibrium. Accordingly, we evaluate the performance of simultaneous item auctions in budgeted settings by the Liquid Price of Anarchy (LPoA) measure – the ratio of the optimal Liquid Welfare to the Liquid Welfare obtained in the worst equilibrium. For pure Nash equilibria of simultaneous first price auctions, we obtain a bound of 2 on the LPoA for additive buyers. Our results easily extend to the larger class of fractionally-subadditive valuations. Next we show that the LPoA of mixed Nash equilibria for first price auctions with additive bidders is bounded by a constant. Our proofs are robust, and can be extended to achieve similar bounds for Bayesian Nash equilibria. To derive our results, we develop a new technique in which some bidders deviate (surprisingly) toward a non-optimal solution. In particular, this technique goes beyond the smoothness-based approach.

اللغة الأصليةالإنجليزيّة
عنوان منشور المضيفAlgorithmic Game Theory - 10th International Symposium, SAGT 2017, Proceedings
المحررونVittorio Bilo, Michele Flammini
الصفحات3-15
عدد الصفحات13
المعرِّفات الرقمية للأشياء
حالة النشرنُشِر - 2017
الحدث10th International Symposium on Algorithmic Game Theory, SAGT 2017 - L’Aquila, إيطاليا
المدة: ١٢ سبتمبر ٢٠١٧١٤ سبتمبر ٢٠١٧

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

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

!!Conference

!!Conference10th International Symposium on Algorithmic Game Theory, SAGT 2017
الدولة/الإقليمإيطاليا
المدينةL’Aquila
المدة١٢/٠٩/١٧١٤/٠٩/١٧

All Science Journal Classification (ASJC) codes

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

بصمة

أدرس بدقة موضوعات البحث “Liquid price of anarchy'. فهما يشكلان معًا بصمة فريدة.

قم بذكر هذا