Strong substitutes: structural properties, and a new algorithm for competitive equilibrium prices

• 成果类型: Article
• 署名作者: Baldwin, Elizabeth; Bichler, Martin; Fichtl, Maximilian; Klemperer, Paul
• 署名单位: University of Oxford; University of Oxford; Technical University of Munich; University of Oxford; University of Oxford
• 刊物名称: MATHEMATICAL PROGRAMMING
• ISSN/ISSBN: 0025-5610
• DOI: 10.1007/s10107-022-01792-w
• 发表日期: 2024
• 页码: 611-643
• 关键词: Nonconvex optimization; convex-functions; gross; difference; auction; models; GOODS

摘要

We show the strong substitutes product-mix auction 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.