A path to the Arrow-Debreu competitive market equilibrium (Q2467155)

The author presents polynomial time algorithms for computing the Fisher and Arrow-Debreu competitive marked equilibrium. A formulation of Fisher's model as convex program leads to optimality conditions which can be solved similar to the primal-dual interior point algorithm for LP's. The complexity of the algorithm is of order \( O(n^4 \log{1/\varepsilon})\) for an \(\varepsilon\)-approximation and of \( O(n^4 L)\) for an exact solution of the problem (with rational data). Secondly, an interior point algorithm for solving the Arrow-Debreu equilibrium problem is presented with complexity \( O(n^4 \log{1/\varepsilon})\) for an \(\varepsilon\)-approximation and \( O(n^4 L)\) for an exact solution as well. This algorithm is based on a convex programming formulation of Arrow-Debreu's model combined with a logarithmic transformation. This formulation allows an interior point approach with selfconcordant barrier function. Finally a formulation of Arrow-Debreu's model as convex program combined with a fixed point condition leads to optimality conditions which can be solved by an interior point pathfollowing procedure. A complexity result for this approach is not yet obtained. The complexity bounds for the algorithms in this article are much better compared with bounds for previously discussed algorithms.