Citation

Discussion Paper Details

Please find the details for DP14976 in an easy to copy and paste format below:

Full Details

Title: Solving Strong-Substitutes Product-Mix Auctions

Author(s): Elizabeth Baldwin, Paul Goldberg, Paul Klemperer and Edwin Lock

Publication Date: June 2020

Keyword(s): bidding language, Competitive Equilibrium, convex optimisation, product-mix auction, strong substitutes, submodular minimisation and Walrasian Equilibrium

Programme Area(s): Financial Economics and Industrial Organization

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.

For full details and related downloads, please visit: https://cepr.org/active/publications/discussion_papers/dp.php?dpno=14976

Bibliographic Reference

Baldwin, E, Goldberg, P, Klemperer, P and Lock, E. 2020. 'Solving Strong-Substitutes Product-Mix Auctions'. London, Centre for Economic Policy Research. https://cepr.org/active/publications/discussion_papers/dp.php?dpno=14976