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
מזהי עצם דיגיטלי (DOIs)
סטטוס פרסוםפורסם - 2017
אירוע10th International Symposium on Algorithmic Game Theory, SAGT 2017 - L’Aquila, איטליה
משך הזמן: 12 ספט׳ 201714 ספט׳ 2017

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

שםLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
כרך10504 LNCS

כנס

כנס10th International Symposium on Algorithmic Game Theory, SAGT 2017
מדינה/אזוראיטליה
עירL’Aquila
תקופה12/09/1714/09/17

ASJC Scopus subject areas

  • ???subjectarea.asjc.2600.2614???
  • ???subjectarea.asjc.1700.1700???

טביעת אצבע

להלן מוצגים תחומי המחקר של הפרסום 'Liquid price of anarchy'. יחד הם יוצרים טביעת אצבע ייחודית.

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