On the polynomial time computation of equilibria for certain exchange economies

ABSTRACT

The problem of computing equilibria for exchange economies has recently started to receive a great deal of attention in the theoretical computer science community. It has been shown that equilibria can be computed in polynomial time in various special cases, the most important of which are when traders have linear, Cobb-Douglas, or a range of CES utility functions. These important special cases are instances when the market satisfies a property called weak gross substitutability. Classical results in economics, which theoretical computer scientists (including us) appear to have been hitherto unaware of, show that the equilibrium prices in such markets are characterized by an infinite number of linear inequalities and therefore form a convex set. In this paper, we show that under fairly general assumptions, there are polynomial-time algorithms to compute equilibria in such markets. To the best of our knowledge, these are the first polynomial-time algorithms for exchange markets under the general setting of weak gross substitutability. To show this result, we need to build on the proofs that characterize the equilibria as a convex set.As a consequence, we obtain alternative polynomial-time algorithms for computing equilibria with linear, Cobb-Douglas, a range of CES, as well as certain other non-homogeneous utility functions that satisfy weak gross substitutability. Unlike previous polynomial-time algorithms, our approach does not make use of the specific form of these utility functions and is in this sense more general. We expect our framework to work or be readily adaptable to handle other exchange markets, provided that the utility functions satisfy weak gross substitutability.

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: J. S. Chipman, Homothetic Preferences and Aggregation, Journal of Economic Theory 8, 26--38 (1974).
• 6: B. Codenotti, B. McCune, S. Pemmaraju, K. Varadarajan. Manuscript in preparation.
• 7: B. Codenotti and K. Varadarajan, Efficient Computation of Equilibrium Prices for Markets with Leontief Utilities. ICALP 2004.
• 8: B. Codenotti and K. Varadarajan, Equilibrium for Elastic Exchange Markets: From Nonlinear Complementarity to Convex Programming. Submitted, 2004.
• 9: 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
• 10: Nikhil R. Devanur, The spending constraint model for market equilibrium: algorithmic, existence and uniqueness results, Proceedings of the thirty-sixth annual ACM symposium on Theory of computing, June 13-16, 2004, Chicago, IL, USA [doi>10.1145/1007352.1007431]
• 11: B. C. Eaves, Finite Solution of Pure Trade Markets with Cobb-Douglas Utilities, Mathematical Programming Study 23, pp. 226--239 (1985).
• 12: E. Eisenberg, Aggregation of Utility Functions. Management Sciences, Vol. 7 (4), 337--350 (1961).
• 13: E. Eisenberg and D. Gale, Consensus of Subjective Probabilities: The Pari-Mutuel Method. Annals of Mathematical Statistics, 30, 165--168 (1959).
• 14: D. Gale, The Theory of Linear Economic Models. McGraw Hill, N.Y. (1960).
• 15: 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]
• 16: R. Garg, S. Kapoor, and V. V. Vazirani, An auction-based market equilbrium algorithm for the separable gross substitutibility case, APPROX 2004.
• 17: M. Grötschel and L. Lovász and A. Schrijver. Geometric Algorithms and Combinatorial Optimization, Algorithms and Combinatorics, Vol. 2, Springer-Verlag, 2nd edition (1994).
• 18: 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]
• 19: K. Jain, M. Mahdian, and A. Saberi, Approximating Market Equilibria, Proc. APPROX 2003.
• 20: A. P. Kirman, K. J. Koch, Market Excess Demand in Exchange Economies with Identical Preferences and Collinear Endowments, Review of Economic Studies 53(3), 457--463 (1986).
• 21: A. Mas-Colell, M. D. Whinston, and J. R. Green, Microeconomic Theory, Oxford University Press (1995).
• 22: E. I. Nenakov and M. E. Primak. One algorithm for finding solutions of the Arrow-Debreu model, Kibernetica 3, 127--128 (1983).
• 23: 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).
• 24: V. M. Polterovich, Economic Equilibrium and the Optimum, Matekon (5), pp. 3--20 (1973).
• 25: V. M. Polterovich and V. A. Spivak. Gross substitutability of point to set correspondences, Journal of Mathematical Economics 11 (2), 117--140 (1983).
• 26: 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).
• 27: M. E. Primak, A converging algorithm for a linear exchange model, Journal of Mathematica Economics 22, 181--187 (1993).
• 28: S. P. Tarasov, L. G. Khachiyan, and I. I. Erlikh, The method of inscribed ellipsoids, Soviet Math. Dokl. 37(1), 226--230 (1988).
• 29: H. Varian, Microeconomic Analysis, New York: W.W. Norton (1992).
• 30: Y. Ye, A Path to the Arrow-Debreu Competitive Market Equilibrium, Discussion Paper, Stanford University, February 2004.
• 31: D. B. Yudin and A. S. Nemirovski, "Evaluation of the informational complexity of mathematical programming problems," (in Russian), Economika i Matematicheskie Metody 12, 128--142, 1976 (English translation: Matekon 13, 2, 3--45, 1976).