{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T04:48:48Z","timestamp":1750308528108,"version":"3.41.0"},"reference-count":38,"publisher":"Association for Computing Machinery (ACM)","issue":"3","license":[{"start":{"date-parts":[[2016,5,13]],"date-time":"2016-05-13T00:00:00Z","timestamp":1463097600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"NSF","award":["CCF 1451574"],"award-info":[{"award-number":["CCF 1451574"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Algorithms"],"published-print":{"date-parts":[[2016,6,15]]},"abstract":"<jats:p>\n            We give a new mathematical formulation of market equilibria in exchange economies using an\n            <jats:italic>indirect utility function<\/jats:italic>\n            : the function of prices and income that gives the maximum utility achievable. The formulation is a\n            <jats:italic>convex<\/jats:italic>\n            program and can be solved when the indirect utility function is convex in prices. We illustrate that many economies, including:\n          <\/jats:p>\n          <jats:p>\u2014Homogeneous utilities of degree \u03b1 \u2208 [0, 1] in Fisher economies\u2014this includes Linear, Leontief, Cobb-Douglas<\/jats:p>\n          <jats:p>\n            \u2014\n            <jats:italic>Resource allocation utilities<\/jats:italic>\n            like multi-commodity flows\n          <\/jats:p>\n          <jats:p>satisfy this condition and can be efficiently solved.<\/jats:p>\n          <jats:p>\n            Further, we give a natural t\u00e2tonnement type price-adjusting algorithm in these economies. Our algorithm, which is applicable to a larger class of utility functions than previously known\n            <jats:italic>weak gross substitutes<\/jats:italic>\n            , mimics the natural dynamics for the markets as suggested by Walras: it iteratively adjusts a good\u2019s price upward when the demand for that good under current prices exceeds its supply; and downward when its supply exceeds its demand. The algorithm computes an approximate equilibrium in a number of iterations that is independent of the number of traders and is almost\n            <jats:italic>linear<\/jats:italic>\n            in the number of goods.\n          <\/jats:p>","DOI":"10.1145\/2905372","type":"journal-article","created":{"date-parts":[[2016,5,16]],"date-time":"2016-05-16T12:27:17Z","timestamp":1463401637000},"page":"1-15","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":2,"title":["A Simple and Efficient Algorithm for Computing Market Equilibria"],"prefix":"10.1145","volume":"12","author":[{"given":"Lisa","family":"Fleischer","sequence":"first","affiliation":[{"name":"Dartmouth College, NH, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Rahul","family":"Garg","sequence":"additional","affiliation":[{"name":"IBM Thomas J. Watson Research Center"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Sanjiv","family":"Kapoor","sequence":"additional","affiliation":[{"name":"Illinois Institute of Technology, IL, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Rohit","family":"Khandekar","sequence":"additional","affiliation":[{"name":"IBM Thomas J. Watson Research Center"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Amin","family":"Saberi","sequence":"additional","affiliation":[{"name":"Stanford University, CA, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2016,5,13]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.4086\/toc.2012.v008a006"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.2307\/1907779"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.2307\/1907353"},{"key":"e_1_2_1_4_1","volume-title":"Proceedings of the 12th Annual European Symposium. Springer","author":"Chen Ning","year":"2004","unstructured":"Ning Chen , Xiaotie Deng , Xiaoming Sun , and Andrew Chi-Chih Yao . 2004 . Proceedings of the 12th Annual European Symposium. Springer , Berlin, 169--179. DOI:http:\/\/dx.doi.org\/10.1007\/978-3-540-30140-0_17 10.1007\/978-3-540-30140-0_17 Ning Chen, Xiaotie Deng, Xiaoming Sun, and Andrew Chi-Chih Yao. 2004. Proceedings of the 12th Annual European Symposium. Springer, Berlin, 169--179. DOI:http:\/\/dx.doi.org\/10.1007\/978-3-540-30140-0_17"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2009.29"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/1227161.1402295"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1007\/11561071_10"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/1060590.1060601"},{"volume-title":"Computation of market equilibria by convex programming","author":"Codenotti Bruno","key":"e_1_2_1_9_1","unstructured":"Bruno Codenotti and Kasturi Varadarajan . 2007. Computation of market equilibria by convex programming . In Algorithmic Game Theory, N. Nisan, T. Roughgarden, E. Tardos, and V. V. Vazirani (Eds.). Cambridge University Press , 135--158. Bruno Codenotti and Kasturi Varadarajan. 2007. Computation of market equilibria by convex programming. In Algorithmic Game Theory, N. Nisan, T. Roughgarden, E. Tardos, and V. V. Vazirani (Eds.). Cambridge University Press, 135--158."},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/1374376.1374422"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/509907.509920"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/1566374.1566384"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2008.30"},{"volume-title":"Proceedings of the 43rd Symposium on Foundations of Computer Science (FOCS\u201902)","author":"Devanur Nikhil R.","key":"e_1_2_1_14_1","unstructured":"Nikhil R. Devanur , Christos H. Papadimitriou , Amin Saberi , and Vijay V. Vazirani . 2002. Market equilibrium via a primal-dual-type algorithm . In Proceedings of the 43rd Symposium on Foundations of Computer Science (FOCS\u201902) . IEEE, 389--395. Nikhil R. Devanur, Christos H. Papadimitriou, Amin Saberi, and Vijay V. Vazirani. 2002. Market equilibrium via a primal-dual-type algorithm. In Proceedings of the 43rd Symposium on Foundations of Computer Science (FOCS\u201902). IEEE, 389--395."},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-92185-1_11"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0895480199355754"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539704446232"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1287\/moor.1060.0216"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1007\/11944874_21"},{"key":"e_1_2_1_20_1","volume-title":"Proceedings of the 7th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems (APPROX\u201904)","author":"Garg Rahul","year":"2004","unstructured":"Rahul Garg , Sanjiv Kapoor , and Vijay Vazirani . 2004 . An auction-based market equilbrium algorithm for the separable gross substitutibility case . In Proceedings of the 7th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems (APPROX\u201904) . Springer, 128--138. Rahul Garg, Sanjiv Kapoor, and Vijay Vazirani. 2004. An auction-based market equilbrium algorithm for the separable gross substitutibility case. In Proceedings of the 7th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems (APPROX\u201904). Springer, 128--138."},{"volume-title":"Geometric Algorithms and Combinatorial Optimization","author":"Gr\u00f6tschel Martin","key":"e_1_2_1_21_1","unstructured":"Martin Gr\u00f6tschel , L\u00e1szl\u00f3 Lov\u00e1sz , and Alexander Schrijver . 1988. Geometric Algorithms and Combinatorial Optimization . Springer-Verlag , Berlin . Martin Gr\u00f6tschel, L\u00e1szl\u00f3 Lov\u00e1sz, and Alexander Schrijver. 1988. Geometric Algorithms and Combinatorial Optimization. Springer-Verlag, Berlin."},{"key":"e_1_2_1_22_1","doi-asserted-by":"crossref","unstructured":"Kamal Jain Mohammad Mahdian and Amin Saberi. 2003. Approximating market equilibrium. In Proceedings of the 6th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems APPROX 2003 and 7th International Workshop on Randomization and Approximation Techniques in Computer Science. Springer Berlin 98--108.  Kamal Jain Mohammad Mahdian and Amin Saberi. 2003. Approximating market equilibrium. In Proceedings of the 6th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems APPROX 2003 and 7th International Workshop on Randomization and Approximation Techniques in Computer Science. Springer Berlin 98--108.","DOI":"10.1007\/978-3-540-45198-3_9"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/1250790.1250845"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1002\/ett.4460080106"},{"volume-title":"The Theory of General Economic Equilibrium: A Differential Approach","author":"Mas-Colell Andrew","key":"e_1_2_1_26_1","unstructured":"Andrew Mas-Colell . 1985. The Theory of General Economic Equilibrium: A Differential Approach . Cambridge University Press , Cambridge . Andrew Mas-Colell. 1985. The Theory of General Economic Equilibrium: A Differential Approach. Cambridge University Press, Cambridge."},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/1284320.1284321"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.2307\/1907623"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.2307\/1909319"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.2307\/2525408"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.5555\/3219302.3219303"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1111\/1468-0262.00141"},{"volume-title":"Foundations of Economic Analysis","author":"Samuelson Paul A.","key":"e_1_2_1_33_1","unstructured":"Paul A. Samuelson . 1947. Foundations of Economic Analysis . Harward University Press , Cambridge, MA . Paul A. Samuelson. 1947. Foundations of Economic Analysis. Harward University Press, Cambridge, MA."},{"volume-title":"Microeconomic Analysis","author":"Varian Hal R.","key":"e_1_2_1_34_1","unstructured":"Hal R. Varian . 1992. Microeconomic Analysis . W. W. Norton , New York . Hal R. Varian. 1992. Microeconomic Analysis. W. W. Norton, New York."},{"volume-title":"Combinatorial algorithms for market equilibria","author":"Vazirani Vijay V.","key":"e_1_2_1_35_1","unstructured":"Vijay V. Vazirani . 2007. Combinatorial algorithms for market equilibria . In Algorithmic Game Theory, N. Nisan, T. Roughgarden, E. Tardos, and V. V. Vazirani (Eds.). Cambridge University Press. Vijay V. Vazirani. 2007. Combinatorial algorithms for market equilibria. In Algorithmic Game Theory, N. Nisan, T. Roughgarden, E. Tardos, and V. V. Vazirani (Eds.). Cambridge University Press."},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1145\/1970392.1970394"},{"volume-title":"Elements of Pure Economics, or the Theory of Social Wealth (in French)","author":"Walras Leon","key":"e_1_2_1_37_1","unstructured":"Leon Walras . 1874. Elements of Pure Economics, or the Theory of Social Wealth (in French) . Lausanne , Paris . Leon Walras. 1874. Elements of Pure Economics, or the Theory of Social Wealth (in French). Lausanne, Paris."},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1145\/1250790.1250844"},{"key":"e_1_2_1_39_1","first-page":"1","article-title":"A path to the arrow--debreu competitive market equilibrium","volume":"111","author":"Ye Yinyu","year":"2008","unstructured":"Yinyu Ye . 2008 . A path to the arrow--debreu competitive market equilibrium . Mathematical Programming 111 , 1 -- 2 (2008), 315--348. Yinyu Ye. 2008. A path to the arrow--debreu competitive market equilibrium. Mathematical Programming 111, 1--2 (2008), 315--348.","journal-title":"Mathematical Programming"}],"container-title":["ACM Transactions on Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2905372","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2905372","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T18:55:49Z","timestamp":1750272949000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2905372"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016,5,13]]},"references-count":38,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2016,6,15]]}},"alternative-id":["10.1145\/2905372"],"URL":"https:\/\/doi.org\/10.1145\/2905372","relation":{},"ISSN":["1549-6325","1549-6333"],"issn-type":[{"type":"print","value":"1549-6325"},{"type":"electronic","value":"1549-6333"}],"subject":[],"published":{"date-parts":[[2016,5,13]]},"assertion":[{"value":"2010-03-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2015-12-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2016-05-13","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}