TY - GEN

T1 - Liquid price of anarchy

AU - Azar, Yossi

AU - Feldman, Michal

AU - Gravin, Nick

AU - Roytman, Alan

N1 - Publisher Copyright: © Springer International Publishing AG 2017.

PY - 2017

Y1 - 2017

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=85029368707&partnerID=8YFLogxK

U2 - https://doi.org/10.1007/978-3-319-66700-3_1

DO - https://doi.org/10.1007/978-3-319-66700-3_1

M3 - منشور من مؤتمر

SN - 9783319666990

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 3

EP - 15

BT - Algorithmic Game Theory - 10th International Symposium, SAGT 2017, Proceedings

A2 - Bilo, Vittorio

A2 - Flammini, Michele

T2 - 10th International Symposium on Algorithmic Game Theory, SAGT 2017

Y2 - 12 September 2017 through 14 September 2017

ER -