{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,10]],"date-time":"2026-06-10T07:47:38Z","timestamp":1781077658206,"version":"3.54.1"},"reference-count":43,"publisher":"Association for Computing Machinery (ACM)","issue":"2","license":[{"start":{"date-parts":[[2019,5,31]],"date-time":"2019-05-31T00:00:00Z","timestamp":1559260800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["CRII Award 1755619"],"award-info":[{"award-number":["CRII Award 1755619"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Econ. Comput."],"published-print":{"date-parts":[[2019,5,31]]},"abstract":"<jats:p>Earning limits and utility limits are novel aspects in the classic Fisher market model. Sellers with earning limits have bounds on their income and lower the supply they bring to the market if income exceeds the limit. Buyers with utility limits have an upper bound on the amount of utility that they want to derive and lower the budget they bring to the market if utility exceeds the limit. Markets with these properties can have multiple equilibria with different characteristics.<\/jats:p>\n          <jats:p>\n            We analyze earning limits and utility limits in markets with linear and spending-constraint utilities. For markets with earning limits and spending-constraint utilities, we show that equilibrium price vectors form a lattice and the spending of buyers is unique in non-degenerate markets. We provide a scaling-based algorithm to compute an equilibrium in time\n            <jats:italic>O<\/jats:italic>\n            (\n            <jats:italic>n<\/jats:italic>\n            <jats:sup>3<\/jats:sup>\n            \u2113 log (\u2113 +\n            <jats:italic>nU<\/jats:italic>\n            )), where\n            <jats:italic>n<\/jats:italic>\n            is the number of agents, \u2113 \u2265\n            <jats:italic>n<\/jats:italic>\n            a bound on the segments in the utility functions, and\n            <jats:italic>U<\/jats:italic>\n            the largest integer in the market representation. We show how to refine any equilibrium in polynomial time to one with minimal prices or one with maximal prices (if it exists). Moreover, our algorithm can be used to obtain in polynomial time a 2-approximation for maximizing Nash social welfare in multi-unit markets with indivisible items that come in multiple copies.\n          <\/jats:p>\n          <jats:p>For markets with utility limits and linear utilities, we show similar results\u2014lattice structure of price vectors, uniqueness of allocation in non-degenerate markets, and polynomial-time refinement procedures to obtain equilibria with minimal and maximal prices. We complement these positive results with hardness results for related computational questions. We prove that it is NP-hard to compute a market equilibrium that maximizes social welfare, and it is PPAD-hard to find any market equilibrium with utility functions with separate satiation points for each buyer and each good.<\/jats:p>","DOI":"10.1145\/3340234","type":"journal-article","created":{"date-parts":[[2019,7,19]],"date-time":"2019-07-19T13:17:14Z","timestamp":1563542234000},"page":"1-35","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":7,"title":["Earning and Utility Limits in Fisher Markets"],"prefix":"10.1145","volume":"7","author":[{"given":"Xiaohui","family":"Bei","sequence":"first","affiliation":[{"name":"Nanyang Technological University, Singapore"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Jugal","family":"Garg","sequence":"additional","affiliation":[{"name":"University of Illinois at Urbana-Champaign, Urbana, IL, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Martin","family":"Hoefer","sequence":"additional","affiliation":[{"name":"Goethe University Frankfurt, Germany"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Kurt","family":"Mehlhorn","sequence":"additional","affiliation":[{"name":"Max-Planck-Institut f\u00fcr Informatik, Saarbruecken, Germany"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2019,7,18]]},"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.1007\/978-3-540-27810-8_4"},{"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-70575-8_16"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/3319394"},{"key":"e_1_2_1_6_1","volume-title":"Proceedings of the 24th European Symposium on Algorithms (ESA\u201916)","author":"Bei Xiaohui","year":"2016","unstructured":"Xiaohui Bei , Jugal Garg , Martin Hoefer , and Kurt Mehlhorn . 2016 . Computing equilibria in markets with budget-additive utilities . In Proceedings of the 24th European Symposium on Algorithms (ESA\u201916) . 8:1--8:14. Xiaohui Bei, Jugal Garg, Martin Hoefer, and Kurt Mehlhorn. 2016. Computing equilibria in markets with budget-additive utilities. In Proceedings of the 24th European Symposium on Algorithms (ESA\u201916). 8:1--8:14."},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-66700-3_6"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/1993574.1993594"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.5555\/1778580.1778606"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.5555\/1873601.1873646"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.5555\/1958033.1958038"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-10631-6_66"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/2488608.2488633"},{"key":"e_1_2_1_14_1","doi-asserted-by":"crossref","unstructured":"Bruno Codenotti and Kasturi Varadarajan. 2007. Computation of market equilibria by convex programming. See Reference {34} Chapter 8.  Bruno Codenotti and Kasturi Varadarajan. 2007. Computation of market equilibria by convex programming. See Reference {34} Chapter 8.","DOI":"10.1017\/CBO9780511800481.008"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/3033274.3085109"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/1374376.1374422"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1137\/15M1053682"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.5555\/3174304.3175454"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/1411509.1411512"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/1007352.1007431"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-48995-6_22"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.5555\/2884435.2884442"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ic.2014.12.009"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1214\/aoms\/1177706369"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1137\/13094339X"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.5555\/3174304.3175455"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1287\/moor.1110.0517"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/96559.96597"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1145\/3136754"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539705447384"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.geb.2008.11.011"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.5555\/2627817.2627905"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539794263695"},{"key":"e_1_2_1_34_1","doi-asserted-by":"crossref","unstructured":"Noam Nisan \u00c9va Tardos Tim Roughgarden and Vijay Vazirani (Eds.). 2007. Algorithmic Game Theory. Cambridge University Press.   Noam Nisan \u00c9va Tardos Tim Roughgarden and Vijay Vazirani (Eds.). 2007. Algorithmic Game Theory. Cambridge University Press.","DOI":"10.1017\/CBO9780511800481"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1145\/1806689.1806731"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1145\/2764468.2764515"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1134\/S1990478909040097"},{"key":"e_1_2_1_38_1","unstructured":"Vijay Vazirani. 2007. Combinatorial algorithms for market equilibria. See Reference {34} Chapter 7.  Vijay Vazirani. 2007. Combinatorial algorithms for market equilibria. See Reference {34} Chapter 7."},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1287\/moor.1100.0450"},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1287\/moor.2013.0623"},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1137\/140978296"},{"key":"e_1_2_1_42_1","first-page":"1","article-title":"A path to the Arrow-Debreu competitive market equilibrium","volume":"111","author":"Ye Yinyu","year":"2008","unstructured":"Yinyu Ye . 2008 . A path to the Arrow-Debreu competitive market equilibrium . Math. Prog. 111 , 1 -- 2 (2008), 315--348. Yinyu Ye. 2008. A path to the Arrow-Debreu competitive market equilibrium. Math. Prog. 111, 1--2 (2008), 315--348.","journal-title":"Math. Prog."},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2010.06.021"}],"container-title":["ACM Transactions on Economics and Computation"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3340234","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3340234","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3340234","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T17:49:32Z","timestamp":1750268972000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3340234"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,5,31]]},"references-count":43,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2019,5,31]]}},"alternative-id":["10.1145\/3340234"],"URL":"https:\/\/doi.org\/10.1145\/3340234","relation":{},"ISSN":["2167-8375","2167-8383"],"issn-type":[{"value":"2167-8375","type":"print"},{"value":"2167-8383","type":"electronic"}],"subject":[],"published":{"date-parts":[[2019,5,31]]},"assertion":[{"value":"2018-03-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2019-05-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2019-07-18","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}