Strong substitutes: structural properties, and a new algorithm for competitive equilibrium prices

We show the strong substitutes product-mix auction bidding language provides an intuitive and geometric interpretation of strong substitutes as Minkowski differences between sets that are easy to identify. We prove that competitive equilibrium prices for agents with strong substitutes preferences ca...

Full description

Saved in:
Bibliographic Details
Published in:Mathematical programming 2024-01, Vol.203 (1-2), p.611-643
Main Authors: Baldwin, Elizabeth, Bichler, Martin, Fichtl, Maximilian, Klemperer, Paul
Format: Article
Language:English
Subjects:
Algorithms
Calculus of Variations and Optimal Control
Optimization
Combinatorics
Competition (Economics)
Computer science
Full Length Paper
Mathematical and Computational Physics
Mathematical Methods in Physics
Mathematics
Mathematics and Statistics
Mathematics of Computing
Numerical Analysis
Substitutes
Theoretical
Valuation
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:We show the strong substitutes product-mix auction bidding language provides an intuitive and geometric interpretation of strong substitutes as Minkowski differences between sets that are easy to identify. We prove that competitive equilibrium prices for agents with strong substitutes preferences can be computed by minimizing the difference between two linear programs for the positive and the negative bids with suitably relaxed resource constraints. This also leads to a new algorithm for computing competitive equilibrium prices which is competitive with standard steepest descent algorithms in extensive experiments.
ISSN:0025-5610
1436-4646
DOI:10.1007/s10107-022-01792-w