2010/06/05 by James B. Orlin · 1 citation
Economics, Econometrics and Finance · Computer Science · Decision Sciences · #Economic theories and models #Optimization and Search Problems #Game Theory and Applications
paper · doi:10.1145/1806689.1806731
openalex publication_date 2010/06/05 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/29
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.