Strong substitutes: structural properties, and a new algorithm for competitive equilibrium prices
- Resource Type
- Original Paper
- Authors
- Baldwin, Elizabeth; Bichler, Martin; Fichtl, Maximilian; Klemperer, Paul
- Source
- Mathematical Programming: A Publication of the Mathematical Optimization Society. 203(1-2):611-643
- Subject
- Competitive equilibrium
Walrasian equilibrium
Strong substitutes
Product-Mix auction
Envy-free prices
Indivisible goods
Equilibrium computation
DC programming
Auction theory
Algorithms
product mix auction
91-08
- Language
- English
- ISSN
- 0025-5610
1436-4646
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.