Solving Strong-Substitutes Product-Mix Auctions

References

• [1] Ausubel LM (2006) An efficient dynamic auction for heterogeneous commodities. Amer. Econom. Rev. 96(3):602–629.Crossref, Google Scholar
• [2] Baldwin E, Klemperer P (2019) Understanding preferences: “Demand types,” and the existence of equilibrium with indivisibilities. Econometrica 87(3):867–932.Crossref, Google Scholar
• [3] Baldwin E, Klemperer P (2021) Proof that the product-mix auction bidding language can represent any substitutes preferences. Working paper. Accessed December 31, 2021, https://www.nuffield.ox.ac.uk/economics/Papers/2021/2021-W05_subsproof.pdf.Google Scholar
• [4] Baldwin E, Goldberg PW, Klemperer P (2016) Tropical intersections and equilibrium (day 2 slides). Hausdorff School on Tropical Geometry and Economics. Accessed July 1, 2019, http://people.math.gatech.edu/~jyu67/HCM/Baldwin2.pdf.Google Scholar
• [5] Baldwin E, Bichler M, Fichtl M, Klemperer P (2022) Strong substitutes: Structural properties, and a new algorithm for competitive equilibrium prices. Math. Programming 1–33.Google Scholar
• [6] Chakrabarty D, Jain P, Kothari P (2014) Provable submodular minimization using Wolfe’s algorithm. Ghahramani Z, Welling M, Cortes C, Lawrence ND, Weinberger KQ, eds. Adv. Neural Inform. Processing Systems, vol. 802–809 (Curran Associates, Inc., Cambridge, MA).Google Scholar
• [7] Chakrabarty D, Lee YT, Sidford A, Wong SCW (2017) Subquadratic submodular function minimization. Proc. 49th Annual ACM SIGACT Sympos. Theory Comput. (ACM, New York), 1220–1231.Google Scholar
• [8] Danilov V, Koshevoy G, Murota K (2001) Discrete convexity and equilibria in economies with indivisible goods and money. Math. Social Sci. 41(3):251–273.Crossref, Google Scholar
• [9] Goldberg PW, Lock E, Marmolejo-Cossío F (2022) Learning strong substitutes demand via queries. ACM Trans. Econom. Comput. 10(2):1–22.Crossref, Google Scholar
• [10] Gul F, Stacchetti E (2000) The English auction with differentiated commodities. J. Econom. Theory 92(1):66–95.Crossref, Google Scholar
• [11] Iwata S (2008) Submodular function minimization. Math. Programming 112(1):45–64.Crossref, Google Scholar
• [12] Jiang H (2021) Minimizing convex functions with integral minimizers. Proc. 2021 ACM-SIAM Sympos. Discrete Algorithms (SIAM), 976–985.Google Scholar
• [13] Joswig M (2021) Essentials of Tropical Combinatorics, Graduate Studies in Mathematics, vol. 219 (American Mathematical Society, Providence, RI).Crossref, Google Scholar
• [14] Kelso AS, Crawford VP (1982) Job matching, coalition formation, and gross substitutes. Econometrica 50(6):1483–1504.Crossref, Google Scholar
• [15] Klemperer P (2008) A new auction for substitutes: Central bank liquidity auctions, the U.S. TARP, and variable product-mix auctions. Working paper, Nuffield College, Oxford, UK.Google Scholar
• [16] Klemperer P (2010) The product-mix auction: A new auction design for differentiated goods. J. Eur. Econom. Assoc. 8(2–3):526–536.Crossref, Google Scholar
• [17] Klemperer P (2018) Product-mix auctions. Working Paper 2018-W07, Nuffield College, Oxford, UK.Google Scholar
• [18] Lee YT, Sidford A, Wong SCW (2015) A faster cutting plane method and its implications for combinatorial and convex optimization. Proc. 2015 IEEE 56th Annual Sympos. Foundations Comput. Sci. (IEEE Computer Society, Washington, DC), 1049–1065.Google Scholar
• [19] Lin B, Tran NM (2017) Linear and rational factorization of tropical polynomials. Preprint, submitted July 11, https://arxiv.org/abs/1707.03332.Google Scholar
• [20] Maclagan D, Sturmfels B (2015) Introduction to Tropical Geometry, Graduate Studies in Mathematics, vol. 161 (American Mathematical Society, Providence, RI).Crossref, Google Scholar
• [21] Mas-Colell A, Whinston MD, Green JR (1995) Microeconomic Theory, vol. 1 (Oxford University Press, New York).Google Scholar
• [22] McCormick ST (2005) Submodular function minimization. Aardal K, Nemhauser G, Weismantel R, eds. Discrete Optimization, Handbooks in Operations Research and Management Science, vol. 12 (Elsevier, Amsterdam), 321–391.Crossref, Google Scholar
• [23] Mikhalkin G (2004) Decomposition into pairs-of-pants for complex algebraic hypersurfaces. Topology 43(5):1035–1065.Crossref, Google Scholar
• [24] Milgrom P, Strulovici B (2009) Substitute goods, auctions, and equilibrium. J. Econom. Theory 144(1):212–247.Crossref, Google Scholar
• [25] Murota K (2003) Discrete Convex Analysis, SIAM Monographs on Discrete Mathematics and Applications.Google Scholar
• [26] Murota K (2003) On steepest descent algorithms for discrete convex functions. SIAM J. Optim. 14(3):699–707.Crossref, Google Scholar
• [27] Murota K (2016) Discrete convex analysis: A tool for economics and game theory. J. Mechanism Inst. Design 1(1):151–273.Crossref, Google Scholar
• [28] Murota K, Shioura A (1999) M-convex function on generalized polymatroid. Math. Oper. Res. 24(1):95–105.Link, Google Scholar
• [29] Murota K, Shioura A (2014) Exact bounds for steepest descent algorithms of L-convex function minimization. Oper. Res. Lett. 42(5):361–366.Crossref, Google Scholar
• [30] Murota K, Tamura A (2001) Application of M-convex submodular flow problem to mathematical economics. Proc. 12th Internat. Sympos. Algorithms Comput. (Springer-Verlag, Berlin, Heidelberg), 14–25.Google Scholar
• [31] Murota K, Shioura A, Yang Z (2013) Computing a Walrasian equilibrium in iterative auctions with multiple differentiated items. Cai L, Cheng SW, Lam TW, eds. Algorithms and Computation (Springer, Berlin, Heidelberg), 468–478.Crossref, Google Scholar
• [32] Murota K, Shioura A, Yang Z (2016) Time bounds for iterative auctions: A unified approach by discrete convex analysis. Discrete Optim. 19:36–62.Crossref, Google Scholar
• [33] Paes Leme R (2017) Gross substitutability: An algorithmic survey. Games Econom. Behav. 106:294–316.Crossref, Google Scholar
• [34] Paes Leme R, Wong SCW (2017) Computing Walrasian equilibria: Fast algorithms and structural properties. Proc. 28th Annual ACM-SIAM Sympos. Discrete Algorithms (Society for Industrial and Applied Mathematics, Philadelphia), 632–651.Google Scholar
• [35] Schrijver A (1998) Theory of Linear and Integer Programming, Interscience Series in Discrete Mathematics and Optimisation (John Wiley & Sons).Google Scholar
• [36] Shioura A (1998) Minimization of an M-convex function. Discrete Appl. Math. 84(1):215–220.Crossref, Google Scholar
• [37] Shioura A (2017) Algorithms for L-convex function minimization: Connection between discrete convex analysis and other research fields. J. Oper. Res. Soc. Japan 60(3):216–243.Crossref, Google Scholar
• [38] Shioura A, Tamura A (2015) Gross substitutes condition and discrete concavity for multi-unit valuations: A survey. J. Oper. Res. Soc. Japan 58(1):61–103.Crossref, Google Scholar
• [39] Tarjan RE, van Leeuwen J (1984) Worst-case analysis of set union algorithms. J. ACM 31(2):245–281.Crossref, Google Scholar
• [40] van der Walt S, Colbert SC, Varoquaux G (2011) The NumPy array: A structure for efficient numerical computation. Comput. Sci. Engrg. 13(2):22–30.Crossref, Google Scholar