Limits of efficiency in sequential auctions

DOI10.1007/978-3-642-45046-4_14MaRDI QIDQ2937755zbMATH OpenOpenAlexFDO

Authors Michal Feldman, Brendan Lucier, Vasilis Syrgkanis

Publication date 12 January 2015

Published in Web and Internet Economics (Search for Journal in Brave)

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

zbMATH Keywords

capacitated valuationssequential auctionssubgame perfect equilibrium

Mathematics Subject Classification ID

Games in extensive form (91A18) Auctions, bargaining, bidding and selling, and other market models (91B26)

Abstract: 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. Another implication is that the inefficiency in sequential auctions is driven by the maximum number of items contained in any player's optimal set, and this is tight. 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. cite{PaesLeme2012}.

Recommendations

• Sequential auctions and externalities
• Simultaneous auctions are (almost) efficient
• Sequential auctions with multi-unit demands
• Simple combinatorial auctions with budget constraints
• Simultaneous auctions without complements are (almost) efficient

Cites work

• A Theory of Auctions and Competitive Bidding
• Auctions of heterogeneous objects
• Bayesian Combinatorial Auctions
• Combinatorial auctions
• Combinatorial auctions with decreasing marginal utilities
• Composable and efficient mechanisms
• Mechanism Design by Competing Sellers
• Sequential auctions and externalities
• Sequential auctions of endogenously valued objects
• Sequential auctions with multi-unit demands
• Simultaneous auctions are (almost) efficient
• Walrasian equilibrium with gross substitutes
• Welfare guarantees for combinatorial auctions with item bidding

Cited in

(6)

• Fraction auctions: the tradeoff between efficiency and running time
• The price of stability of envy-free equilibria in multi-buyer sequential auctions
• The price of anarchy of two-buyer sequential multiunit auctions
• Efficiency levels in sequential auctions with dynamic arrivals
• Limitations of Deterministic Auction Design for Correlated Bidders
• Sequential auctions and externalities

This page was built for publication: Limits of efficiency in sequential auctions

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