{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,11]],"date-time":"2026-05-11T11:10:34Z","timestamp":1778497834028,"version":"3.51.4"},"reference-count":29,"publisher":"Association for Computing Machinery (ACM)","issue":"5","license":[{"start":{"date-parts":[[2008,10,1]],"date-time":"2008-10-01T00:00:00Z","timestamp":1222819200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/100000143","name":"Division of Computing and Communication Foundations","doi-asserted-by":"publisher","award":["CCF-0546889CCF-0728640"],"award-info":[{"award-number":["CCF-0546889CCF-0728640"]}],"id":[{"id":"10.13039\/100000143","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["J. ACM"],"published-print":{"date-parts":[[2008,10]]},"abstract":"<jats:p>We give the first polynomial time algorithm for exactly computing an equilibrium for the linear utilities case of the market model defined by Fisher. Our algorithm uses the primal--dual paradigm in the enhanced setting of KKT conditions and convex programs. We pinpoint the added difficulty raised by this setting and the manner in which our algorithm circumvents it.<\/jats:p>","DOI":"10.1145\/1411509.1411512","type":"journal-article","created":{"date-parts":[[2008,11,6]],"date-time":"2008-11-06T13:49:43Z","timestamp":1225979383000},"page":"1-18","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":136,"title":["Market equilibrium via a primal--dual algorithm for a convex program"],"prefix":"10.1145","volume":"55","author":[{"given":"Nikhil R.","family":"Devanur","sequence":"first","affiliation":[{"name":"Georgia Institute of Technology, Atlanta, GA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Christos H.","family":"Papadimitriou","sequence":"additional","affiliation":[{"name":"University of California at Berkeley, Berkeley, California"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Amin","family":"Saberi","sequence":"additional","affiliation":[{"name":"Stanford University, Stanford, California"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Vijay V.","family":"Vazirani","sequence":"additional","affiliation":[{"name":"Georgia Institute of Technology, Atlanta, GA"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2008,11,5]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.2307\/1907353"},{"key":"e_1_2_1_2_1","unstructured":"Brainard W. C. and Scarf H. E. 2000. How to compute equilibrium prices in 1891. Cowles Foundation Discussion Paper 1270.  Brainard W. C. and Scarf H. E. 2000. How to compute equilibrium prices in 1891. Cowles Foundation Discussion Paper 1270."},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1007\/11944874_22"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/1054916.1054927"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/509907.509920"},{"key":"e_1_2_1_6_1","volume-title":"Proceedings of the 43rd Annual IEEE Symposium on Foundations of Computer Science. IEEE Computer Society Press","author":"Devanur N.","unstructured":"Devanur , N. , Papadimitriou , C. , Saberi , A. , and Vazirani , V. V . 2002. Market equilibrium via a primal-dual-type algorithm . In Proceedings of the 43rd Annual IEEE Symposium on Foundations of Computer Science. IEEE Computer Society Press , Los Alamitos, CA. Devanur, N., Papadimitriou, C., Saberi, A., and Vazirani, V. V. 2002. Market equilibrium via a primal-dual-type algorithm. In Proceedings of the 43rd Annual IEEE Symposium on Foundations of Computer Science. IEEE Computer Society Press, Los Alamitos, CA."},{"key":"e_1_2_1_7_1","volume-title":"Proceedings of 23rd FSTTCS.","author":"Devanur N. R.","unstructured":"Devanur , N. R. , and Vazirani , V. V . 2003. An improved approximation scheme for computing Arrow-Debreu prices for the linear case . In Proceedings of 23rd FSTTCS. Devanur, N. R., and Vazirani, V. V. 2003. An improved approximation scheme for computing Arrow-Debreu prices for the linear case. In Proceedings of 23rd FSTTCS."},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/1007352.1007431"},{"key":"e_1_2_1_9_1","first-page":"125","article-title":"Maximum matching and a polyhedron with 0,1-vertices. J. Res. NBS","volume":"69","author":"Edmonds J.","year":"1965","unstructured":"Edmonds , J. 1965 . Maximum matching and a polyhedron with 0,1-vertices. J. Res. NBS , Section B 69 , 125 -- 130 . Edmonds, J. 1965. Maximum matching and a polyhedron with 0,1-vertices. J. Res. NBS, Section B 69, 125--130.","journal-title":"Section B"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1214\/aoms\/1177706369"},{"key":"e_1_2_1_11_1","volume-title":"Theory of Linear Economic Models","author":"Gale D.","unstructured":"Gale , D. 1960. Theory of Linear Economic Models . McGraw Hill , New York . Gale, D. 1960. Theory of Linear Economic Models. McGraw Hill, New York."},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/1007352.1007430"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2004.6"},{"key":"e_1_2_1_14_1","volume-title":"Proceedings of the International Workshop on Approximation Algorithms for Combinatorial Optimization Problems.","author":"Jain K.","unstructured":"Jain , K. , Mahdian , M. , and Saberi , A . 2003. Approximating market equilibria . In Proceedings of the International Workshop on Approximation Algorithms for Combinatorial Optimization Problems. Jain, K., Mahdian, M., and Saberi, A. 2003. Approximating market equilibria. In Proceedings of the International Workshop on Approximation Algorithms for Combinatorial Optimization Problems."},{"key":"e_1_2_1_15_1","doi-asserted-by":"crossref","unstructured":"Jain K. and Vazirani V. V. 2008. Eisenberg-Gale markets: Algorithms and game-theoretic properties. Games Econ. Behav.  Jain K. and Vazirani V. V. 2008. Eisenberg-Gale markets: Algorithms and game-theoretic properties. Games Econ. Behav.","DOI":"10.1145\/1250790.1250845"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1002\/ett.4460080106"},{"key":"e_1_2_1_17_1","unstructured":"Kelly F. P. and Vazirani V. V. 2002. Rate control as a market equilibrium. Unpublished manuscript 2002. (Available at: http:\/\/www-static.cc.gatech.edu\/vazirani\/KV.pdf).  Kelly F. P. and Vazirani V. V. 2002. Rate control as a market equilibrium. Unpublished manuscript 2002. (Available at: http:\/\/www-static.cc.gatech.edu\/vazirani\/KV.pdf)."},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01585506"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(91)90200-L"},{"key":"e_1_2_1_20_1","volume-title":"Proceedings of the 3rd Workshop on Internet and Network Economics (WINE2007)","volume":"4858","author":"Meggido N.","unstructured":"Meggido , N. , and Vazirani , V. V . 2007. Continuity properties of equilibrium prices and allocations in linear Fisher markets . In Proceedings of the 3rd Workshop on Internet and Network Economics (WINE2007) . (San Diego, CA, Dec. 12--14). Lecture Notes in Computer Science , vol. 4858 , Springer-Verlag, New York, 362--367. Meggido, N., and Vazirani, V. V. 2007. Continuity properties of equilibrium prices and allocations in linear Fisher markets. In Proceedings of the 3rd Workshop on Internet and Network Economics (WINE2007). (San Diego, CA, Dec. 12--14). Lecture Notes in Computer Science, vol. 4858, Springer-Verlag, New York, 362--367."},{"key":"e_1_2_1_21_1","first-page":"127","article-title":"One algorithm for finding solutions of the Arrow-Debreu model","volume":"3","author":"Nenakov E. I.","year":"1983","unstructured":"Nenakov , E. I. , and Primak , M. E. 1983 . One algorithm for finding solutions of the Arrow-Debreu model . Kibernetica 3 , 127 -- 128 . Nenakov, E. I., and Primak, M. E. 1983. One algorithm for finding solutions of the Arrow-Debreu model. Kibernetica 3, 127--128.","journal-title":"Kibernetica"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1016\/0096-3003(92)90079-G"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0022-0000(05)80063-7"},{"key":"e_1_2_1_24_1","volume-title":"Cowles Foundation Monograph No. 24.","author":"Scarf H.","unstructured":"Scarf , H. 1973. The Computation of Economic Equilibria (with Collaboration of T. Hansen) . Cowles Foundation Monograph No. 24. , Yale University Press , New Haven, CI Scarf, H. 1973. The Computation of Economic Equilibria (with Collaboration of T. Hansen). Cowles Foundation Monograph No. 24., Yale University Press, New Haven, CI"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1287\/moor.1100.0450"},{"key":"e_1_2_1_26_1","volume-title":"Cambridge University Press","author":"Vazirani V. V.","unstructured":"Vazirani , V. V. 2007. Combinatorial algorithms for market equilibria . In Algorithmic Game Theory, N. Nisan, T. Roughgarden, E. Tardos, and V. V. Vazirani, Eds. Cambridge University Press , Cambridge , UK , 103--134. Vazirani, V. V. 2007. Combinatorial algorithms for market equilibria. In Algorithmic Game Theory, N. Nisan, T. Roughgarden, E. Tardos, and V. V. Vazirani, Eds. Cambridge University Press, Cambridge, UK, 103--134."},{"key":"e_1_2_1_27_1","unstructured":"Vazirani V. V. and Wang L. 2008. Continuity properties of equilibria in some Fisher and Arrow-Debreu market models. Available online at The Electronic Colloquium on Computational Complexity (ECCC) Report TR08-047.  Vazirani V. V. and Wang L. 2008. Continuity properties of equilibria in some Fisher and Arrow-Debreu market models. Available online at The Electronic Colloquium on Computational Complexity (ECCC) Report TR08-047."},{"key":"e_1_2_1_28_1","volume-title":"\u00c9l\u00e9ments d'\u00e9conomie politique pure ou th\u00e9orie de la richesse sociale (Elements of Pure Economics, or the theory of social wealth). Lausanne","author":"Walras L.","year":"1899","unstructured":"Walras , L. 1874. \u00c9l\u00e9ments d'\u00e9conomie politique pure ou th\u00e9orie de la richesse sociale (Elements of Pure Economics, or the theory of social wealth). Lausanne , Paris . ( 1899 , 4 th ed.; 1926, rev ed., 1954, Engl . transl.). Walras, L. 1874. \u00c9l\u00e9ments d'\u00e9conomie politique pure ou th\u00e9orie de la richesse sociale (Elements of Pure Economics, or the theory of social wealth). Lausanne, Paris. (1899, 4th ed.; 1926, rev ed., 1954, Engl. transl.).","edition":"4"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10107-006-0065-5"}],"container-title":["Journal of the ACM"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1411509.1411512","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1411509.1411512","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T13:29:29Z","timestamp":1750253369000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1411509.1411512"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2008,10]]},"references-count":29,"journal-issue":{"issue":"5","published-print":{"date-parts":[[2008,10]]}},"alternative-id":["10.1145\/1411509.1411512"],"URL":"https:\/\/doi.org\/10.1145\/1411509.1411512","relation":{},"ISSN":["0004-5411","1557-735X"],"issn-type":[{"value":"0004-5411","type":"print"},{"value":"1557-735X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2008,10]]},"assertion":[{"value":"2005-07-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2008-07-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2008-11-05","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}