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

Paul Klemperer, Elizabeth Baldwin, Martin Bichler and Maximilian Fichtl

No 15831, CEPR Discussion Papers from Centre for Economic Policy Research

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)
Date: 2021-02
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)
https://cepr.org/publications/DP15831 (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:cpr:ceprdp:15831

Ordering information: This working paper can be ordered from
https://cepr.org/publications/DP15831

Access Statistics for this paper

More papers in CEPR Discussion Papers from Centre for Economic Policy Research 33 Great Sutton Street, London EC1V 0DX, UK.
Bibliographic data for series maintained by CEPR ().