# «MATHEMATICS OF OPERATIONS RESEARCH Vol. 27, No. 4, November 2002, pp. 637–646 Printed in U.S.A. COMPUTING EQUILIBRIA IN FINANCE ECONOMIES P. ...»

On top of the great number of equations saved, our method also has the ﬂexibility of choosing the initial price system as desired, contrary to the homotopies of Brown et al.

(1996a) or Schmedders (1998). Since it is not too hard to make a reasonable guess for an equilibrium price system, our algorithm will generally cause a substantial reduction in the arc length of the homotopy path. Suppose that agent h is the only agent in the economy. It follows immediately from the system of ﬁrst-order conditions that the competitive equilibrium price system is given by q ∗ = h A where the so-called state price vector h is equal 644 P. J.-J. HERINGS AND F. KUBLER

to uh eh / uh eh A·J A reasonable guess for q 0 is therefore obtained by computing 0 A where 0 is the average over all the agents’ h = uh eh / uh eh A·J We implemented the algorithm using HOMPACK—a suite of FORTRAN 77 subroutines designed to solve systems of nonlinear homotopy equations with path-following methods.

See Watson (1979) and Watson et al. (1987) for details on HOMPACK.

where h is the coefﬁcient of relative risk aversion.

We set 1 = 2 2 = 4 and 3 = 6. As long as coefﬁcients of relative risk aversion stay relatively small (below 8), the actual choice of these coefﬁcients has only small effects on running times.

In order to examine how running times change with the number of agents, the number of assets and the number of states, we consider the following speciﬁcations: An example with two agents and ﬁve assets, an example with two agents and eight assets, an example with three agents and ﬁve assets, and an example with three agents and eight assets. For each example, we consider the case of 10,000 states, 20,000 states, 30,000 states and 40,000 states.

In order to specify state contingent asset payoffs and individual endowments, we generate random numbers. We take individual endowments to be drawn from a uniform distribution on [1, 10] and dividends to be drawn from a uniform distribution on [0.1, 5].

For each of the 16 examples we compute equilibria for 100 different draws, and we report average running times.

Table 1 shows the running times in minutes. All running times refer to an implementation in FORTRAN 77 on a 500-MHz Pentium III processor running Red Hat Linux.

Since we subsitute for market clearing, we obtain that solving for an equilibrium involves solving a system of H J + 1 nonlinear system. The number of equations is independent of the number of states. Note that the running times do increase signiﬁcantly with the number of states, since the time needed for a single evaluation of the ﬁrst-order conditions increases. The increase is more or less linear in the number of states. If the number of states would increase the number of equations, running times in this order of magnitude would be impossible.

## COMPUTING EQUILIBRIA IN FINANCE ECONOMIES

A central idea underlying our homotopy algorithm is that it is not necessarily desirable to have a high precision along the path. This is consistent with the general idea underlying HOMPACK. Watson et al. (1987) point out that tracking the homotopy path is “merely a means to an end”—ﬁnding the solution to H · 1 = 0—and that no computational effort should be wasted following the path too closely. However, if one sets the error tolerance along the path incorrectly (e.g., too large), the algorithm is likely to lose the right path.In Table 1, the relative tracking tolerance is set to 5 · 10−5. HOMPACK allows the user to independently set the relative error tolerance at the solution, for the table we set this tolerance to 10−9. While the effect of different error tolerances at the solution on running times is not signiﬁcant, the relative tracking tolerance inﬂuences error times substantially.

If this error tolerance is set to 10−3 the algorithm does not converge for all examples considered. When it does converge (approximately 80% of all draws), running times are reduced by a factor of 1.5. If the error is set to a value of 10−7, average running times increase by a factor of 2.

7. Conclusion. In this paper, we develop a homotopy algorithm to compute equilibria in the ﬁnance version of the GEI model that is particularly useful for cases with a large state space. The generic convergence of this algorithm is shown, where “generic” means that for an open set of ﬁnance economies with full Lebesgue measure, convergence takes place.

The implementation of the algorithm is discussed. Its effectiveness is veriﬁed by means of numerical examples. In Herings and Kubler (2000), the algorithm is used to explore asset pricing implications of the GEI model when the number of states is large.

Acknowledgments. The research of Jean-Jacques Herings has been made possible by a fellowship of the Royal Netherlands Academy of Arts and Sciences and a grant from the Netherlands Organization for Scientiﬁc Research (NWO). While this paper was being written, this author enjoyed the generous hospitality of the Cowles Foundation for Research in Economics at Yale University and of CORE at Université Catholique de Louvain.

Felix Kubler gratefully acknowledges the ﬁnancial support of an Anderson Dissertation Fellowship.

## References

Allgower, E. L., K. Georg. 1990. Numerical Continuation Methods: An Introduction. Springer Verlag, New York.Brown, D. J., P. M. DeMarzo, B. C. Eaves. 1996a. Computing equilibria when asset markets are incomplete.

Econometrica 64 1–27.

,,. 1996b. Computing zeros of sections of vector bundles using homotopies and relocalization. Math. Oper. Res. 21 26–43.

Davidenko, D. 1953. On a new method of numerical solution of systems of nonlinear equations. Doklady Akad.

Nauk USSR 88 601–602.

DeMarzo, P. M., B. C. Eaves. 1996. Computing equilibria of GEI by relocalization on a Grassmann manifold. J.

Math. Econom. 26 479–497.

Doup, T. M., G. van der Laan, A. J. J. Talman. 1987. The 2n+1 − 2 -ray algorithm: A new simplicial algorithm to compute economic equilibria. Math. Programming 39 241–252.

Eaves, B. C. 1972. Homotopies for computation of ﬁxed points. Math. Programming 3 1–22.

, K. Schmedders. 1999. General equilibrium models and homotopy methods. J. Econom. Dynam. Control 23 1249–1279.

Garcia, C., W. Zangwill. 1981. Pathways to Solutions, Fixed Points, and Equilibria. Prentice Hall, Englewood Cliffs, NJ.

Geanakoplos, J. D., H. M. Polemarchakis. 1986. Existence, regularity, and constrained suboptimality of competitive allocations when the asset market is incomplete. W. P. Heller, R. M. Starr, D. A. Starrett, eds. Uncertainty, Information and Communication: Essays in Honor of K. J. Arrow, Vol. III. Cambridge University Press, Cambridge, U.K., 65–96.

Hens, T. 1991. Structure of general equilibrium models with incomplete markets. Doctoral dissertation, University of Bonn.

Herings, P. J. J. 1997. A globally and universally stable price adjustment process. J. Math. Econom. 27 163–193.

Herings, P. J. J., F. Kubler. 2000. The robustness of CAPM—A computational approach. METEOR Research Memorandum 00/02, University of Maastricht, Maastricht, The Netherlands, 1–34.

646 P. J.-J. HERINGS AND F. KUBLER Hirsch, M. W. 1963. A proof of the nonretractibility of a cell onto its boundary. Proc. Amer. Math. Soc. 14 364–365.

Judd, K. L. 1998. Numerical Methods in Economics. MIT Press, Cambridge, U.K.

Kellogg, R. B., T. Y. Li, J. Yorke. 1976. A constructive proof of the Brouwer ﬁxed-point theorem and computational results. SIAM J. Numer. Anal. 13 473–483.

Lahaye, E. 1934. Une méthode de résolution d’une catégorie d’équations transcendantes. C. R. Acad. Sci. Paris 198 1840–1842.

Mas-Colell, A. 1985. The Theory of General Economic Equilibrium: A Differentiable Approach. Cambridge University Press, Cambridge, U.K., 45.

Scarf, H. 1967. The approximation of ﬁxed points of a continuous mapping. SIAM J. Appl. Math. 15 1328–1343.

Schmedders, K. 1998. Computing equilibria in the general equilibrium model with incomplete asset markets. J.

Econom. Dynam. Control 22 1375–1401.

Watson, L. T. 1979. A globally convergent algorithm for computing ﬁxed points of C2 maps. Appl. Math. Comput.

5 297–311.

, S. C. Billups, A. P. Morgan. 1987. HOMPACK: A suite of codes for globally convergent homotopy algorithms. ACM Trans. Math. Software 13 281–310.

P. J. J. Herings: Department of Economics, Universiteit Maastricht, PO Box 616, 6200 MD Maastricht, The Netherlands; e-mail: p.herings@algec.unimaas.nl

**F. Kubler, Department of Economics, Stanford University, Stanford, California 94305-6072; e-mail:**