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 C.E.P.R. Discussion Papers

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)
CEPR Discussion Papers are free to download for our researchers, subscribers and members. If you fall into one of these categories but have trouble downloading our papers, please contact us at subscribers@cepr.org

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 C.E.P.R. Discussion Papers Centre for Economic Policy Research, 33 Great Sutton Street, London EC1V 0DX.
Bibliographic data for series maintained by ().