2026-07-20T14:36:19Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:2672 2024-03-06T11:09:18Z ddc:004 open_access

Improved Algorithms for Computing Fisher's Market Clearing Prices Orlin, James B. Market equilibrium Fisher strongly polynomial 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 $e_i$ of money. The integral utility for buyer $i$ of good $j$ is $U_{ij}$. We first develop a weakly polynomial time algorithm that runs in $O(n^4 log U_{max} + n^3 e_{max})$ time, where $n = |B| + |G|$. We further modify the algorithm so that it runs in $O(n^4 log n)$ time. These algorithms improve upon the previous best running time of $O(n^8 log U_{max} + n^7 log e_{max})$, due to Devanur et al. Schloss Dagstuhl – Leibniz-Zentrum für Informatik James B. Orlin 2010 Is Part Of Dagstuhl Seminar Proceedings, Volume 10171, Equilibrium Computation (2010) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/DagSemProc.10171.2 urn:nbn:de:0030-drops-26720 https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.10171.2 eng https://creativecommons.org/licenses/by/4.0/legalcode