Solving Strong-Substitutes Product-Mix Auctions
Elizabeth Baldwin (),
Paul Klemperer () and
No 14976, CEPR Discussion Papers from C.E.P.R. Discussion Papers
This paper develops algorithms to solve strong-substitutes product-mix auctions: it finds competitive equilibrium prices and quantities for agents who use this auction's bidding language to truthfully express their strong-substitutes preferences over an arbitrary number of goods, each of which is available in multiple discrete units. Our use of the bidding language, and the information it provides, contrasts with existing algorithms that rely on access to a valuation or demand oracle. We compute market-clearing prices using algorithms that apply existing submodular minimisation methods. Allocating the supply among the bidders at these prices then requires solving a novel constrained matching problem. Our algorithm iteratively simplifies the allocation problem, perturbing bids and prices in a way that resolves tie-breaking choices created by bids that can be accepted on more than one good. We provide practical running time bounds on both price-finding and allocation, and illustrate experimentally that our allocation mechanism is practical.
Keywords: bidding language; Competitive Equilibrium; convex optimisation; product-mix auction; strong substitutes; submodular minimisation; Walrasian Equilibrium (search for similar items in EconPapers)
JEL-codes: D44 (search for similar items in EconPapers)
References: Add references at CitEc
Citations: Track citations by RSS feed
Downloads: (external link)
CEPR Discussion Papers are free to download for our researchers, subscribers and members. If you fall into one of these categories but have trouble downloading our papers, please contact us at firstname.lastname@example.org
Working Paper: Solving Strong-Substitutes Product-Mix Auctions (2019)
This item may be available elsewhere in EconPapers: Search for items with the same title.
Export reference: BibTeX
RIS (EndNote, ProCite, RefMan)
Persistent link: https://EconPapers.repec.org/RePEc:cpr:ceprdp:14976
Ordering information: This working paper can be ordered from
http://www.cepr.org/ ... rs/dp.php?dpno=14976
Access Statistics for this paper
More papers in CEPR Discussion Papers from C.E.P.R. Discussion Papers Centre for Economic Policy Research, 33 Great Sutton Street, London EC1V 0DX.
Bibliographic data for series maintained by ().