Liquid price of anarchy

DOI10.1007/978-3-319-66700-3_1zbMATH Open1403.91157arXiv1511.01132OpenAlexW2964281423MaRDI QIDQ681835FDOQ681835

Authors: Yossi Azar, Michal Feldman, Alan Roytman, N. V. Gravin 

Publication date: 13 February 2018

Abstract: 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. Our main result is that the LPoA for mixed Nash equilibria is bounded by a constant when bidders are additive and items can be divided into sufficiently many discrete parts. Our proofs are robust, and can be extended to achieve similar bounds for simultaneous second price auctions as well as Bayesian Nash equilibria. For pure Nash equilibria, we establish tight bounds on the LPoA for the larger class of fractionally-subadditive valuations. To derive our results, we develop a new technique in which some bidders deviate (surprisingly) toward a non-optimal solution. In particular, this technique does not fit into the smoothness framework.

Full work available at URL: https://arxiv.org/abs/1511.01132

Recommendations

• Simple combinatorial auctions with budget constraints
• Liquid welfare maximization in auctions with multiple items
• Efficiency Guarantees in Auctions with Budgets
• A note on the efficiency of position mechanisms with budget constraints
• Simultaneous auctions are (almost) efficient

zbMATH Keywords

auctionssocial welfare functionpure Nash equilibrialiquid welfare objective function

Mathematics Subject Classification ID

Auctions, bargaining, bidding and selling, and other market models (91B26)

Cited In (7)

• Simple combinatorial auctions with budget constraints
• The Efficiency of Resource Allocation Mechanisms for Budget-Constrained Users
• Walrasian pricing in multi-unit auctions
• Autobidding with constraints
• Online random sampling for budgeted settings
• A note on the efficiency of position mechanisms with budget constraints
• Liquid welfare maximization in auctions with multiple items

This page was built for publication: Liquid price of anarchy

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q681835)