research-article

An experimental study of different approaches to solve the market equilibrium problem

Authors:

Bruno Codenotti,

Sriram Pemmaraju,

Kasturi VaradarajanAuthors Info & Claims

Journal of Experimental Algorithmics (JEA), Volume 12

Article No.: 3.3, Pages 1 - 21

https://doi.org/10.1145/1227161.1402295

Published: 29 August 2008 Publication History

Abstract

Over the last few years, the problem of computing market equilibrium prices for exchange economies has received much attention in the theoretical computer science community. Such activity led to a flurry of polynomial time algorithms for various restricted, yet significant, settings. The most important restrictions arise either when the traders' utility functions satisfy a property known as gross substitutability or when the initial endowments are proportional (the Fisher model). In this paper, we experimentally compare the performance of some of these recent algorithms against that of the most used software packages. In particular, we evaluate the following approaches: (1) the solver PATH, available under GAMS/MPSGE, a popular tool for computing market equilibrium prices; (2) a discrete version of a simple iterative price update scheme called tâtonnement; (3) a discrete version of the welfare adjustment process; (4) convex feasibility programs that characterize the equilibrium in some special cases. We analyze the performance of these approaches on models of exchange economies where the consumers are equipped with utility functions, which are widely used in real world applications. The outcomes of our experiments consistently show that many market settings allow for an efficient computation of the equilibrium, well beyond the restrictions under which the theory provides polynomial time guarantees. For some of the approaches, we also identify models where they are are prone to failure.

References

[1]

Arrow, K. and Debreu, G. 1954. Existence of an equilibrium for a competitive economy. Econometrica 22, 3, 265--290.

[2]

Arrow, K. J. and Hurwicz, L. 1960. Competitive stability under weak gross substitutability: The “euclidean distance” approach. International Economic Review 1, 38--49.

[3]

Arrow, K. J., Block, H. D., and Hurwicz, L. 1959. On the stability of the competitive equilibrium, ii. Econometrica 27, 82--109.

[4]

Bagirov, A. and Rubinov, A. 2001. Global optimization of marginal functions with applications to economic equilibrium. Journal of Global Optimization 20, 215--237.

Digital Library

[5]

Billups, S., Dirkse, S., and Ferris, M. 1997. A comparison of large scale mixed complemetarity problem solvers. Compututational Optimization and Applications 7, 3--25.

Digital Library

[6]

Brooke, A., Kendrick, D., and Meeraus, A. 1988. GAMS: A User's Guide. The Scientific Press, San Francisco, CA.

[7]

Cheng, J. Q. and Wellman, M. P. 1998. The walras algorithm: A convergent distributed implementation of general equilibrium outcomes. Computational Economics 12, 1, 1--24.

Digital Library

[8]

Codenotti, B. and Varadarajan, K. R. 2004. Efficient computation of equilibrium prices for markets with leontief utilities. In ICALP. 371--382.

[9]

Codenotti, B., Pemmaraju, S., and Varadarajan, K. 2004. The computation of market equilibria. ACM SIGACT News 35, 4, 23--37.

Digital Library

[10]

Codenotti, B., McCune, B., Pemmaraju, S. V., Raman, R., and Varadarajan, K. 2005a. An experimental study of different approaches to solve the market equilibrium problem. In ALENEX/ANALCO. 167--179.

Digital Library

[11]

Codenotti, B., McCune, B., Penumatcha, S., and Varadarajan, K. 2005b. Market equilibrium for ces exchange economies: Existence, multiplicity, and computation. In FSTTCS 2005: Foundations of Software Technology and Theoretical Computer Science. Springer Verlag, New York. 505--516.

Digital Library

[12]

Codenotti, B., McCune, B., Raman, R., and Varadarajan, K. 2005c. Computing equilibrium prices: Does theory meet practice&quest; In Proceedings ESA 2005, 13th Annual European Symposium, Palma de Mallorca, Spain, October 3--6, 2005. 83--94.

Digital Library

[13]

Codenotti, B., McCune, B., and Varadarajan, K. 2005d. Market equilibrium via the excess demand function. In Proceedings of the 37th Annual ACM Symposium on Theory of Computing. ACM Press, New York. 74--83.

Digital Library

[14]

Codenotti, B., Pemmaraju, S., and Varadarajan, K. 2005e. On the polynomial time computation of equilibria for certain exchange economies. In Proceedings of the 16th Annual ACM-SIAM Symposium on Discrete Algorithms. Society for Industrial and Applied Mathematics, Philadelphia, PA. 72--81.

Digital Library

[15]

Deng, X., Papadimitriou, C. H., and Safra, M. 2002. On the complexity of equilibria. In Proceedings of the 34th Annual ACM Symposium on Theory of Computing. ACM Press, New York. 67--71.

Digital Library

[16]

Devanur, N. R., Papadimitriou, C. H., Saberi, A., and Vazirani, V. V. 2002. Market equilibrium via a primal-dual-type algorithm. In 43rd Symposium on Foundations of Computer Science. IEEE Computer Science, Los Alamitos, CA. 389--395.

Digital Library

[17]

Dirkse, S. and Ferris, M. 1996. A pathsearch damped newton method for computing general equilibria. Annals of Operations Research, 211--232.

[18]

Eaves, B. C. 1985. Finite solution of pure trade markets with cobb-douglas utilities. Mathematical Programming Study 23, 226--239.

[19]

Eaves, B. C. and Scarf, H. 1976. The solution of systems of piecewise linear equations. Mathematics of Operations Research 1, 1, 1--27.

Digital Library

[20]

Eisenberg, E. 1961. Aggregation of utility functions. Management Sciences 7, 4, 337--350.

Digital Library

[21]

Esteban-Bravo, M. 2004. Computing equilibria in general equilibrium models via interior-point methods. Computational Economic 23, 147--171.

Digital Library

[22]

Ferris, M. C. and Munson, T. S. 2000a. Complementarity problems in gams and the path solver. Journal of Economic Dynamics and Control 24, 165--188.

[23]

Ferris, M. C. and Munson, T. S. 2000b. Path 4.6.

[24]

Ferris, M. C., Munson, T. S., and Ralph, D. 2000. A Homotopy Method for Mixed Complementarity Problems Based on the PATH Solver. Chapman and Hall, London. 143--167.

[25]

Garg, R. and Kapoor, S. 2004. Auction algorithms for market equilibrium. In Proceedings of the 36th Annual ACM Symposium on Theory of Computing, Chicago, IL, June 13--16, 2004. ACM, New York. 511--518.

Digital Library

[26]

Garg, R., Kapoor, S., and Vazirani, V. 2004. An auction-based market equilibrium algorithm for the separable gross substitutability case. In Proceedings of the Approximation, Randomization, and Combinatorial Optimization, Algorithms and Techniques, 7th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, APPROX 2004, and 8th International Workshop on Randomization and Computation, RANDOM 2004, Cambridge, MA, August 22--24, 2004, Springer, New York. 128--138.

[27]

Ginsburgh, V. A. and Waelbroeck, J. L. 1981. Activity Analysis and General Equilibrium Modelling. North Holland, Amsterdam.

[28]

Hansen, T. and Scarf, H. 1973. The Computation of Economic Equilibrium, Cowles Foundation Monograph No. 24. Yale University Press, New Haven.

[29]

Harker, P. and Xiao, B. 1990. Newton's method for the nonlinear complementarity problem: A b-differential equation approach. Mathematical Programming 48, 339--358.

Digital Library

[30]

Jain, K. 2004. A polynomial time algorithm for computing the arrow-debreu market equilibrium for linear utilities. In Proceedings of the 45th Annual IEEE Symposium on Foundations of Computer Science (FOCS'04). IEEE Computer Society, Los Alamitos, CA. 286--294.

Digital Library

[31]

Jain, K., Mahdian, M., and Saberi, A. 2003. Approximating market equilibria. In Proceedings of the Approximation, Randomization, and Combinatorial Optimization: Algorithms and Techniques, 6th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, APPROX 2003 and 7th International Workshop on Randomization and Approximation Techniques in Computer Science, RANDOM 2003, Princeton, NJ, August 24--26, 2003, Springer, New York. 98--108.

[32]

Kehoe, T., Srinivasan, T., and Whalley, J. 2005. Frontiers in Applied General Equilibrium Modelling. Cambridge University Press, Cambridge.

Digital Library

[33]

Mantel, R. R. 1971. The welfare adjustment process: its stability properties. International Economic Review 12, 415--430.

[34]

Mas-Colell, A., Whinston, M. D., and Green, J. R. 1995. Microeconomic Theory. Oxford University Press, Oxford.

[35]

Negishi, T. 1960. Welfare economics and existence of an equilibrium for a competitive economy. Metroeconomica 12, 92--97.

[36]

Nenakov, E. I. and Primak, M. E. 1983. One algorithm for finding solutions of the Arrow-Debreu model. Kibernetica 3, 127--128.

[37]

Newman, D. J. and Primak, M. E. 1992. Complexity of circumscribed and inscribed ellipsoid methods for solving equilibrium economical models. Applied Mathematics and Computation 52, 223--231.

Digital Library

[38]

Papadimitriou, C. 1994. On the complexity of the parity argument and other inefficient proofs of existence. Journal of Computer and System Sciences 48, 498--532.

Digital Library

[39]

Primak, M. E. 1984. An algorithm for finding a solution of the linear exchange model and the linear Arrow-Debreu model. Kibernetika 5, 76--81.

[40]

Primak, M. E. 1993. A converging algorithm for a linear exchange model. Journal of Mathematical Economics 22, 181--187.

[41]

Rutherford, T. 1995. Extensions of gams for complementarity problems arising in applied economic analysis. Journal of Economic Dynamics and Control 19, 1299--1324.

[42]

Rutherford, T. 1999a. Applied general equilibrium modeling with mpsge as a gams sybsystem: An overview of the modeling framework and syntax. Computational Economics 14, 1--46.

Digital Library

[43]

Rutherford, T. 1999b. Sequential Joint Maximization. Vol. 18. Kluwer, Boston, MA.

[44]

Samuelson, P. 1947. Foundations of Economic Analysis. Cambridge, Mass.: Harvard University Press.

[45]

Scarf, H. 1967. The approximation of fixed points of a continuous mapping. SIAM J. Applied Math 15, 1328--1343.

Digital Library

[46]

Scarf, H. 1982. The Computation of Equilibrium Prices: An Exposition. Vol. 2. 1008--1061.

[47]

Shoven, J. and Whalley, J. 1992. Applying General Equilibrium. Cambridge University Press, Cambridge.

[48]

Smale, S. 1976. A convergent process of price adjustment and global newton methods. Journal of Mathematical Economics 3, 2, 107--120.

[49]

Vanderbei, R. J. 2000. LOQO Users' Manual: Version 4.05, Technical Report.

[50]

Ye, Y. 2008. A path to the arrow-debreu competitive market equilibrium. Mathematical Programming. 111, 315--348.

Digital Library

Cited By

Prasad AArumaithurai MKoll DJiang YFu X(2019)OFM: An Online Fisher Market for Cloud ComputingIEEE INFOCOM 2019 - IEEE Conference on Computer Communications10.1109/INFOCOM.2019.8737641(2575-2583)Online publication date: 29-Apr-2019
https://dl.acm.org/doi/10.1109/INFOCOM.2019.8737641
Prasad AArumaithurai MKoll DFu X(2019)DMC: A Differential Marketplace for Cloud Resources2019 19th IEEE/ACM International Symposium on Cluster, Cloud and Grid Computing (CCGRID)10.1109/CCGRID.2019.00034(198-209)Online publication date: May-2019
https://doi.org/10.1109/CCGRID.2019.00034
Pantoja AObando GQuijano N(2019)Distributed optimization with information-constrained population dynamicsJournal of the Franklin Institute10.1016/j.jfranklin.2018.10.016356:1(209-236)Online publication date: Jan-2019
https://doi.org/10.1016/j.jfranklin.2018.10.016
Show More Cited By

Index Terms

An experimental study of different approaches to solve the market equilibrium problem

Recommendations

Market equilibrium via the excess demand function
STOC '05: Proceedings of the thirty-seventh annual ACM symposium on Theory of computing

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 ...
Auction algorithms for market equilibrium
STOC '04: Proceedings of the thirty-sixth annual ACM symposium on Theory of computing

In this paper we study algorithms for computing market equilibrium in markets with linear utility functions. The buyers in the market have an initial endowment given by a portfolio of items. The market equilibrium problem is to compute a price vector ...
Auction Algorithms for Market Equilibrium

In this paper we study algorithms for computing market equilibrium in markets with linear utility functions. The buyers in the market have an initial endowment given by a portfolio of goods. The market equilibrium problem is to compute a price vector ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Journal of Experimental Algorithmics

ACM Journal of Experimental Algorithmics Volume 12, Issue

2008

507 pages

ISSN:1084-6654

EISSN:1084-6654

DOI:10.1145/1227161

Issue’s Table of Contents

Copyright © 2008 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 29 August 2008

Accepted: 01 May 2007

Revised: 01 December 2006

Received: 01 November 2005

Published in JEA Volume 12

Author Tag

Market equilibrium

Qualifiers

Research-article
Research
Refereed

Funding Sources

National Science Foundation

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

5
Total Citations
View Citations
372
Total Downloads

Downloads (Last 12 months)8
Downloads (Last 6 weeks)0

Reflects downloads up to 29 Sep 2024

Other Metrics

View Author Metrics

Citations

Cited By

Prasad AArumaithurai MKoll DJiang YFu X(2019)OFM: An Online Fisher Market for Cloud ComputingIEEE INFOCOM 2019 - IEEE Conference on Computer Communications10.1109/INFOCOM.2019.8737641(2575-2583)Online publication date: 29-Apr-2019
https://dl.acm.org/doi/10.1109/INFOCOM.2019.8737641
Prasad AArumaithurai MKoll DFu X(2019)DMC: A Differential Marketplace for Cloud Resources2019 19th IEEE/ACM International Symposium on Cluster, Cloud and Grid Computing (CCGRID)10.1109/CCGRID.2019.00034(198-209)Online publication date: May-2019
https://doi.org/10.1109/CCGRID.2019.00034
Pantoja AObando GQuijano N(2019)Distributed optimization with information-constrained population dynamicsJournal of the Franklin Institute10.1016/j.jfranklin.2018.10.016356:1(209-236)Online publication date: Jan-2019
https://doi.org/10.1016/j.jfranklin.2018.10.016
Fleischer LGarg RKapoor SKhandekar RSaberi A(2016)A Simple and Efficient Algorithm for Computing Market EquilibriaACM Transactions on Algorithms10.1145/290537212:3(1-15)Online publication date: 13-May-2016
https://dl.acm.org/doi/10.1145/2905372
Gomes EVo QKowalczyk R(2012)Pure exchange markets for resource sharing in federated cloudsConcurrency and Computation: Practice & Experience10.1002/cpe.165924:9(977-991)Online publication date: 1-Jun-2012
https://dl.acm.org/doi/10.1002/cpe.1659

View Options

Get Access

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Article

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Issue’s Table of Contents