Working Paper: CEPR ID: DP14976
Authors: Elizabeth Baldwin; Paul Goldberg; Paul Klemperer; Edwin Lock
Abstract: This paper develops algorithms to solve strong-substitutes product-mix auctions: it findscompetitive equilibrium prices and quantities for agents who use this auction’s biddinglanguage to truthfully express their strong-substitutes preferences over an arbitrary numberof goods, each of which is available in multiple discrete units. Our use of the biddinglanguage, and the information it provides, contrasts with existing algorithms that rely onaccess to a valuation or demand oracle.We compute market-clearing prices using algorithms that apply existing submodularminimisation methods. Allocating the supply among the bidders at these prices then requiressolving a novel constrained matching problem. Our algorithm iteratively simplifies theallocation problem, perturbing bids and prices in a way that resolves tie-breaking choicescreated by bids that can be accepted on more than one good. We provide practical runningtime bounds on both price-finding and allocation, and illustrate experimentally that ourallocation mechanism is practical.
Keywords: bidding language; product-mix auction; competitive equilibrium; Walrasian equilibrium; convex optimisation; strong substitutes; submodular minimisation
JEL Codes: D44
Edges that are evidenced by causal inference methods are in orange, and the rest are in light blue.
| Cause | Effect |
|---|---|
| algorithms (C60) | competitive equilibrium prices (D41) |
| algorithms (C60) | competitive equilibrium quantities (D41) |
| auction design (D44) | ability of bidders to express preferences effectively (D44) |
| ability of bidders to express preferences effectively (D44) | market equilibrium outcomes (D53) |
| algorithms (C60) | market-clearing prices (D41) |
| algorithms (C60) | market-clearing quantities (D41) |