{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,17]],"date-time":"2026-03-17T07:02:50Z","timestamp":1773730970379,"version":"3.50.1"},"reference-count":53,"publisher":"Association for Computing Machinery (ACM)","issue":"3","license":[{"start":{"date-parts":[[2019,6,7]],"date-time":"2019-06-07T00:00:00Z","timestamp":1559865600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"NSF CRII","award":["1755619"],"award-info":[{"award-number":["1755619"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Algorithms"],"published-print":{"date-parts":[[2019,7,31]]},"abstract":"<jats:p>We design a simple ascending-price algorithm to compute a (1 + \u03b5)-approximate equilibrium in Arrow-Debreu markets with weak gross substitute property. It applies to an unknown market setting without exact knowledge about the number of agents, their individual utilities, and endowments. Instead, our algorithm only uses price queries to a global demand oracle. This is the first polynomial-time algorithm for most of the known tractable classes of Arrow-Debreu markets, which computes such an equilibrium with a number of calls to the demand oracle that is polynomial in log 1\/\u03b5 and avoids heavy machinery such as the ellipsoid method.<\/jats:p>\n          <jats:p>Demands can be real-valued functions of prices, but the oracles only return demand values of bounded precision. Due to this more realistic assumption, precision and representation of prices and demands become a major technical challenge, and we develop new tools and insights that may be of independent interest. Furthermore, we give the first polynomial-time algorithm to compute an exact equilibrium for markets with spending constraint utilities. This resolves an open problem posed by Duan and Mehlhorn.<\/jats:p>","DOI":"10.1145\/3319394","type":"journal-article","created":{"date-parts":[[2019,6,10]],"date-time":"2019-06-10T12:10:51Z","timestamp":1560168651000},"page":"1-33","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":9,"title":["Ascending-Price Algorithms for Unknown Markets"],"prefix":"10.1145","volume":"15","author":[{"given":"Xiaohui","family":"Bei","sequence":"first","affiliation":[{"name":"Nanyang Technological University, Singapore"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Jugal","family":"Garg","sequence":"additional","affiliation":[{"name":"University of Illinois at Urbana-Champaign, Urbana, IL, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Martin","family":"Hoefer","sequence":"additional","affiliation":[{"name":"Goethe University Frankfurt, Germany"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2019,6,7]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.5555\/3174304.3175452"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.2307\/1907353"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.2307\/1907515"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/2940716.2940765"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-66700-3_6"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/1993574.1993594"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0531(78)90063-7"},{"key":"e_1_2_1_8_1","volume-title":"How to Compute Equilibrium Prices","author":"Brainard William","year":"1891","unstructured":"William Brainard and Herbert Scarf . 2000. How to Compute Equilibrium Prices in 1891 . Discussion Paper 1270. Cowles Foundation . William Brainard and Herbert Scarf. 2000. How to Compute Equilibrium Prices in 1891. Discussion Paper 1270. Cowles Foundation."},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2009.29"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/3064810"},{"key":"e_1_2_1_11_1","unstructured":"Yun Kuen Cheung and Richard Cole. 2016. A unified approach to analyzing asynchronous coordinate descent and tatonnement. arXiv:1612.09171.  Yun Kuen Cheung and Richard Cole. 2016. A unified approach to analyzing asynchronous coordinate descent and tatonnement. arXiv:1612.09171."},{"key":"e_1_2_1_12_1","volume-title":"Proceedings of the 45th Symposium on Theory of Computing (STOC\u201913)","author":"Cheung Yun Kuen","year":"2013","unstructured":"Yun Kuen Cheung , Richard Cole , and Nikhil Devanur . 2013 . Tatonnement beyond gross substitutes? Gradient descent to the rescue . In Proceedings of the 45th Symposium on Theory of Computing (STOC\u201913) . 191--200. Yun Kuen Cheung, Richard Cole, and Nikhil Devanur. 2013. Tatonnement beyond gross substitutes? Gradient descent to the rescue. In Proceedings of the 45th Symposium on Theory of Computing (STOC\u201913). 191--200."},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/2229012.2229039"},{"key":"e_1_2_1_14_1","volume-title":"Proceedings of the 25th Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS\u201905)","author":"Codenotti Bruno","unstructured":"Bruno Codenotti , Benton McCune , Sriram Penumatcha , and Kasturi R. Varadarajan . 2005. Market equilibrium for CES exchange economies: Existence, multiplicity, and computation . In Proceedings of the 25th Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS\u201905) . 505--516. Bruno Codenotti, Benton McCune, Sriram Penumatcha, and Kasturi R. Varadarajan. 2005. Market equilibrium for CES exchange economies: Existence, multiplicity, and computation. In Proceedings of the 25th Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS\u201905). 505--516."},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/1060590.1060601"},{"key":"e_1_2_1_16_1","volume-title":"Proceedings of the 16th Symposium on Discrete Algorithms (SODA\u201905)","author":"Codenotti Bruno","year":"2005","unstructured":"Bruno Codenotti , Sriram Pemmaraju , and Kasturi Varadarajan . 2005 . On the polynomial time computation of equilibria for certain exchange economies . In Proceedings of the 16th Symposium on Discrete Algorithms (SODA\u201905) . 72--81. Bruno Codenotti, Sriram Pemmaraju, and Kasturi Varadarajan. 2005. On the polynomial time computation of equilibria for certain exchange economies. In Proceedings of the 16th Symposium on Discrete Algorithms (SODA\u201905). 72--81."},{"key":"e_1_2_1_17_1","volume-title":"Algorithmic Game Theory, N. Nisan, \u00c9","author":"Codenotti Bruno","unstructured":"Bruno Codenotti and Kasturi Varadarajan . 2007. Computation of market equilibria by convex programming . In Algorithmic Game Theory, N. Nisan, \u00c9 . Tardos, T. Roughgarden, and V. Vazirani (Eds.). Cambridge University Press , New York, NY , 135--158. Bruno Codenotti and Kasturi Varadarajan. 2007. Computation of market equilibria by convex programming. In Algorithmic Game Theory, N. Nisan, \u00c9. Tardos, T. Roughgarden, and V. Vazirani (Eds.). Cambridge University Press, New York, NY, 135--158."},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/3033274.3085109"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/1374376.1374422"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/2746539.2746589"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/2930658"},{"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","doi-asserted-by":"publisher","DOI":"10.1145\/1007352.1007431"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.5555\/2884435.2884442"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ic.2014.12.009"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1016\/0304-4068(76)90028-8"},{"key":"e_1_2_1_28_1","volume-title":"Economic Equilibrium: Model Formulation and Solution. Mathematical Programming Studies","author":"Eaves B. Curtis","unstructured":"B. Curtis Eaves . 1985. Finite solution of pure trade markets with Cobb-Douglas utilities . In Economic Equilibrium: Model Formulation and Solution. Mathematical Programming Studies , Vol. 23 . Springer , 226--239. B. Curtis Eaves. 1985. Finite solution of pure trade markets with Cobb-Douglas utilities. In Economic Equilibrium: Model Formulation and Solution. Mathematical Programming Studies, Vol. 23. Springer, 226--239."},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1287\/mnsc.7.4.337"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1214\/aoms\/1177706369"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1145\/2905372"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.5555\/3174304.3175455"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1137\/140971002"},{"key":"e_1_2_1_34_1","volume-title":"Proceedings of the 24th Symposium on Discrete Algorithms (SODA\u201913)","author":"Garg Jugal","unstructured":"Jugal Garg , Ruta Mehta , Milind A. Sohoni , and Nisheeth K. Vishnoi . 2013. Towards polynomial simplex-like algorithms for market equilibria . In Proceedings of the 24th Symposium on Discrete Algorithms (SODA\u201913) . 1226--1242. Jugal Garg, Ruta Mehta, Milind A. Sohoni, and Nisheeth K. Vishnoi. 2013. Towards polynomial simplex-like algorithms for market equilibria. In Proceedings of the 24th Symposium on Discrete Algorithms (SODA\u201913). 1226--1242."},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1145\/2591796.2591863"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1287\/moor.1060.0216"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-77105-0_38"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1145\/3136754"},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539705447384"},{"key":"e_1_2_1_40_1","unstructured":"Frank Kelly and Vijay Vazirani. 2002. Rate Control as a Market Equilibrium. Retrieved April 10 209 from http:\/\/www.cc.gatech.edu\/&sim;vazirani\/KV.pdf.  Frank Kelly and Vijay Vazirani. 2002. Rate Control as a Market Equilibrium. Retrieved April 10 209 from http:\/\/www.cc.gatech.edu\/&sim;vazirani\/KV.pdf."},{"key":"e_1_2_1_41_1","volume-title":"Microeconomic Theory","author":"Mas-Colell Andreu","unstructured":"Andreu Mas-Colell , Michael Whinston , and Jerry Green . 1995. Microeconomic Theory . Oxford University Press . Andreu Mas-Colell, Michael Whinston, and Jerry Green. 1995. Microeconomic Theory. Oxford University Press."},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1016\/0304-4068(95)00763-6"},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1145\/1806689.1806731"},{"key":"e_1_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.2307\/2549561"},{"key":"e_1_2_1_45_1","volume-title":"The Computation of Economic Equilibria","author":"Scarf Herbert","unstructured":"Herbert Scarf . 1973. The Computation of Economic Equilibria . Yale University Press , New Haven, CT . Herbert Scarf. 1973. The Computation of Economic Equilibria. Yale University Press, New Haven, CT."},{"key":"e_1_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.2307\/2296080"},{"key":"e_1_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.2307\/1912771"},{"key":"e_1_2_1_48_1","volume-title":"Samuelsonian Economics and the Twenty-First Century","author":"Varian Hal","unstructured":"Hal Varian . 2005. Revealed preference . In Samuelsonian Economics and the Twenty-First Century , M. Szenberg, L. Ramrattan, and A. Gottesman (Eds.). Oxford University Press , Oxford, UK , 99--115. Hal Varian. 2005. Revealed preference. In Samuelsonian Economics and the Twenty-First Century, M. Szenberg, L. Ramrattan, and A. Gottesman (Eds.). Oxford University Press, Oxford, UK, 99--115."},{"key":"e_1_2_1_49_1","doi-asserted-by":"publisher","DOI":"10.1287\/moor.1100.0450"},{"key":"e_1_2_1_50_1","doi-asserted-by":"publisher","DOI":"10.1145\/1970392.1970394"},{"key":"e_1_2_1_51_1","doi-asserted-by":"publisher","DOI":"10.1137\/140978296"},{"key":"e_1_2_1_52_1","volume-title":"\u00c9l\u00e9ments d\u2019\u00e9conomie politique pure, ou th\u00e9orie de la richesse sociale (Elements of Pure Economics, or the Theory of Social Wealth)","author":"Walras L\u00e9on","unstructured":"L\u00e9on Walras . 1874. \u00c9l\u00e9ments d\u2019\u00e9conomie politique pure, ou th\u00e9orie de la richesse sociale (Elements of Pure Economics, or the Theory of Social Wealth) . Lausanne , Paris . L\u00e9on Walras. 1874. \u00c9l\u00e9ments d\u2019\u00e9conomie politique pure, ou th\u00e9orie de la richesse sociale (Elements of Pure Economics, or the Theory of Social Wealth). Lausanne, Paris."},{"key":"e_1_2_1_53_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2007.02.016"}],"container-title":["ACM Transactions on Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3319394","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3319394","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T22:38:21Z","timestamp":1750199901000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3319394"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,6,7]]},"references-count":53,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2019,7,31]]}},"alternative-id":["10.1145\/3319394"],"URL":"https:\/\/doi.org\/10.1145\/3319394","relation":{},"ISSN":["1549-6325","1549-6333"],"issn-type":[{"value":"1549-6325","type":"print"},{"value":"1549-6333","type":"electronic"}],"subject":[],"published":{"date-parts":[[2019,6,7]]},"assertion":[{"value":"2018-04-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2019-03-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2019-06-07","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}