Back to Search Start Over

Solving Strong-Substitutes Product-Mix Auctions.

Authors :
Baldwin, Elizabeth
Goldberg, Paul W.
Klemperer, Paul
Lock, Edwin
Source :
Mathematics of Operations Research; Aug2024, Vol. 49 Issue 3, p1502-1534, 33p
Publication Year :
2024

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 minimization 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. Funding: E. Baldwin and P. Klemperer were supported by the Economic and Social Research Council [Grant ES/L003058/1]. P. W. Goldberg and E. Lock were supported by a JP Morgan faculty fellowship during the work on the final version of the paper. Supplemental Material: The online companion is available at https://doi.org/10.1287/moor.2019.0248. [ABSTRACT FROM AUTHOR]

Details

Language :
English
ISSN :
0364765X
Volume :
49
Issue :
3
Database :
Complementary Index
Journal :
Mathematics of Operations Research
Publication Type :
Academic Journal
Accession number :
179020542
Full Text :
https://doi.org/10.1287/moor.2019.0248