A path to the Arrow-Debreu competitive market equilibrium

被引:67
作者
Ye, Yinyu [1 ]
机构
[1] Stanford Univ, Dept Management Sci & Engn, Stanford, CA 94305 USA
关键词
D O I
10.1007/s10107-006-0065-5
中图分类号
TP31 [计算机软件];
学科分类号
081202 ; 0835 ;
摘要
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, efficient 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.
引用
收藏
页码:315 / 348
页数:34
相关论文
共 40 条
[11]  
Eaves BC, 1976, J. Math. Econom., V3, P197, DOI 10.1016/0304-4068(76)90028-8
[12]   CONSENSUS OF SUBJECTIVE PROBABILITIES - THE PARI-MUTUEL METHOD [J].
EISENBERG, E ;
GALE, D .
ANNALS OF MATHEMATICAL STATISTICS, 1959, 30 (01) :165-168
[13]   Computing equilibria in general equilibrium models via interior-point methods [J].
Esteban-Bravo M. .
Computational Economics, 2004, 23 (2) :147-171
[14]   Engineering and economic applications of complementarity problems [J].
Ferris, MC ;
Pang, JS .
SIAM REVIEW, 1997, 39 (04) :669-713
[15]  
Gale David, 1960, THEORY LINEAR EC MOD
[16]  
GINSBURGH V, 1077, STRUCTURE APPL GEN E
[18]   A polynomial time algorithm for computing an Arrow-Debreu market equilibrium for linear utilities [J].
Jain, K .
45TH ANNUAL IEEE SYMPOSIUM ON FOUNDATIONS OF COMPUTER SCIENCE, PROCEEDINGS, 2004, :286-294
[19]  
Jain K, 2003, LECT NOTES COMPUT SC, V2764, P98
[20]  
Jain K, 2005, PROCEEDINGS OF THE SIXTEENTH ANNUAL ACM-SIAM SYMPOSIUM ON DISCRETE ALGORITHMS, P63