Citation

Discussion Paper Details

Please find the details for DP15831 in an easy to copy and paste format below:

Full Details   |   Bibliographic Reference

Full Details

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

Author(s): Elizabeth Baldwin, Martin Bichler, Maximilian Fichtl and Paul Klemperer

Publication Date: February 2021

Keyword(s): Algorithms, Auction Theory, Competitive Equilibrium, DC programming, Envy-free prices, Equilibrium computation, indivisible goods, product-mix auction, strong substitutes and Walrasian Equilibrium

Programme Area(s): Financial Economics and Industrial Organization

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.

For full details and related downloads, please visit: https://cepr.org/active/publications/discussion_papers/dp.php?dpno=15831

Bibliographic Reference

Baldwin, E, Bichler, M, Fichtl, M and Klemperer, P. 2021. 'Strong Substitutes: Structural Properties, and a New Algorithm for Competitive Equilibrium Prices'. London, Centre for Economic Policy Research. https://cepr.org/active/publications/discussion_papers/dp.php?dpno=15831