  


A Path to the ArrowDebreu Competitive Market Equilibrium
Yinyu Ye (yinyuyestanford.edu) Abstract: We present polynomialtime interiorpoint algorithms for solving the Fisher and ArrowDebreu 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 bitlength 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^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, efficient barrier functions and fast rounding techniques. We also present a continuous path leading to the set of the ArrowDebreu equilibrium, similar to the central path developed for linear programming interiorpoint methods. This path is derived from the weighted logarithmic utility and barrier functions and the Brouwer fixedpoint theorem. The defining equations are bilinear and possess some primaldual structure for the application of the Newtonbased pathfollowing method. Keywords: Analytic Center, Market Equilibria, , Complexity Category 1: Other Topics (Game Theory ) Category 2: Linear, Cone and Semidefinite Programming (Linear Programming ) Category 3: Complementarity and Variational Inequalities Citation: Working Paper posted February/23/04, revised final version July 15, 2005; to appear in Math Programming 2006. Download: [PDF] Entry Submitted: 07/28/2006 Modify/Update this entry  
Visitors  Authors  More about us  Links  
Subscribe, Unsubscribe Digest Archive Search, Browse the Repository

Submit Update Policies 
Coordinator's Board Classification Scheme Credits Give us feedback 
Optimization Journals, Sites, Societies  