{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,10]],"date-time":"2026-06-10T16:12:36Z","timestamp":1781107956447,"version":"3.54.1"},"reference-count":25,"publisher":"National Academy of Sciences","issue":"5","content-domain":{"domain":["www.pnas.org"],"crossmark-restriction":true},"short-container-title":["Proc. Natl. Acad. Sci. U.S.A."],"published-print":{"date-parts":[[2010,2,2]]},"abstract":"<jats:p>\n                    We show that there is no discrete-time price-adjustment mechanism (any process that at each period looks at the history of prices and excess demands and updates the prices) such that for any market (a set of goods and consumers with endowments and strictly concave utilities) the price-adjustment mechanism will achieve excess demands that are at most an\n                    <jats:italic>\u03f5<\/jats:italic>\n                    fraction of the total supply within a number of periods that is polynomial in the number of goods and\n                    <jats:inline-formula>\n                      <jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" xlink:href=\"pnas.0914728107eq1.gif\"\/>\n                    <\/jats:inline-formula>\n                    . This holds even if one restricts markets so that excess demand functions are differentiable with derivatives bounded by a small constant. For the convergence time to the actual price equilibrium, we show by a different method a stronger result: Even in the case of three goods with a unique price equilibrium, there is no function of\n                    <jats:italic>\u03f5<\/jats:italic>\n                    that bounds the number of periods needed by a price-adjustment mechanism to arrive at a set of prices that is\n                    <jats:italic>\u03f5<\/jats:italic>\n                    -close to the equilibrium.\n                  <\/jats:p>","DOI":"10.1073\/pnas.0914728107","type":"journal-article","created":{"date-parts":[[2010,1,19]],"date-time":"2010-01-19T23:53:28Z","timestamp":1263945208000},"page":"1854-1859","update-policy":"https:\/\/doi.org\/10.1073\/pnas.cm10313","source":"Crossref","is-referenced-by-count":7,"title":["An impossibility theorem for price-adjustment mechanisms"],"prefix":"10.1073","volume":"107","author":[{"given":"Christos H.","family":"Papadimitriou","sequence":"first","affiliation":[{"name":"Department of Electrical Engineering and Computer Science, University of California, Berkeley, CA 94720;"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Mihalis","family":"Yannakakis","sequence":"additional","affiliation":[{"name":"Department of Computer Science, Columbia University, New York NY 10027"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"341","published-online":{"date-parts":[[2010,1,19]]},"reference":[{"key":"e_1_3_3_1_2","doi-asserted-by":"publisher","DOI":"10.2307\/1907353"},{"key":"e_1_3_3_2_2","unstructured":"L Walras El\u00e9ments d\u2019 Economie Politique L. Corbaz Lausanne. (1874)."},{"key":"e_1_3_3_3_2","doi-asserted-by":"publisher","DOI":"10.2307\/2556215"},{"key":"e_1_3_3_4_2","doi-asserted-by":"publisher","DOI":"10.1137\/0115116"},{"key":"e_1_3_3_5_2","volume-title":"Ten Economic Studies in the Tradition of Irving Fisher","author":"Scarf H","year":"1967","unstructured":"H Scarf, On the computation of equilibrium prices. Ten Economic Studies in the Tradition of Irving Fisher (John Wiley and Sons, New York, 1967)."},{"key":"e_1_3_3_6_2","volume-title":"The Computation of Economic Equilibria","author":"Scarf H","year":"1973","unstructured":"H Scarf The Computation of Economic Equilibria (Yale Univ Press, New Haven, with collaboration of T. Hansen. (1973)."},{"key":"e_1_3_3_7_2","doi-asserted-by":"publisher","DOI":"10.1016\/0304-4068(76)90019-7"},{"key":"e_1_3_3_8_2","doi-asserted-by":"publisher","DOI":"10.2307\/1911438"},{"key":"e_1_3_3_9_2","doi-asserted-by":"publisher","DOI":"10.1016\/0165-1765(87)90023-1"},{"key":"e_1_3_3_10_2","doi-asserted-by":"publisher","DOI":"10.2307\/2938327"},{"key":"e_1_3_3_11_2","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-4068(96)00770-7"},{"key":"e_1_3_3_12_2","doi-asserted-by":"crossref","unstructured":"NR Devanur CH Papadimitriou A Saberi VV Vazirani Market equilibrium via a primal-dual algorithm for a convex program. J ACM 55 1\u201318 (2008).","DOI":"10.1145\/1411509.1411512"},{"key":"e_1_3_3_13_2","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511800481"},{"key":"e_1_3_3_14_2","doi-asserted-by":"publisher","DOI":"10.1145\/1374376.1374422"},{"key":"e_1_3_3_15_2","doi-asserted-by":"publisher","DOI":"10.1145\/1109557.1109629"},{"key":"e_1_3_3_16_2","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2007.39"},{"key":"e_1_3_3_17_2","doi-asserted-by":"publisher","DOI":"10.1145\/1132516.1132527"},{"key":"e_1_3_3_18_2","doi-asserted-by":"publisher","DOI":"10.1016\/0885-064X(89)90017-4"},{"key":"e_1_3_3_19_2","doi-asserted-by":"publisher","DOI":"10.1093\/oso\/9780195106909.001.0001"},{"key":"e_1_3_3_20_2","first-page":"59","article-title":"Walras\u2019 existence theorem and Brouwer\u2019s fixpoint theorem","volume":"13","author":"Uzawa H","year":"1962","unstructured":"H Uzawa, Walras\u2019 existence theorem and Brouwer\u2019s fixpoint theorem. Econ Stud Quart 13, 59\u201362 (1962).","journal-title":"Econ Stud Quart"},{"key":"e_1_3_3_21_2","doi-asserted-by":"publisher","DOI":"10.1016\/0304-4068(74)90032-9"},{"key":"e_1_3_3_22_2","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0531(74)90100-8"},{"key":"e_1_3_3_23_2","doi-asserted-by":"publisher","DOI":"10.2307\/1913184"},{"key":"e_1_3_3_24_2","doi-asserted-by":"publisher","DOI":"10.1007\/BF01275667"},{"key":"e_1_3_3_25_2","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-4068(02)00060-5"}],"container-title":["Proceedings of the National Academy of Sciences"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/pnas.org\/doi\/pdf\/10.1073\/pnas.0914728107","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,4,14]],"date-time":"2022-04-14T06:01:29Z","timestamp":1649916089000},"score":1,"resource":{"primary":{"URL":"https:\/\/pnas.org\/doi\/full\/10.1073\/pnas.0914728107"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2010,1,19]]},"references-count":25,"journal-issue":{"issue":"5","published-print":{"date-parts":[[2010,2,2]]}},"alternative-id":["10.1073\/pnas.0914728107"],"URL":"https:\/\/doi.org\/10.1073\/pnas.0914728107","relation":{},"ISSN":["0027-8424","1091-6490"],"issn-type":[{"value":"0027-8424","type":"print"},{"value":"1091-6490","type":"electronic"}],"subject":[],"published":{"date-parts":[[2010,1,19]]},"assertion":[{"value":"2010-01-19","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}