Template-type: ReDIF-Paper 1.0
Author-Name: Elizabeth Baldwin
Author-Workplace-Name: Dept of Economics, Oxford University
Author-Name: Martin Bichler
Author-Workplace-Name: Dept of Computer Science, Technical University of Munich
Author-Name: Maximilian Fichtl
Author-Workplace-Name: Dept of Computer Science, Technical University of Munich
Author-Name: Paul Klemperer
Author-Workplace-Name: Dept of Economics, Oxford University
Author-Email:  paul.klemperer@nuffield.ox.ac.uk
Title: Strong Substitutes: Structural Properties, and a New Algorithm for Competitive Equilibrium Prices
Abstract: We show the Strong Substitutes Product-Mix Auction (SSPMA) 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.
Keywords: Competitive equilibrium, Walrasian equilibrium, Strong substitutes, Product-Mix auction, Envy-free prices, Indivisible goods, Equilibrium computation, DC programming, Auction
theory, Algorithms
Length: 27 pages
Creation-Date: 2021-02-08
Number: 2021-W02
File-URL: http://www.nuffield.ox.ac.uk/economics/Papers/2021/2021W02_submission.pdf
File-Format: application/pdf
Handle: RePEc:nuf:econwp:2102