Improved Algorithms for Computing Fisher's Market Clearing Prices

2022/01/26 by Orlin, James B.
#Fisher #Market equilibrium #strongly polynomial

paper · doi:10.4230/dagsemproc.10171.2

Abstract

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⁴ log U_max + n³ e_max) time, where n = |B| + |G|. We further modify the algorithm so that it runs in O(n⁴ log n) time. These algorithms improve upon the previous best running time of O(n⁸ log U_max + n⁷ log e_max), due to Devanur et al.

Related

• Computing Equilibrium in Matching Markets
• Computing Equilibria in Markets with Budget-Additive Utilities
• Matching Markets
• Fisher Markets with Linear Constraints: Equilibrium Properties and Efficient Distributed Algorithms
• Approximating Equilibrium under Constrained Piecewise Linear Concave Utilities with Applications to Matching Markets