{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,10]],"date-time":"2026-06-10T07:56:38Z","timestamp":1781078198474,"version":"3.54.1"},"reference-count":28,"publisher":"Association for Computing Machinery (ACM)","issue":"3","license":[{"start":{"date-parts":[[2011,5,1]],"date-time":"2011-05-01T00:00:00Z","timestamp":1304208000000},"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-0728640CCF-0914732CCF-0728736CCF-1017955"],"award-info":[{"award-number":["CCF-0728640CCF-0914732CCF-0728736CCF-1017955"]}],"id":[{"id":"10.13039\/100000143","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000006","name":"Office of Naval Research","doi-asserted-by":"publisher","award":["N000140910755"],"award-info":[{"award-number":["N000140910755"]}],"id":[{"id":"10.13039\/100000006","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["J. ACM"],"published-print":{"date-parts":[[2011,5]]},"abstract":"<jats:p>\n            We consider Fisher and Arrow--Debreu markets under additively separable, piecewise-linear, concave utility functions and obtain the following results. For both market models, if an equilibrium exists, there is one that is rational and can be written using polynomially many bits. There is no simple necessary and sufficient condition for the existence of an equilibrium: The problem of checking for existence of an equilibrium is NP-complete for both market models; the same holds for existence of an \u03b5-approximate equilibrium, for \u03b5 =\n            <jats:italic>O<\/jats:italic>\n            (\n            <jats:italic>n<\/jats:italic>\n            <jats:sup>\u22125<\/jats:sup>\n            ). Under standard (mild) sufficient conditions, the problem of finding an exact equilibrium is in PPAD for both market models. Finally, building on the techniques of Chen et al. [2009a] we prove that under these sufficient conditions, finding an equilibrium for Fisher markets is PPAD-hard.\n          <\/jats:p>","DOI":"10.1145\/1970392.1970394","type":"journal-article","created":{"date-parts":[[2011,6,6]],"date-time":"2011-06-06T11:51:38Z","timestamp":1307361098000},"page":"1-25","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":75,"title":["Market equilibrium under separable, piecewise-linear, concave utilities"],"prefix":"10.1145","volume":"58","author":[{"given":"Vijay V.","family":"Vazirani","sequence":"first","affiliation":[{"name":"Georgia Institute of Technology, Atlanta, GA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Mihalis","family":"Yannakakis","sequence":"additional","affiliation":[{"name":"Columbia University, New York, NY"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2011,6,9]]},"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.1109\/FOCS.2009.29"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/1516512.1516516"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-10631-6_66"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.5555\/1109557.1109629"},{"key":"e_1_2_1_7_1","volume-title":"Proceedings of the Conference on Automation Languages and Programming (ICALP).","author":"Codenotti B.","unstructured":"Codenotti , B. , and Varadarajan , K . 2004. Efficient computation of equilibrium prices for markets with Leontief utilities . In Proceedings of the Conference on Automation Languages and Programming (ICALP). Codenotti, B., and Varadarajan, K. 2004. Efficient computation of equilibrium prices for markets with Leontief utilities. In Proceedings of the Conference on Automation Languages and Programming (ICALP)."},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1137\/070699652"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ipl.2008.07.011"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2008.30"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/1411509.1411512"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1016\/0304-4068(76)90028-8"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1137\/080720826"},{"key":"e_1_2_1_14_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_15_1","doi-asserted-by":"publisher","DOI":"10.1016\/0304-4068(76)90029-X"},{"key":"e_1_2_1_16_1","unstructured":"Garey M. R. and Johnson D. S. 1979. Computer and Intractability: A Guide to the Theory of NP-Completeness. Freeman.   Garey M. R. and Johnson D. S. 1979. Computer and Intractability: A Guide to the Theory of NP-Completeness. Freeman."},{"key":"e_1_2_1_17_1","volume-title":"Proceedings of the 3rd International Symposium on Algorithmic Game Theory (SAGT). 186--197","author":"Goel G.","unstructured":"Goel , G. , and Vazirani , V. V . 2010. A perfect price discrimination market model with production and a (rational) convex program for it . In Proceedings of the 3rd International Symposium on Algorithmic Game Theory (SAGT). 186--197 . Goel, G., and Vazirani, V. V. 2010. A perfect price discrimination market model with production and a (rational) convex program for it. In Proceedings of the 3rd International Symposium on Algorithmic Game Theory (SAGT). 186--197."},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.5555\/1776166.1776175"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539705447384"},{"key":"e_1_2_1_20_1","doi-asserted-by":"crossref","unstructured":"Lemke C. and Howson J. 1964. Equilibrium points of bimatrix games. J. SIAM 413--423.  Lemke C. and Howson J. 1964. Equilibrium points of bimatrix games. J. SIAM 413--423.","DOI":"10.1137\/0112033"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1016\/0304-4068(95)00763-6"},{"key":"e_1_2_1_22_1","unstructured":"Megiddo N. 1988. A note on the complexity of P-matrix LCP and computing an equilibrium. IBM Res. rep. 6439. http:\/\/theory.stanford.edu\/~megiddo\/pdf\/plcp.pdf.  Megiddo N. 1988. A note on the complexity of P-matrix LCP and computing an equilibrium. IBM Res. rep. 6439. http:\/\/theory.stanford.edu\/~megiddo\/pdf\/plcp.pdf."},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(91)90200-L"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0022-0000(05)80063-7"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1137\/0115116"},{"key":"e_1_2_1_26_1","volume-title":"The Computation of Economic Equilibria","author":"Scarf H.","unstructured":"Scarf , H. 1973. The Computation of Economic Equilibria . Yale University Press . Scarf, H. 1973. The Computation of Economic Equilibria. Yale University Press."},{"key":"e_1_2_1_27_1","first-page":"59","article-title":"Walras' existence theorem and Brower's fixpoint theorem","volume":"13","author":"Uzawa H.","year":"1962","unstructured":"Uzawa , H. 1962 . Walras' existence theorem and Brower's fixpoint theorem . Econ. Stud. Quart. 13 , 59 -- 62 . Uzawa, H. 1962. Walras' existence theorem and Brower's fixpoint theorem. Econ. Stud. Quart. 13, 59--62.","journal-title":"Econ. Stud. Quart."},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2007.02.016"}],"container-title":["Journal of the ACM"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1970392.1970394","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1970392.1970394","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T10:52:53Z","timestamp":1750243973000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1970392.1970394"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2011,5]]},"references-count":28,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2011,5]]}},"alternative-id":["10.1145\/1970392.1970394"],"URL":"https:\/\/doi.org\/10.1145\/1970392.1970394","relation":{},"ISSN":["0004-5411","1557-735X"],"issn-type":[{"value":"0004-5411","type":"print"},{"value":"1557-735X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2011,5]]},"assertion":[{"value":"2009-12-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2011-02-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2011-06-09","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}