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

Elizabeth Baldwin, Martin Bichler, Maximilian Fichtl, Paul Klemperer

Research output: Contribution to journalArticlepeer-review

Abstract

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.

Original languageEnglish
Pages (from-to)611-643
Number of pages33
JournalMathematical Programming
Volume203
Issue number1-2
DOIs
StatePublished - Jan 2024

Keywords

  • 91-08
  • Algorithms
  • Auction theory
  • Competitive equilibrium
  • DC programming
  • Envy-free prices
  • Equilibrium computation
  • Indivisible goods
  • Product-Mix auction
  • Strong substitutes
  • Walrasian equilibrium
  • product mix auction

Fingerprint

Dive into the research topics of 'Strong substitutes: structural properties, and a new algorithm for competitive equilibrium prices'. Together they form a unique fingerprint.

Cite this