A Strongly Polynomial Algorithm for Linear Exchange Markets

References

• Adler I, Cosares S (1991) A strongly polynomial algorithm for a special class of linear programs. Oper. Res. 39(6):955–960.Link, Google Scholar
• Arrow KJ, Debreu G (1954) Existence of an equilibrium for a competitive economy. Econometrica 22(3):265–290.Crossref, Google Scholar
• Brainard W, Scarf H (2000) How to compute equilibrium prices in 1891. Cowles Foundation Discussion Paper 1270, Cowles Foundation, New Haven, CT.Google Scholar
• Codenotti B, Pemmaraju S, Varadarajan K (2004) The computation of market equilibria. ACM SIGACT News 35(4):23–37.Crossref, Google Scholar
• Cohen E, Megiddo N (1994) Improved algorithms for linear inequalities with two variables per inequality. SIAM J. Comput. 23(6):1313–1347.Crossref, Google Scholar
• Cornet B (1989) Linear exchange economies. Technical report, Cahier Eco-Math, Université de Paris, Paris.Google Scholar
• Cottle RW, Veinott AF (1972) Polyhedral sets having a least element. Math. Program. 3(1):238–249.Crossref, Google Scholar
• Darwish O, Mehlhorn K (2016) Improved balanced flow computation using parametric flow. Inform. Process. Lett. 116(9):560–563.Crossref, Google Scholar
• Devanur NR, Vazirani VV (2003) An improved approximation scheme for computing Arrow-Debreu prices for the linear case. Pandya PK, Radhakrishnan J, eds. FST TCS 2003 Foundation Software Tech. Theoret. Comput. Sci., Lecture Notes in Computer Science, vol. 2914 (Springer, Berlin), 149–155.Google Scholar
• Devanur NR, Garg J, Végh LA (2016) A rational convex program for linear Arrow-Debreu markets. ACM Trans. Econom. Comput. 5(1):6.Google Scholar
• Devanur NR, Papadimitriou CH, Saberi A, Vazirani VV (2008) Market equilibrium via a primal–dual algorithm for a convex program. J. ACM 55(5):22.Crossref, Google Scholar
• Duan R, Mehlhorn K (2015) A combinatorial polynomial algorithm for the linear Arrow–Debreu market. Inform. Comput. 243:112–132.Crossref, Google Scholar
• Duan R, Garg J, Mehlhorn K (2016) An improved combinatorial polynomial algorithm for the linear Arrow-Debreu market. Kraughgamer R, ed. SODA’16 Proc. 27th Annu. ACM-SIAM Sympos. Discrete Algorithms (Society for Industrial and Applied Mathematics, Philadelphia), 90–106.Google Scholar
• Eaves BC (1976) A finite algorithm for the linear exchange model. J. Math. Econom. 3:197–203.Crossref, Google Scholar
• Edmonds J (1967) Systems of distinct representatives and linear algebra. J. Res. National Bureau Standards B 71:241–245.Crossref, Google Scholar
• Eisenberg E, Gale D (1959) Consensus of subjective probabilities: The Pari-Mutuel method. Ann. Math. Statist. 30(1):165–168.Crossref, Google Scholar
• Gale D (1976) The linear exchange model. J. Math. Econom. 3(2):205–209.Crossref, Google Scholar
• Garg R, Kapoor S (2006) Auction algorithms for market equilibrium. Math. Oper. Res. 31(4):714–729.Link, Google Scholar
• Garg J, Végh LA (2019) A strongly polynomial algorithm for linear exchange markets. STOC 2019 Proc. 51st Annu. ACM SIGACT Sympos. Theory Comput. (Association for Computing Machinery, New York), 54–65.Google Scholar
• Garg J, Mehta R, Vazirani VV, Yazdanbod S (2017) Settling the complexity of Leontief and PLC exchange markets under exact and approximate equilibria. STOC 2017 Proc. 49th Annu. ACM SIGACT Sympos. Theory Comput. (Association for Computing Machinery, New York), 890–901.Google Scholar
• Ghiyasvand M, Orlin JB (2012) A simple approximation algorithm for computing Arrow-Debreu prices. Oper. Res. 60(5):1245–1248.Link, Google Scholar
• Goel G, Vazirani V (2011) A perfect price discrimination market model with production, and a rational convex program for it. Math. Oper. Res. 36(4):762–782.Link, Google Scholar
• Goldberg AV, Tarjan RE (1989) Finding minimum-cost circulations by canceling negative cycles. J. ACM. 36(4):873–886.Crossref, Google Scholar
• Grötschel M, Lovász L, Schrijver A (1988) Geometric Algorithms and Combinatorial Optimization, Algorithms and Combinatorics, vol. 2 (Springer Verlag, Berlin).Crossref, Google Scholar
• Hochbaum DS, Naor J (1994) Simple and fast algorithms for linear and integer programs with two variables per inequality. SIAM J. Comput. 23(6):1179–1192.Crossref, Google Scholar
• Jain K (2007) A polynomial time algorithm for computing an Arrow-Debreu market equilibrium for linear utilities. SIAM J. Comput. 37(1):303–318.Crossref, Google Scholar
• Jain K, Mahdian M, Saberi A (2003) Approximating market equilibria. Arora S, Jansen K, Rolim JDP, Sahai A, eds. RANDOM 2003 APPROX 2003 Approximation Randomization Combinatorial Optimization Algorithms Techniques, Lecture Notes in Computer Science, vol. 2764 (Springer, Berlin), 98–108.Google Scholar
• Kamiyama N (2019) A note on balanced flows in equality networks. Inform. Process. Lett. 145:74–76.Crossref, Google Scholar
• Lemke CE (1965) Bimatrix equilibrium points and mathematical programming. Management Sci. 11(7):681–689.Link, Google Scholar
• Megiddo N (1983) Toward a genuinely polynomial algorithm for linear programming. SIAM J. Comput. 12(2):347–353.Crossref, Google Scholar
• Nenakov EI, Primak ME (1983) One algorithm for finding solutions of the Arrow-Debreu model. Kibernetica 3:127–128.Google Scholar
• Olver N, Végh LA (2017) A simpler and faster strongly polynomial algorithm for generalized flow maximization. STOC 2017 Proc. 49th Annu. ACM SIGACT Sympos. Theory Comput. (Association for Computing Machinery, New York), 100–111.Google Scholar
• Orlin JB (1993) A faster strongly polynomial minimum cost flow algorithm. Oper. Res. 41(2):338–350.Link, Google Scholar
• Orlin JB (2010) Improved algorithms for computing Fisher’s market clearing prices. STOC’10 Proc. 42nd ACM Sympos. Theory Comput. (Association for Computing Machinery, New York), 291–300.Google Scholar
• Orlin JB (2013) Max flows in O(nm) time, or better. STOC’13 Proc. 45th Annu. ACM Sympos. Theory Comput. (Association for Computing Machinery, New York), 765–774.Google Scholar
• Shmyrev VI (2009) An algorithm for finding equilibrium in the linear exchange model with fixed budgets. J. Appl. Indust. Math. 3(4):505–518.Crossref, Google Scholar
• Tardos É (1985) A strongly polynomial minimum cost circulation algorithm. Combinatorica 5(3):247–255.Crossref, Google Scholar
• Tardos É (1986) A strongly polynomial algorithm to solve combinatorial linear programs. Oper. Res. 34(2):250–256.Link, Google Scholar
• Varian H (1974) Equity, envy and efficiency. J. Econom. Theory 29(2):217–244.Google Scholar
• Vavasis SA, Ye Y (1996) A primal-dual interior point method whose running time depends only on the constraint matrix. Math. Program. 74(1):79–120.Crossref, Google Scholar
• Vazirani V (2010) Spending constraint utilities with applications to the adwords market. Math. Oper. Res. 35(2):458–478.Link, Google Scholar
• Vazirani VV (2012) The notion of a rational convex program, and an algorithm for the Arrow-Debreu Nash bargaining game. J. ACM 59(2):7.Crossref, Google Scholar
• Végh LA (2013) Concave generalized flows with applications to market equilibria. Math. Oper. Res. 39(2):573–596.Link, Google Scholar
• Végh LA (2016) A strongly polynomial algorithm for a class of minimum-cost flow problems with separable convex objectives. SIAM J. Comput. 45(5):1729–1761.Crossref, Google Scholar
• Végh LA (2017) A strongly polynomial algorithm for generalized flow maximization. Math. Oper. Res. 42(2):179–211.Link, Google Scholar
• Walras L (1874) Eléments d’Economie Politique Pure, ou Théorie de la Richesse Sociale (in French). [English translation: Elements of Pure Economics; or, the Theory of Social Wealth] (American Economic Association and the Royal Economic Society, Corbaz & Cie, Lausanne).Google Scholar
• Ye Y (2005) A new complexity result on solving the Markov decision problem. Math. Oper. Res. 30(3):733–749.Link, Google Scholar
• Ye Y (2008) A path to the Arrow–Debreu competitive market equilibrium. Math. Program. 111(1–2):315–348.Crossref, Google Scholar
• Ye Y (2011) The simplex and policy-iteration methods are strongly polynomial for the Markov decision problem with a fixed discount rate. Math. Oper. Res. 36(4):593–603.Link, Google Scholar