Working Paper: CEPR ID: DP15831
Authors: Elizabeth Baldwin; Martin Bichler; Maximilian Fichtl; Paul Klemperer
Abstract: We show the Strong Substitutes Product-Mix Auction (SSPMA) bidding language providesan intuitive and geometric interpretation of strong substitutes as Minkowski differences between setsthat are easy to identify.We prove that competitive equilibrium prices for agents with strong substitutespreferences can be computed by minimizing the difference between two linear programs for the positiveand the negative bids with suitably relaxed resource constraints. This also leads to a new algorithmfor computing competitive equilibrium prices which is competitive with standard steepest descentalgorithms in extensive experiments.
Keywords: competitive equilibrium; Walrasian equilibrium; strong substitutes; product-mix auction; envy-free prices; indivisible goods; equilibrium computation; DC programming; auction theory; algorithms
JEL Codes: No JEL codes provided
Edges that are evidenced by causal inference methods are in orange, and the rest are in light blue.
| Cause | Effect |
|---|---|
| minimization of the difference between two linear programs (C61) | competitive equilibrium prices (D41) |
| strong substitutes property (D10) | existence of competitive equilibrium prices (D41) |
| structure of the strong substitutes product-mix auction (SSPMA) (D44) | ability to compute competitive equilibrium prices efficiently (D41) |
| new algorithm based on DC programming (C61) | efficiency in computing equilibrium prices (D41) |