In this paper we consider the classic problem of finding the market equilibrium prices under linear utility functions. A notion of approximate market equilibrium was proposed by Deng, Papadimitriou and Safra. Using this notion, we present the first fully polynomial-time approximation scheme for finding a market equilibrium price vector. The main tool in our algorithm is the polynomial-time algorithm of Devanur et al. for a variant of the problem in which there is a clear demarcation between buyers and sellers. Their algorithm is used as a subroutine in our algorithm.
展开▼
