{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,1]],"date-time":"2026-05-01T00:41:43Z","timestamp":1777596103516,"version":"3.51.4"},"reference-count":63,"publisher":"Association for Computing Machinery (ACM)","issue":"3","license":[{"start":{"date-parts":[[2017,6,16]],"date-time":"2017-06-16T00:00:00Z","timestamp":1497571200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/100006474","name":"Columbia University","doi-asserted-by":"crossref","id":[{"id":"10.13039\/100006474","id-type":"DOI","asserted-by":"crossref"}]},{"DOI":"10.13039\/100000001","name":"NSF","doi-asserted-by":"publisher","award":["CCF-1149257, CCF-1320654 and CCF-1423100"],"award-info":[{"award-number":["CCF-1149257, CCF-1320654 and CCF-1423100"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"name":"Sloan research fellowship"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["J. ACM"],"published-print":{"date-parts":[[2017,6,30]]},"abstract":"<jats:p>We introduce the notion of non-monotone utilities, which covers a wide variety of utility functions in economic theory. We then prove that it is PPAD-hard to compute an approximate Arrow-Debreu market equilibrium in markets with linear and non-monotone utilities. Building on this result, we settle the long-standing open problem regarding the computation of an approximate Arrow-Debreu market equilibrium in markets with CES utility functions, by proving that it is PPAD-complete when the Constant Elasticity of Substitution parameter \u03c1 is any constant less than \u2212 1.<\/jats:p>","DOI":"10.1145\/3064810","type":"journal-article","created":{"date-parts":[[2017,6,16]],"date-time":"2017-06-16T18:10:59Z","timestamp":1497636659000},"page":"1-56","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":23,"title":["The Complexity of Non-Monotone Markets"],"prefix":"10.1145","volume":"64","author":[{"given":"Xi","family":"Chen","sequence":"first","affiliation":[{"name":"Columbia University, New York, NY"}]},{"given":"Dimitris","family":"Paparas","sequence":"additional","affiliation":[{"name":"University of Wisconsin-Madison, Madison, WI"}]},{"given":"Mihalis","family":"Yannakakis","sequence":"additional","affiliation":[{"name":"Columbia University, New York, NY"}]}],"member":"320","published-online":{"date-parts":[[2017,6,16]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.2307\/1907779"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.2307\/1927286"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.2307\/1907353"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"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\/1379759.1379761"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/1516512.1516516"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1007\/11944874_25"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-69733-6_18"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2007.53"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-10631-6_66"},{"key":"e_1_2_1_12_1","volume-title":"Proceedings of the 2nd Symposium on Innovations in Computer Science.","author":"Chen X.","year":"2011","unstructured":"X. Chen and S.-H. Teng . 2011 . A complexity view of markets with social influence . In Proceedings of the 2nd Symposium on Innovations in Computer Science. X. Chen and S.-H. Teng. 2011. A complexity view of markets with social influence. In Proceedings of the 2nd Symposium on Innovations in Computer Science."},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1007\/11590156_41"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/1060590.1060601"},{"key":"e_1_2_1_15_1","volume-title":"Proceedings of the 16th Annual ACM-SIAM Symposium on Discrete Algorithms. 72--81","author":"Codenotti B.","unstructured":"B. Codenotti , S. Pemmaraju , and K. Varadarajan . 2005c. On the polynomial time computation of equilibria for certain exchange economies . In Proceedings of the 16th Annual ACM-SIAM Symposium on Discrete Algorithms. 72--81 . B. Codenotti, S. Pemmaraju, and K. Varadarajan. 2005c. On the polynomial time computation of equilibria for certain exchange economies. In Proceedings of the 16th Annual ACM-SIAM Symposium on Discrete Algorithms. 72--81."},{"key":"e_1_2_1_16_1","volume-title":"Proceedings of the 17th Annual ACM-SIAM Symposium on Discrete Algorithms. 659--667","author":"Codenotti B.","unstructured":"B. Codenotti , A. Saberi , K. Varadarajan , and Y. Ye . 2006. Leontief economies encode nonzero sum two-player games . In Proceedings of the 17th Annual ACM-SIAM Symposium on Discrete Algorithms. 659--667 . B. Codenotti, A. Saberi, K. Varadarajan, and Y. Ye. 2006. Leontief economies encode nonzero sum two-player games. In Proceedings of the 17th Annual ACM-SIAM Symposium on Discrete Algorithms. 659--667."},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1137\/070699652"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511609893"},{"key":"e_1_2_1_19_1","volume-title":"Theory of Value","author":"Debreu G.","unstructured":"G. Debreu . 1959. Theory of Value . New York , Wiley . G. Debreu. 1959. Theory of Value. New York, Wiley."},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ipl.2008.07.011"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0022-0000(03)00011-4"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2008.30"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/1411509.1411512"},{"key":"e_1_2_1_24_1","volume-title":"Proceedings of the 23rd Conference on Foundations of Software Technology and Theoretical Computer Science. 149--155","author":"Devanur N. R.","unstructured":"N. R. Devanur and V. V. Vazirani . 2003. An improved approximation scheme for computing Arrow-Debreu prices for the linear case . In Proceedings of the 23rd Conference on Foundations of Software Technology and Theoretical Computer Science. 149--155 . N. R. Devanur and V. V. Vazirani. 2003. An improved approximation scheme for computing Arrow-Debreu prices for the linear case. In Proceedings of the 23rd Conference on Foundations of Software Technology and Theoretical Computer Science. 149--155."},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/1007352.1007431"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.2307\/2295874"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1007\/BFb0121035"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1214\/aoms\/1177706369"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511609411"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.5555\/1958033.1958052"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1016\/0304-4068(76)90029-X"},{"key":"e_1_2_1_32_1","unstructured":"J. Garg R. Mehta V. V. Vazirani and S. Yazdanbond. 2014. Leontief exchange markets can solve multivariate polynomial equations yielding FIXP and ETR hardness. (2014). arXiv:1411.5060.  J. Garg R. Mehta V. V. Vazirani and S. Yazdanbond. 2014. Leontief exchange markets can solve multivariate polynomial equations yielding FIXP and ETR hardness. (2014). arXiv:1411.5060."},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1145\/1007352.1007430"},{"key":"e_1_2_1_34_1","volume-title":"Proceedings of the 7th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems and 8th International Workshop on Randomization and Computation. 128--138","author":"Garg R.","unstructured":"R. Garg , S. Kapoor , and V. Vazirani . 2004. An auction-based market equilibrium algorithm for the separable gross substitutability case . In Proceedings of the 7th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems and 8th International Workshop on Randomization and Computation. 128--138 . R. Garg, S. Kapoor, and V. Vazirani. 2004. An auction-based market equilibrium algorithm for the separable gross substitutability case. In Proceedings of the 7th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems and 8th International Workshop on Randomization and Computation. 128--138."},{"key":"e_1_2_1_36_1","volume-title":"The Theory of Wages","author":"Hicks J. R.","unstructured":"J. R. Hicks . 1932. The Theory of Wages . MacMillan , London . J. R. Hicks. 1932. The Theory of Wages. MacMillan, London."},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1016\/0885-064X(89)90017-4"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.5555\/1776166.1776175"},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539705447384"},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1007\/11600930_79"},{"key":"e_1_2_1_41_1","volume-title":"Proceedings of the 6th International Workshop on Approximation Algorithms. 98--108","author":"Jain K.","unstructured":"K. Jain , M. Mahdian , and A. Saberi . 2003. Approximating market equilibria . In Proceedings of the 6th International Workshop on Approximation Algorithms. 98--108 . K. Jain, M. Mahdian, and A. Saberi. 2003. Approximating market equilibria. In Proceedings of the 6th International Workshop on Approximation Algorithms. 98--108."},{"key":"e_1_2_1_42_1","volume-title":"Proceedings of the 17th Annual ACM-SIAM Symposium on Discrete Algorithm. 688--697","author":"Jain K.","unstructured":"K. Jain and K. Varadarajan . 2006. Equilibria for economies with production: Constant-returns technologies and production planning constraints . In Proceedings of the 17th Annual ACM-SIAM Symposium on Discrete Algorithm. 688--697 . K. Jain and K. Varadarajan. 2006. Equilibria for economies with production: Constant-returns technologies and production planning constraints. In Proceedings of the 17th Annual ACM-SIAM Symposium on Discrete Algorithm. 688--697."},{"key":"e_1_2_1_43_1","volume-title":"Proceedings of the 16th Annual ACM-SIAM Symposium on Discrete Algorithms. 63--71","author":"Jain K.","unstructured":"K. Jain , V. V. Vazirani , and Y. Ye . 2005. Market equilibria for homothetic, quasi-concave utilities and economies of scale in production . In Proceedings of the 16th Annual ACM-SIAM Symposium on Discrete Algorithms. 63--71 . K. Jain, V. V. Vazirani, and Y. Ye. 2005. Market equilibria for homothetic, quasi-concave utilities and economies of scale in production. In Proceedings of the 16th Annual ACM-SIAM Symposium on Discrete Algorithms. 63--71."},{"key":"e_1_2_1_44_1","volume-title":"Equilibrium points in polymatrix games. Latvian Mathematical Collection","author":"Janovskaya E. B.","year":"1968","unstructured":"E. B. Janovskaya . 1968. Equilibrium points in polymatrix games. Latvian Mathematical Collection ( 1968 ). E. B. Janovskaya. 1968. Equilibrium points in polymatrix games. Latvian Mathematical Collection (1968)."},{"key":"e_1_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1215\/S0012-7094-41-00838-4"},{"key":"e_1_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.1073\/pnas.61.4.1238"},{"key":"e_1_2_1_47_1","unstructured":"A. Mas-Colell M. D. Whinston and J. R. Green. 1995. Microeconomic Theory. Oxford Press.  A. Mas-Colell M. D. Whinston and J. R. Green. 1995. Microeconomic Theory. Oxford Press."},{"key":"e_1_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.1016\/0304-4068(95)00763-6"},{"key":"e_1_2_1_49_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":"E. I. Nenakov and M. E. Primak . 1983 . One algorithm for finding solutions of the Arrow-Debreu model . Kibernetica 3 (1983), 127 -- 128 . E. I. Nenakov and M. E. Primak. 1983. One algorithm for finding solutions of the Arrow-Debreu model. Kibernetica 3 (1983), 127--128.","journal-title":"Kibernetica"},{"key":"e_1_2_1_50_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0022-0000(05)80063-7"},{"key":"e_1_2_1_51_1","doi-asserted-by":"publisher","DOI":"10.1145\/1993574.1993595"},{"key":"e_1_2_1_52_1","doi-asserted-by":"publisher","DOI":"10.1073\/pnas.0914728107"},{"key":"e_1_2_1_53_1","volume-title":"The Economics of Imperfect Competition. MacMillian","author":"Robinson J.","unstructured":"J. Robinson . 1933. The Economics of Imperfect Competition. MacMillian , London . J. Robinson. 1933. The Economics of Imperfect Competition. MacMillian, London."},{"key":"e_1_2_1_54_1","doi-asserted-by":"publisher","DOI":"10.1145\/2746539.2746578"},{"key":"e_1_2_1_55_1","doi-asserted-by":"publisher","DOI":"10.1023\/A:1008655831209"},{"key":"e_1_2_1_56_1","volume-title":"Foundations of Economic Analysis","author":"Samuelson P. A.","unstructured":"P. A. Samuelson . 1947. Foundations of Economic Analysis . Harvard University Press . P. A. Samuelson. 1947. Foundations of Economic Analysis. Harvard University Press."},{"key":"e_1_2_1_57_1","volume-title":"The Computation of Economic Equilibria","author":"Scarf H.","unstructured":"H. Scarf . 1973. The Computation of Economic Equilibria . Yale University Press . H. Scarf. 1973. The Computation of Economic Equilibria. Yale University Press."},{"key":"e_1_2_1_58_1","unstructured":"J. B. Shoven and J. Whalley. 1992. Applying General Equilibrium. Cambridge University Press.  J. B. Shoven and J. Whalley. 1992. Applying General Equilibrium. Cambridge University Press."},{"key":"e_1_2_1_59_1","doi-asserted-by":"publisher","DOI":"10.2307\/1884513"},{"key":"e_1_2_1_60_1","doi-asserted-by":"publisher","DOI":"10.1287\/moor.1100.0450"},{"key":"e_1_2_1_61_1","doi-asserted-by":"publisher","DOI":"10.1145\/1970392.1970394"},{"key":"e_1_2_1_62_1","unstructured":"L. Walras. 1874. Elements of Pure Economics or the Theory of Social Wealth. 1954 English Translation.  L. Walras. 1874. Elements of Pure Economics or the Theory of Social Wealth. 1954 English Translation."},{"key":"e_1_2_1_63_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2007.02.016"},{"key":"e_1_2_1_64_1","doi-asserted-by":"publisher","DOI":"10.5555\/3113602.3113800"}],"container-title":["Journal of the ACM"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3064810","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3064810","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3064810","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T03:36:40Z","timestamp":1750217800000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3064810"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017,6,16]]},"references-count":63,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2017,6,30]]}},"alternative-id":["10.1145\/3064810"],"URL":"https:\/\/doi.org\/10.1145\/3064810","relation":{},"ISSN":["0004-5411","1557-735X"],"issn-type":[{"value":"0004-5411","type":"print"},{"value":"1557-735X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2017,6,16]]},"assertion":[{"value":"2014-04-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2017-03-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2017-06-16","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}