| Summary: | 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 operation complexity bound of O(n^4 log(1/Epsilon)) for computing an Epsilon-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^4)L) 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^8 log(1/Epsilon)) for approximating the two problems using other methods. The key ingredient to derive these results is to show that these problems admit convex optimization formulations, e±cient barrier functions and fast rounding techniques. We also present a continuous path leading to the set of the Arrow-Debreu equilibrium, similar to the central path developed for linear programming interior-point methods. This path is derived from the weighted logarithmic utility and barrier functions and the Brouwer fixed-point theorem. The defining equations are bilinear and possess some primal-dual structure for the application of the Newton-based path-following method. |
