Extending the Approximability Frontier ofarket Equilibrium
Date Issued
2008
Date
2008
Author(s)
Tseng, Wen-Liang
Abstract
We consider the computation of market equilibrium and make progress along directions of utility function sets and unbounded unmber of goods for a production economy of Fisher’s model. Eisenberg and Gale gave a convex program for computing market equilibrium for linear utility functions, and Eisenberg generalized this to concave homogeneous functions of degree one. Jain, Vazirani and Yeeneralized to homothetic, quasi-concave functions. We apply the method developed by Codenotti, McCune, and Varadarajan to further extend the frontier of approximability to the utility functions that imply monotone demand, which include the cases beyond homothetic and gross substitutes. In addition, by a careful analysis in the applied method, we show that our results can be extended to the case where the number of goods is unbounded. Thus we make progress towards affirmativelynswering the problem mentioned by Deng, Papadimitriou, and Safra.
Subjects
market equilibrium
approximation algorithm
Type
thesis
File(s)![Thumbnail Image]()
Loading...
Name
ntu-97-R92943139-1.pdf
Size
23.32 KB
Format
Adobe PDF
Checksum
(MD5):b8c3d5854896943600726ea3be1c6bb5