Solving Strong-Substitutes Product-Mix Auctions

Elizabeth Baldwin, Paul W. Goldberg (), Paul Klemperer and Edwin Lock ()
Additional contact information
Paul W. Goldberg: Dept. of Computer Science, Oxford University
Edwin Lock: Dept. of Computer Science, Oxford University

No 2019-W08, Economics Papers from Economics Group, Nuffield College, University of Oxford

Abstract: 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; product-mix auction; competitive equilibrium; Walrasian equilibrium; convex optimisation; strong substitutes; submodular minimisation (search for similar items in EconPapers)
Pages: 38 pages
Date: 2019-10-06
New Economics Papers: this item is included in nep-com, nep-des, nep-gth and nep-mic
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (3)

Downloads: (external link)
https://www.nuffield.ox.ac.uk/economics/Papers/2019/2019W08_paper-arxiv.pdf (application/pdf)

Related works:
Working Paper: Solving Strong-Substitutes Product-Mix Auctions (2020)
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:nuf:econwp:1908

Access Statistics for this paper

More papers in Economics Papers from Economics Group, Nuffield College, University of Oxford Contact information at EDIRC.
Bibliographic data for series maintained by Maxine Collett ().