Template-type: ReDIF-Paper 1.0
Author-Name: Elizabeth Baldwin
Author-Workplace-Name: Dept. of Economics, Oxford University
Author-Email: elizabeth.baldwin@economics.o x.ac.uk
Author-Name: Paul W. Goldberg
Author-Workplace-Name: Dept. of Computer Science, Oxford University
Author-Email: paul.goldberg@cs.ox.ac.uk
Author-Name: Paul Klemperer
Author-Workplace-Name: Dept. of Economics, Oxford University
Author-Email: paul.klemperer@nuffield.ox.ac.uk
Author-Name: Edwin Lock
Author-Workplace-Name: Dept. of Computer Science, Oxford University
Author-Email: edwin.lock@cs.ox.ac.uk
Title: Solving Strong-Substitutes Product-Mix Auctions
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
Length: 38 pages
Creation-Date: 2019-10-06
Number: 2019-W08
File-URL: https://www.nuffield.ox.ac.uk/economics/Papers/2019/2019W08_paper-arxiv.pdf
File-Format: application/pdf
Handle: RePEc:nuf:econwp:1908