A Universally Efficient Dynamic Auction for All Unimodular Demand Types

References

• [1] Andersson T , Svensson L (2016) Strategy-proof house allocation with price restrictions. J. Econom. Theory 163:167–177.Crossref, Google Scholar
• [2] Arrow K , Hahn F (1971) General Competitive Analysis (Holden-Day, San Francisco).Google Scholar
• [3] Aumann R (1964) Markets with a continuum of traders. Econometrica 32(1/2):39–50.Crossref, Google Scholar
• [4] Ausubel L (2004) An efficient ascending-bid auction for multiple objects. Amer. Econom. Rev. 94(5):1452–1475.Crossref, Google Scholar
• [5] Ausubel L (2006) An efficient dynamic auction for heterogeneous commodities. Amer. Econom. Rev. 96(3):602–629.Crossref, Google Scholar
• [6] Ausubel L , Cramton P (2004) Vickrey auctions with reserve pricing. Econom. Theory 23:493–505.Crossref, Google Scholar
• [7] Ausubel L , Milgrom P (2002) Ascending auctions with package bidding. B.E. J. Theor. Econom. 1(1):20011001.Crossref, Google Scholar
• [8] Ausubel L , Milgrom P (2005) The lovely but lonely Vickrey auction. Cramton P , Shoham Y , Steinberg R , eds. Combinatorial Auctions (MIT Press, Cambridge, MA), 57–95.Crossref, Google Scholar
• [9] Baldwin E , Klemperer P (2014) Tropical geometry to analyse demand. Working paper, Oxford University, Oxford, UK.Google Scholar
• [10] Baldwin E , Klemperer P (2019) Understanding preferences: “Demand types”, and the existence of equilibrium with indivisibilities. Econometrica 87(3):867–932.Crossref, Google Scholar
• [11] Baldwin E , Edhan O , Jagadeesan R , Klemperer P , Teytelboym A (2020) The equilibrium existence duality: Equilibrium with indivisibilities and income effects. Preprint, submitted June 30, https://arxiv.org/abs/2006.16939.Google Scholar
• [12] Bergemann D , Morris S (2007) An ascending auction for interdependent values: Uniqueness and robustness to strategic uncertainty. Amer. Econom. Rev. 97(2):125–130.Crossref, Google Scholar
• [13] Bikhchandani S , Mamer J (1997) Competitive equilibrium in an exchange economy with indivisibilities. J. Econom. Theory 74(2):385–413.Crossref, Google Scholar
• [14] Candogan O , Ozdaglar A , Parrilo P (2015) Iterative auction design for tree valuations. Oper. Res. 63(4):751–771.Link, Google Scholar
• [15] Clarke E (1971) Multipart pricing of public goods. Public Choice 11:17–33.Crossref, Google Scholar
• [16] Crawford V (2008) The flexible-salary match: A proposal to increase the salary flexibility of the national resident matching program. J. Econom. Behav. Organ. 66(2):149–160.Crossref, Google Scholar
• [17] Crawford V , Knoer E (1981) Job matching with heterogeneous firms and workers. Econometrica 49(2):437–450.Crossref, Google Scholar
• [18] Crémer J , Mclean R (1985) Optimal selling strategies under uncertainty for a discriminating monopolist when demands are interdependent. Econometrica 53(2):345–362.Crossref, Google Scholar
• [19] Danilov V , Koshevoy G , Murota K (2001) Discrete convexity and equilibria in economies with indivisible goods and money. Math. Soc. Sci. 41(3):251–273.Crossref, Google Scholar
• [20] Debreu G , Scarf H (1963) A limit theorem on the core of an economy. Internat. Econom. Rev. 4(3):235–246.Crossref, Google Scholar
• [21] Demange G , Gale D , Sotomayor M (1986) Multi-item auctions. J. Political Econom. 94(4):863–872.Crossref, Google Scholar
• [22] De Vries S , Schummer J , Vohra R (2007) On ascending Vickrey auctions for heterogeneous objects. J. Econom. Theory 132(1):95–118.Crossref, Google Scholar
• [23] Fudenberg D , Tirole J (1991) Game Theory (MIT Press, Cambridge, MA).Google Scholar
• [24] Fujishige S (2005) Submodular Functions and Optimization , 2nd ed. (Elsevier, Amsterdam).Google Scholar
• [25] Fujishige S , Yang Z (2003) A note on Kelso and Crawford’s gross substitutes condition. Math. Oper. Res. 28(3):463–469.Link, Google Scholar
• [26] Green J , Laffont JJ (1977) Characterization of satisfactory mechanisms for the revelation of preferences for public goods. Econometrica 45(2):427–438.Crossref, Google Scholar
• [27] Groves T (1973) Incentives in teams. Econometrica 41(4):617–631.Crossref, Google Scholar
• [28] Gul F , Stacchetti E (1999) Walrasian equilibrium with gross substitutes. J. Econom. Theory 87(1):95–124.Crossref, Google Scholar
• [29] Gul F , Stacchetti E (2000) The English auction with differentiated commodities. J. Econom. Theory 92(1):66–95.Crossref, Google Scholar
• [30] Hatfield J , Milgrom P (2005) Matching with contracts. Amer. Econom. Rev. 95(4):913–935.Crossref, Google Scholar
• [31] Hatfield J , Kominers S , Nichifor A , Ostrovsky M , Westkamp A (2013) Stability and competitive equilibrium in trading networks. J. Political Econom. 121(5):966–1005.Crossref, Google Scholar
• [32] Hayek F (1945) The use of knowledge in society. Amer. Econom. Rev. 35(4):519–530.Google Scholar
• [33] Holmström B (1979) Groves’ scheme on restricted domains. Econometrica 47(5):1137–1144.Crossref, Google Scholar
• [34] Hurwicz L (1973) The design of mechanisms for resource allocation. Amer. Econom. Rev. 63(2):1–39.Google Scholar
• [35] Jehiel P , Moldovanu B (2003) An economic perspective on auctions. Econom. Policy 18(36):269–308.Crossref, Google Scholar
• [36] Kelso A , Crawford V (1982) Job matching, coalition formation, and gross substitutes. Econometrica 50(6):1483–1504.Crossref, Google Scholar
• [37] Klemperer P (2008) A new auction for substitutes: Central bank liquidity auctions, the U.S. TARP, and variable product-mix auctions. Working paper, Oxford University, Oxford, UK.Google Scholar
• [38] 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
• [39] Klemperer P (2018) Product-mix auctions. Working paper, Oxford University, Oxford, UK.Google Scholar
• [40] Kojima F , Pathak P (2009) Incentives and stability in large two-sided matching markets. Amer. Econom. Rev. 99(3):608–627.Crossref, Google Scholar
• [41] Koopmans T , Beckmann M (1957) Assignment problems and the location of economic activities. Econometrica 25(1):53–76.Crossref, Google Scholar
• [42] Krishna V (2002) Auction Theory (Academic Press, Cambridge, MA).Google Scholar
• [43] Krishna V , Maenner E (2001) Convex potentials with an application to mechanism design. Econometrica 69(4):1113–1119.Crossref, Google Scholar
• [44] Lee J , Leyffer S (2012) Mixed Integer Nonlinear Programming (Springer, New York).Crossref, Google Scholar
• [45] Leonard H (1983) Elicitation of honest preferences for the assignment of individuals to positions. J. Political Econom. 91(3):1–36.Crossref, Google Scholar
• [46] Levin J (1997) An optimal auction for complements. Games Econom. Behav. 18(2):176–192.Crossref, Google Scholar
• [47] Ma J (1998) Competitive equilibrium with indivisibilities. J. Econom. Theory 82(2):458–468.Crossref, Google Scholar
• [48] Maskin E (2005) Recent contributions to mechanism design: A highly selective review. Working paper, Princeton University, Princeton, NJ.Google Scholar
• [49] McMillan J (1994) Selling spectrum rights. J. Econom. Perspect. 8(3):145–162. Crossref, Google Scholar
• [50] Milgrom P (2000) Putting auction theory to work: The simultaneous ascending auction. J. Political Econom. 108(2):245–272.Crossref, Google Scholar
• [51] Milgrom P (2004) Putting Auction Theory to Work (Cambridge University Press, Cambridge, UK).Crossref, Google Scholar
• [52] Milgrom P (2007) Package auctions and exchanges. Econometrica 75(4):935–965.Crossref, Google Scholar
• [53] Milgrom P (2017) Discovering Prices: Auction Design in Markets with Complex Constraints (Columbia University Press, New York).Crossref, Google Scholar
• [54] Milgrom P , Strulovici B (2009) Substitute goods, auctions, and equilibrium. J. Econom. Theory 144(1):212–247.Crossref, Google Scholar
• [55] Mishra D , Parkes D (2007) Ascending price Vickrey auction for general valuations. J. Econom. Theory 132(1):335–366.Crossref, Google Scholar
• [56] Murota K (2003) Discrete Convex Analysis (Society for Industrial and Applied Mathematics, Philadelphia).Crossref, Google Scholar
• [57] Murota K , Tamura A (2023) Note on Minkowski summation and unimodularity in discrete convex analysis. Preprint, submitted December 3, https://arxiv.org/abs/2312.01822.Google Scholar
• [58] Murota K , Shioura A , Yang Z (2016) Time bounds for iterative auctions: A unified approach by discrete convex analysis. Discrete Optim. 19(February):36–62.Crossref, Google Scholar
• [59] Myerson R (1981) Optimal auction design. Math. Oper. Res. 6(1):58–73.Link, Google Scholar
• [60] Myerson R , Satterthwaite M (1983) Efficient mechanisms and bilateral trading. J. Econom. Theory 29(2):265–281.Crossref, Google Scholar
• [61] Noussair C (2003) Innovations in the design of bundled-item auctions. Proc. Natl. Acad. Sci. USA 100(19):10590–10591.Crossref, Google Scholar
• [62] Perry M , Reny P (2005) An efficient multi-unit ascending auction. Rev. Econom. Stud. 72(2):567–592.Crossref, Google Scholar
• [63] Porter D , Rassenti S , Roopnarine A , Smith V (2003) Combinatorial auction design. Proc. Natl. Acad. Sci. USA 100(19):11153–11157.Crossref, Google Scholar
• [64] Rothkopf M (2007) Thirteen reasons why the Vickrey-Clarke-Groves process is not practical. Oper. Res. 55(2):191–197.Link, Google Scholar
• [65] Rothkopf M , Teisberg T , Kahn E (1990) Why are Vickrey auctions rare? J. Political Econom. 98(1):94–109.Crossref, Google Scholar
• [66] Shapley L , Shubik M (1971) The assignment game I: The core. Internat. J. Game Theory 1(1):111–130.Crossref, Google Scholar
• [67] 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
• [68] Shioura A , Yang Z (2015) Equilibrium, auction, generalized gross substitutes and complements. J. Oper. Res. Soc. Japan 58(4):410–415.Crossref, Google Scholar
• [69] Sun N , Yang Z (2002) The max-convolution approach to equilibrium analysis. Working Paper No. 341, Institute of Mathematical Economics, Bielefeld University, Bielefeld, Germany.Google Scholar
• [70] Sun N , Yang Z (2006) Equilibria and indivisibilities: Gross substitutes and complements. Econometrica 74(5):1385–1402.Crossref, Google Scholar
• [71] Sun N , Yang Z (2009) A double-track adjustment process for discrete markets with substitutes and complements. Econometrica 77(3):933–952.Crossref, Google Scholar
• [72] Sun Y , Yang Z (2014) An efficient and incentive compatible dynamic auction for multiple complements. J. Political Econom. 122(2):422–466.Crossref, Google Scholar
• [73] Tran N , Yu J (2019) Product-mix auctions and tropical geometry. Math. Oper. Res. 44(4):1396–1411.Link, Google Scholar
• [74] Varian H (1981) Dynamic systems with applications to economics. Arrow K , Intriligator M , eds. Handbook of Mathematical Economics , vol. 1 (North-Holland, Amsterdam), 93–110.Google Scholar
• [75] Vickrey W (1961) Counterspeculation, auctions, and competitive sealed tenders. J. Finance 16(1):8–37.Crossref, Google Scholar
• [76] Wilson R (1987) Game-theoretic analyses of trading processes. Bewley T , ed. Advances in Economic Theory: 5th World Congress (Cambridge University Press, Cambridge, UK), 33–70.Crossref, Google Scholar
• [77] Yang Z (2003) A competitive market model for indivisible commodities. Econom. Lett. 78(1):41–47.Crossref, Google Scholar