Speaker: Yinyu Ye Stanford University
Time: 2004-12-20 14:30-2004-12-20 15:30
We present polynomial-time interior-point algorithms for solving the Fisher and Arrow-Debreu competitive market equilibrium problems with linear utilities and n players. Both of them have the arithmetic computation complexity bound of O(n4 log(1/?)) for computing an ? equilibrium solution. If the problem data are rational numbers and their bit-length is L, then the bound to generate an exact solution is O(n^4L) which is in line with the best complexity bound for linear programming of the same dimension and size. This is a significant improvement over the previously best bound O(n^8L) for solving the two problems using other methods. The key ingredient to derive these results is to show that these problems admit convex optimization formulations and efficient barrier functions. We also further generalize these results to homothetic and/or quasi-concave utilities, and to the market equilibrium in the presence of economies of production and non-exogenous activities.