Improved Algorithms for Computing Fisher's Market Clearing Prices
ACM Digital Library url: http://dl.acm.org/citation.cfm?id=1806731
| Main Author: | |
|---|---|
| Other Authors: | |
| Format: | Article |
| Language: | en_US |
| Published: |
Association for Computing Machinery
2012
|
| Online Access: | http://hdl.handle.net/1721.1/68009 https://orcid.org/0000-0002-7488-094X |
| _version_ | 1811088887250944000 |
|---|---|
| author | Orlin, James B. |
| author2 | Sloan School of Management |
| author_facet | Sloan School of Management Orlin, James B. |
| author_sort | Orlin, James B. |
| collection | MIT |
| description | ACM Digital Library url: http://dl.acm.org/citation.cfm?id=1806731 |
| first_indexed | 2024-09-23T14:08:40Z |
| format | Article |
| id | mit-1721.1/68009 |
| institution | Massachusetts Institute of Technology |
| language | en_US |
| last_indexed | 2024-09-23T14:08:40Z |
| publishDate | 2012 |
| publisher | Association for Computing Machinery |
| record_format | dspace |
| spelling | mit-1721.1/680092022-10-01T19:29:50Z Improved Algorithms for Computing Fisher's Market Clearing Prices Orlin, James B. Sloan School of Management Orlin, James B. Orlin, James B. ACM Digital Library url: http://dl.acm.org/citation.cfm?id=1806731 We give the first strongly polynomial time algorithm for computing an equilibrium for the linear utilities case of Fisher's market model. We consider a problem with a set B of buyers and a set G of divisible goods. Each buyer i starts with an initial integral allocation ei of money. The integral utility for buyer i of good j is Uij. We first develop a weakly polynomial time algorithm that runs in O(n4 log Umax + n3 emax) time, where n = |B| + |G|. We further modify the algorithm so that it runs in O(n4 log n) time. These algorithms improve upon the previous best running time of O(n8 log Umax + n7 log emax), due to Devanur et al. United States. Office of Naval Research (ONR grant N00014-05-1-0165) 2012-01-06T16:31:07Z 2012-01-06T16:31:07Z 2010-06 Article http://purl.org/eprint/type/ConferencePaper 978-1-4503-0050-6 http://hdl.handle.net/1721.1/68009 Orlin, James B. “Improved algorithms for computing fisher’s market clearing prices.” Proceedings of the 42nd ACM symposium on Theory of computing, STOC '10, ACM Press, 2010. 291. https://orcid.org/0000-0002-7488-094X en_US http://dx.doi.org/10.1145/1806689.1806731 Proceedings of the 42nd ACM Symposium on Theory of Computing, STOC 2010, June 5, 2010 - June 8, 2010. Creative Commons Attribution-Noncommercial-Share Alike 3.0 http://creativecommons.org/licenses/by-nc-sa/3.0/ application/pdf Association for Computing Machinery Prof. Orlin via Alex Caracuzzo |
| spellingShingle | Orlin, James B. Improved Algorithms for Computing Fisher's Market Clearing Prices |
| title | Improved Algorithms for Computing Fisher's Market Clearing Prices |
| title_full | Improved Algorithms for Computing Fisher's Market Clearing Prices |
| title_fullStr | Improved Algorithms for Computing Fisher's Market Clearing Prices |
| title_full_unstemmed | Improved Algorithms for Computing Fisher's Market Clearing Prices |
| title_short | Improved Algorithms for Computing Fisher's Market Clearing Prices |
| title_sort | improved algorithms for computing fisher s market clearing prices |
| url | http://hdl.handle.net/1721.1/68009 https://orcid.org/0000-0002-7488-094X |
| work_keys_str_mv | AT orlinjamesb improvedalgorithmsforcomputingfishersmarketclearingprices |