Market equilibrium via the excess demand function

ABSTRACT

We consider the problem of computing market equilibria and show three results. (i) For exchange economies satisfying weak gross substitutability we analyze a simple discrete version of tâtonnement, and prove that it converges to an approximate equilibrium in polynomial time. This is the first polynomial-time approximation scheme based on a simple atonnement process. It was only recently shown, using vastly more sophisticated techniques, that an approximate equilibrium for this class of economies is computable in polynomial time. (ii) For Fisher's model, we extend the frontier of tractability by developing a polynomial-time algorithm that applies well beyond the homothetic case and the gross substitutes case. (iii) For production economies, we obtain the first polynomial-time algorithms for computing an approximate equilibrium when the consumers' side of the economy satisfies weak gross substitutability and the producers' side is restricted to positive production.

REFERENCES

• 1: K.J. Arrow and G. Debreu, Existence of an Equilibrium for a Competitive Economy, Econometrica 22 (3), pp. 265--290 (1954).
• 2: K. J. Arrow, H. D. Block, and L. Hurwicz. On the stability of the competitive equilibrium, II. Econometrica 27, 82--109 (1959).
• 3: K. J. Arrow and L. Hurwicz. Some remarks on the equilibria of economic systems. Econometrica 28, 640--646.
• 4: K. J. Arrow and L. Hurwicz. Competitive stability under weak gross substitutability: The "Euclidean distance" approach. International Economic Review 1, 1960, 38--49.
• 5: N. Chen, X. Deng, X. Sun, and A. Yao, Fisher Equilibrium Price with a Class of Concave Utility Functions, ESA 2004.
• 6: B. Codenotti, B. McCune, S. Pemmaraju, R. Raman, and K. Varadarajan, An experimental study of different approaches to solve the market equilibrium problem. In Proceedings of ALENEX 2005.
• 7: Bruno Codenotti , Sriram Pemmaraju , Kasturi Varadarajan, The computation of market equilibria, ACM SIGACT News, v.35 n.4, December 2004 [doi>10.1145/1054916.1054927]
• 8: Bruno Codenotti , Sriram Pemmaraju , Kasturi Varadarajan, On the polynomial time computation of equilibria for certain exchange economies, Proceedings of the sixteenth annual ACM-SIAM symposium on Discrete algorithms, January 23-25, 2005, Vancouver, British Columbia
• 9: B. Codenotti, K. Varadarajan, Efficient Computation of Equilibrium Prices for Markets with Leontief Utilities, ICALP 2004.
• 10: Nikhil R. Devanur , Christos H. Papadimitriou , Amin Saberi , Vijay V. Vazirani, Market Equilibrium via a Primal-Dual-Type Algorithm, Proceedings of the 43rd Symposium on Foundations of Computer Science, p.389-395, November 16-19, 2002
• 11: E. Eisenberg, Aggregation of Utility Functions. Management Sciences, Vol. 7 (4), 337--350 (1961).
• 12: Rahul Garg , Sanjiv Kapoor, Auction algorithms for market equilibrium, Proceedings of the thirty-sixth annual ACM symposium on Theory of computing, June 13-16, 2004, Chicago, IL, USA [doi>10.1145/1007352.1007430]
• 13: R. Garg, S. Kapoor, and V. V. Vazirani, Approximating Market Equilbrium-The Separable Gross Substitutability Case, APPROX 2004.
• 14: F. H. Hahn, Gross Substitutes and the Dynamic Stability of General Equilibrium, Econometrica, Vol. 26 (1), p.169--170 (1958).
• 15: F. H. Hahn, Stability, in K.J. Arrow and M.D. Intriligator, editors, Handbook of Mathematical Economics, Vol. II. North-Holland (1982).
• 16: Kamal Jain, A Polynomial Time Algorithm for Computing the Arrow-Debreu Market Equilibrium for Linear Utilities, Proceedings of the 45th Annual IEEE Symposium on Foundations of Computer Science (FOCS'04), p.286-294, October 17-19, 2004 [doi>10.1109/FOCS.2004.6]
• 17: K. Jain, A polynomial size convex program for market equilibria with production planning and linear utilities.
• 18: K. Jain, M. Mahdian, and A. Saberi, Approximating Market Equilibria, Proc. APPROX 2003.
• 19: Kamal Jain , Vijay V. Vazirani , Yinyu Ye, Market equilibria for homothetic, quasi-concave utilities and economies of scale in production, Proceedings of the sixteenth annual ACM-SIAM symposium on Discrete algorithms, January 23-25, 2005, Vancouver, British Columbia
• 20: T. J. Kehoe, Uniqueness and Stability, in Alan P. Kirman, editor, Elements of General Equilibrium Analysis, Basil Blackwell, 1998, 38--87.
• 21: A. Mas-Colell, On the Uniqueness of Equilibrium Once Again, in: Equilibrium Theory and Applications, W. Barnett, B. Cornet, C. D'Aspremont, J. Gabszewicz, and A. Mas-Colell (eds). Cambridge University Press (1991).
• 22: A. Mas-Colell, M.D. Whinston, and J.R. Green, Microeconomic Theory, Oxford University Press (1995).
• 23: L.G. Mitjuschin and W. M. Polterovich, Criteria for monotonicity ofdemand functions, Ekonomika i Matematicheskie Metody, 14, 122--128 (1978). (In Russian.)
• 24: T. Negishi, A Note on the Stability of an Economy where All Goods are Gross Substitutes, Econometrica (1958).
• 25: T. Negishi, Stability of a Competitive Economy: A survey article, Econometrica (1962).
• 26: E. I. Nenakov and M. E. Primak. One algorithm for finding solutions of the Arrow-Debreu model, Kibernetica 3, 127--128 (1983). (In Russian.)
• 27: D. J. Newman and M. E. Primak. Complexity of Circumscribed and Inscribed Ellipsoid Methods for Solving Equilibrium Economical Models, Applied Mathematics and Computation 52: 223--231 (1992).
• 28: M. E. Primak, An algorithm for finding a solution of the linear exchange model and the linear Arrow-Debreu model, Kibernetika 5, 76--81 (1984).
• 29: M. E. Primak, A converging algorithm for a linear exchange model, Journal of Mathematical Economics 22, 181--187 (1993).
• 30: V. M. Polterovich, Economic Equilibrium and the Optimum, Matekon (5), pp. 3--20 (1973).
• 31: P.A. Samuelson, Foundations of Economic Analysis. Harvard University Press (1947).
• 32: L. Walras, Elements of Pure Economics, Allen and Unwin (1954).

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Geometrical problems and computations

General Terms:
Algorithms, Economics

Keywords:
algorithms, approximation, market equilibrium, polynomial-time algorithms, tâtonnement