Strong Substitutes: Structural Properties, and a New Algorithm for Competitive Equilibrium Prices

Elizabeth Baldwin, Martin Bichler, Maximilian Fichtl and Paul Klemperer
Additional contact information
Martin Bichler: Dept of Computer Science, Technical University of Munich
Maximilian Fichtl: Dept of Computer Science, Technical University of Munich

No 2021-W02, Economics Papers from Economics Group, Nuffield College, University of Oxford

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 (search for similar items in EconPapers)
Pages: 27 pages
Date: 2021-02-08
New Economics Papers: this item is included in nep-com and nep-des
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://www.nuffield.ox.ac.uk/economics/Papers/2021/2021W02_submission.pdf (application/pdf)

Related works:
Working Paper: Strong Substitutes: Structural Properties, and a New Algorithm for Competitive Equilibrium Prices (2021)
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:nuf:econwp:2102

Access Statistics for this paper

More papers in Economics Papers from Economics Group, Nuffield College, University of Oxford Contact information at EDIRC.
Bibliographic data for series maintained by Maxine Collett ().