3.1.1 Methods Based on the Euler Equations

Simple Markov equilibria are characterized by continuous functions that satisfy

(19)

(20)

for all . Of course, in the absence of an analytical solution the system must be solved by numerical approximations.

As mentioned above, two basic approaches are typically used to obtain approximate functions . Perturbation methods—pioneered by Judd and Guu (1997)—take a Taylor approximation around a point with known solution or quite close to the exact solution. This point typically corresponds to the deterministic steady state of the model, that is, an equilibrium where for all . Projection methods—developed by Judd (1992)—aim instead at more global approximations. First, a finite-dimensional space of functions is chosen that can approximate arbitrarily well continuous mappings. Common finite-dimensional spaces include finite elements (tent maps, splines, polynomials defined in small neighborhoods), or global bases such as polynomials or other functions defined over the whole domain . Second, let be elements of this finite-dimensional space evaluated at the nodal points defining these functions. Then, nodal values are obtained as solutions of non-linear systems conformed by equations (19) and (20) evaluated at some pre determined points of the state space . It is assumed that this non-linear system has a well-defined solution—albeit in most cases the existence of the solution is hard to show. And third, rules for the optimal placement of such pre determined points exist for some functional basis; e.g., Chebyshev polynomials that have some regular orthogonality properties could be evaluated at the Chebyshev nodes in the hope of minimizing oscillations.

3.1.2 Dynamic Programming

For economies satisfying the conditions of the second welfare theorem, equilibria can be computed by an optimization problem over a social welfare function subject to aggregate feasibility constraints. Then, one can find prices that support the planner’s allocation as a competitive equilibrium with transfer payments. A competitive equilibrium is attained when these transfers are equal to zero. Therefore, we need to search for the appropriate individual weights in the social welfare function in order to make these transfers equal to zero.

Matters are simplified by the principle of optimality: the planner’s intertemporal optimization problem can be summarized by a value function satisfying Bellman’s functional equation

(21)

Here, is the intertemporal discount factor, is the one-period return function, and is a correspondence that captures the feasibility constraints of the economy. Note that our vectors and now refer to allocations only, while in previous decentralized models these vectors may include prices, taxes, or other variables outside the planning problem.

Value function is therefore a fixed point of Bellman’s equation (21). Under mild regularity conditions (cf., Stokey et al., 1989) it is easy to show that this fixed point can be approximated by the following DP operator. Let be the space of bounded functions. Then, operator is defined as

(22)

Operator is actually a contraction mapping with modulus . It follows that is a unique solution of the functional equation (21), and can be found as the limit of the sequence recursively defined by for an arbitrarily given initial function . This iterating procedure is called the method of successive approximations, and operator is called the DP operator.

By the contraction property of the DP operator, it is possible to construct reliable numerical algorithms discretizing (22). For instance, Santos and Vigo-Aguiar (1998) establish error bounds for a numerical DP algorithm preserving the contraction property. The analysis starts with a set of piecewise-linear functions defined over state space X on a discrete set of nodal points with grid size . Then, a discretized version of operator is obtained by solving the optimization problem (22) at each nodal point. For piecewise-linear interpolation, operator is also a contraction mapping. Hence, given any grid size , and any initial value function the sequence of functions converges to a unique solution . Moreover, the contraction property of operator can help bound the distance between such limit , and the application of this operator, . Finally, it is important to remark that this approximation scheme will converge to the true solution of the model as the grid size goes to zero; that is, will be sufficiently close to the original value function for some small —as a matter of fact, convergence is of order . Of course, once a numerical value function has been secured it is easy to obtain good approximations for our equilibrium functions from operator .

What slows down the DP algorithm is the maximization process at each iteration. Hence, functional interpolation—as opposed to discrete functions just defined over a set of nodal points—facilitates the use of some fast maximization routines. Splines and high-order polynomials may also be operative but these approximations may damage the concavity of the computed functions; moreover, for some interpolations there is no guarantee that the discretized operator is a contraction. There are other procedures to speed up the maximization process. Santos and Vigo-Aguiar (1998) use a multigrid method which can be efficiently implemented by an analysis of the approximation errors. Another popular method is policy iteration—contrary to popular belief this latter algorithm turns out to be quite slow for very fine grids (Santos and Rust, 2004).

3.2.1 Accuracy of Equilibrium Functions

Suppose that we come up with a pair of numerical approximations . Is there a way of assessing the magnitude of the approximation error without actual knowledge of the solution of the model: ?

To develop intuition on key ideas behind existing accuracy tests, let us define the Euler equation residuals for functions as

(23)

(24)

Note that an exact solution of the model will have Euler equation residuals equal to zero at all possible values of the state . Hence, “small” Euler equation residuals should indicate that the approximation error is also “small.” The relevant question, of course, is what we mean by “small.” Furthermore, we are circumventing other technical issues since first-order conditions may not be enough to characterize optimal solutions.

Den Haan and Marcet (1994) appeal to statistical techniques and propose testing for orthogonality of the Euler equation residuals over current and past information as a measure of accuracy. Since orthogonal Euler equation residuals may occur in spite of large deviations from the optimal policy, Judd (1992) suggests to evaluate the size of the Euler equation residuals over the whole state space as a test for accuracy. Moreover, for strongly concave infinite-horizon optimization problems Santos (2000) demonstrates that the approximation error of the policy function is of the same order of magnitude as the size of the Euler equation residuals, and the constants involved in these error bounds can be related to model primitives.

These theoretical error bounds are based on worse-case scenarios and hence they are usually not optimal for applied work. In some cases, researchers may want to assess numerically the approximation errors in the hope of getting more operative estimates (cf. Santos, 2000). Besides, for some algorithms it is possible to derive error bounds from their approximation procedures. This is the case of the DP algorithm (Santos and Vigo-Aguiar, 1998) and in some models with quadratic-linear approximations (Schmitt-Grohe and Uribe, 2004).

The logic underlying numerical estimation of error bounds from the Euler equation residuals goes as follows (Santos, 2000). We start with a model under a fixed set of parameter values. Then, Euler equation residuals are computed for several numerical equilibrium functions. We need sufficient variability in these approximations in order to obtain good and robust estimates. This variability is obtained by considering various approximation spaces or by changing the grid size. Let be the approximation with the lowest Euler equation residuals, which would be our best candidate for the true policy function. Then, for each available numerical approximation we compute the approximation constant

(25)

Here, is the max norm in the space of functions. From the available theory (cf. Santos, 2000), the approximation error of the policy function is of the same order of magnitude as that of the Euler equation residuals. Then, the values of should have bounded variability (unless the approximation is very close to ). Indeed in many cases hovers around certain values. Hence, any upper bound for these values would be a conservative estimate for the constant involved in these error estimates. It follows that the resulting assessed value, , can be used to estimate an error bound for our candidate solution:

(26)

Note that in this last equation we contemplate the error between our best policy function and the true policy function .

Therefore, worst-case error bounds are directly obtained from constants given by the theoretical analysis. These bounds are usually very conservative. Numerical estimation of these bounds should be viewed as a heuristic procedure to assess the actual value of the bounding constant. From the available theory we know that the error of the equilibrium function is of the same order of magnitude as the size of the Euler equation residuals. That is, the following error bound holds:

(27)

We thus obtain an estimate for constant from various comparisons of approximated equilibrium functions.

3.2.2 Accuracy of the Simulated Moments

Researchers usually focus on long-run properties of equilibrium time series. The common belief is that equilibrium orbits will stabilize and converge to a stationary distribution. Stationary distributions are simply the stochastic counterparts of steady states in deterministic models. Computation of the moments of an invariant distribution for a non-linear model is usually a rather complicated task—even for analytical equilibrium functions. Hence, laws of large numbers are invoked to compute the moments of an invariant distribution from the sample moments.

The above one-period approximation error (27) is just a first step to control the cumulative error of numerical simulations. Following Santos and Peralta-Alva (2005), our goal now is to present some regularity conditions so that the error from the simulated statistics converges to zero as the approximated equilibrium function approaches the exact equilibrium function. The following example illustrates that certain convergence properties may not always hold.

Let us now perturb slightly so that the new stochastic matrix is the following

As , the sequence of stochastic matrices converges to

Hence, is the only possible long-run distribution for the system. Moreover, is a transient state, and is the only ergodic set. Consequently, a small perturbation on a transition probability may lead to a pronounced change in its invariant distributions. Indeed, small errors may propagate over time and alter the existing ergodic sets.

Santos and Peralta-Alva (2005) show that certain continuity properties of the policy function suffice to establish some generalized laws of large numbers for numerical simulations. To provide a formal statement of their results, we need to lay down some standard concepts and terminology.

For ease of presentation, we restrict attention to exogenous stochastic shocks of the form

where is an iid shock. The distribution of this shock is denoted by probability measure on a measurable space . Then, as it is standard in the literature (cf. Stokey et al., 1989) we define a new probability space comprising all infinite sequences . Let be the countably infinite Cartesian product of copies of E. Let be the -field in generated by the collection of all cylinders where for . A probability measure can be constructed over the finite-dimensional sets as

Measure has a unique extension on . Hence, the triple denotes a probability space. Now, for every initial value and sequence of shocks , let be the sample paths generated by the policy functions , so that for all .

Let be the sample path generated from an approximate policy function . Averaging over these sample paths we get sequences of simulated statistics as defined by some function . Let be the expected value under an invariant distribution of the original equilibrium function . Santos and Peralta-Alva (2005) establish the following result:

Therefore, for a sufficiently good numerical approximation and for a sufficiently large the sequence approaches (almost surely) the expected value of the invariant distribution of the original equilibrium function .

Note that this theorem does not require uniqueness of the invariant distribution for each numerical policy function. This requirement would be rather restrictive: numerical approximations may contain multiple steady states. For instance, consider a polynomial approximation of the policy function. As is well understood, the fluctuating behavior of polynomials may give rise to several ergodic sets. But according to the theorem, these multiple distributions from these approximations will eventually be close to the unique invariant distribution of the model. Moreover, if the model has multiple invariant distributions, then there is an extension of Theorem 1 in which the simulated statics of computed policy functions become close to those of some invariant distribution of the model for large enough [see . .].

The existence of an invariant distribution is guaranteed under the so-called Feller property (cf. Stokey et al., 1989). The Feller property is satisfied if equilibrium function is a continuous mapping on a compact domain or if the domain is made up of a finite number of points. (These latter stochastic processes are called Markov chains.) There are several extensions of these results to non-continuous mappings and non-compact domains (cf. Futia, 1982; Hopenhayn and Prescott, 1992; Stenflo, 2001). These papers also establish conditions for uniqueness of the invariant distribution under mixing or contractive conditions. The following contraction property is taken from Stenflo (2001): CONDITION C: There exists a constant such that for all pairs .

Condition C may arise naturally in growth models [Schenk-Hoppe and Schmalfuss (2001)], in learning models (Ellison and Fudenberg, 1993), and in certain types of stochastic games (Sanghvi and Sobel, 1976).

Using Condition C, the following bounds for the approximation error of the simulated moments are established in Santos and Peralta-Alva (2005). A real-valued function on is called Lipschitz with constant if for all pairs and .

Again, this is another application of the contraction property, which becomes instrumental to substantiate error bounds. Stachurski and Martin (2008) study a Monte Carlo algorithm for computing densities of invariant measures and establish global asymptotic convergence as well as error bounds.

3.3.1 Calibration

Faced with these complex analytical problems, the economics literature has come up with many simplifying approaches for model estimation. Starting with the real business cycle literature (e.g., Cooley and Prescott, 1995), parameter values are often determined from independent evidence or from other parts of the theory not related to the basic facts selected for testing. This is loosely referred to as model calibration. Christiano and Eichembaum (1992) is a good example of this approach. They consider a business cycle model, and pin down parameter values from various steady-state conditions. In other words, the model is evaluated according to business cycle predictions, and it is calibrated to replicate empirical properties of balanced growth paths. As a matter of fact, Christiano and Eichembaum (1992) are able to provide standard errors for their estimates, and hence their analysis goes beyond most calibration exercises.

3.3.2 Simulation-Based Estimation

The aforementioned limitations of traditional estimation methods for non-linear systems along with advances in computing have fostered the more recent use of estimation and testing based upon simulations of the model. Estimation by model simulation offers more flexibility to evaluate the behavior of the model by computing statistics of its invariant distributions that can be compared with their data counterparts. But this greater flexibility inherent in simulation-based estimators entails a major computational cost: extensive model simulations may be needed to sample the entire parameter space. Relatively little is known about the family of models in which simulation-based estimators would have good asymptotic properties such as consistency and normality. These properties would seem a minimal requirement for a rigorous application of estimation methods under the rather complex and delicate techniques of numerical simulation in which approximation errors may propagate in unexpected ways.

To fix ideas, we will focus on a simulated moments estimator (SME) put forward by Lee and Ingram (1991). This estimation method allows the researcher to assess the behavior of the model along various dimensions. Indeed, the conditions characterizing the estimation process may involve some moments of the model’s invariant distributions or some other features of the dynamics on which the desired vector of parameters must be selected.

Several elements conform the SME. First, one specifies a target function or function of interest which typically would characterize a selected set of moments of the invariant distribution of the model and those of the data generating process. Second, a notion of distance is defined between the selected statistics of the model and its data counterparts. The minimum distance between these statistics is attained at some vector of parameters in a space . Then, the estimation method yields a sequence of candidate solutions over increasing finite samples of the model simulations and data so as to approximate the true value .

We assume that the sequence of continuous functions converges uniformly to function for -almost all , and the sequence of functions goes to for -almost all . Note that both functions and are allowed to depend on the sequence of random shocks and data , and is a measure defined over and . These functions will usually depend on all information available up to time . The rule reflects that the length of model’s simulations may be different from that of data samples.

It should be stressed that problem (31) is defined over population characteristics of the model and of the data-generating process, whereas problem (33) is defined over statistics of finite simulations and data.

By the measurable selection theorem (Crauel, 2002) there exists a sequence of measurable functions . See Duffie and Singleton (1993) and Santos (2010) for asymptotic properties of this estimator. Sometimes vector could be estimated independently, and hence we could then try to get an SME estimate of . This mixed procedure can still recover consistency and it may save on computational cost. Consistency of the estimator can also be established for numerical approximations: the SME would converge to the true value as the approximation error goes to zero.

Another route to estimation is via the likelihood function. The existence of such functions imposes certain regularity conditions on the dynamics of the model which are sometimes hard to check. Fernandez-Villaverde and Rubio-Ramirez (2007) propose computation of the likelihood function by a particle filter. Numerical errors of the computed solution will also affect the likelihood function and the estimated parameter values (see Fernandez-Villaverde et al., 2006). Recent research on dynamic stochastic general equilibrium models has made extensive use of Monte Carlo methods such as the Markov Chain Monte Carlo method and the Metropolis-Hastings algorithm (e.g., Fernandez-Villaverde, 2012).

4.1.1 A Growth Model with Taxes

Consider the following parameterization for the growth model with taxes of Section 2:

Assume that income taxes are only imposed on households’ capital income. More specifically, this form of taxation is determined by the following piecewise-linear schedule:

Santos (2002, Prop. 3.4) shows that a continuous Markov equilibrium fails to exist. For this specification of the model, there are three steady states: the middle steady state is unstable and has two complex eigenvalues while the other two steady states are saddle-path stable; see Figure 1. Standard algorithms approximating the Euler equation would solve for a continuous policy function of the form

where belongs to a finite-dimensional space of continuous functions as defined by a vector of parameters . We obtain an estimate for by forming a discrete system of Euler equations over as many grid points as the dimensionality of the parameter space:

We assume that belongs to the class of piecewise-linear functions, and employ a uniform grid of 5000 points over the domain . The resulting approximation, together with a highly accurate solution (in this case the shooting algorithm can be implemented), is illustrated in Figure 1.

This approximation of the Euler equation over piecewise-continuous functions converged up to computer precision in only three iterations. This fast convergence is actually deceptive because as pointed out above no continuous policy function does exist. Indeed, the dynamic behavior implied by the continuous function approximation is quite different from the true one. As a matter of fact, the numerical approximation displays four more steady states, and changes substantially the basins of attraction of the original steady states (see Figure 1).

A further test of the fixed-point solution of this algorithm based on the Euler equation residuals produced mixed results (see Figure 2). First, the average Euler equation residual over the domain of feasible capitals is fairly small, i.e., it is equal to 0.0073. Second, the maximum Euler equation residual is slightly more pronounced in a small area near the unstable steady state. But even in that area, the error is not extremely large: in three tiny intervals the Euler equation residuals are just around 0.06. Therefore, from these computational tests a researcher may be led to conclude that the putative continuous solution should mimic well the true equilibrium dynamics.

4.1.2 An Overlapping Generations Economy

Consider the following specification for the overlapping generations economy presented in Section 2. There are two perishable commodities, and two types of agents that live for two periods. There is no Lucas tree. In the first period of life of each agent, endowments are stochastic and depend only on the current state , while in the second period they are deterministic. In particular, , if , and , if , while and .

The utility function of an agent of type 1 is given by

while that of agent of type 2 is given by

For this model, it is easy to show that a competitive equilibrium exists. Practitioners are, however, interested in competitive equilibria that have a recursive structure on the space of shocks and wealth distributions. Specifically, standard computational methods search for a Markovian equilibrium on the natural state space. Hence, let us consider that there exists a continuous function such that equilibrium allocations can be characterized by:

Kubler and Polemarchakis (2004) show that such a representation does not exist for this economy. Specifically, the unique equilibrium of this economy is described by:

Observe that knowledge of the current shock and wealth distribution is not enough to characterize consumption of the old.

As in our previous example, and in spite of realizing that a recursive equilibrium on the natural state space does not exist, we applied the projection method to obtain a numerical approximation to function . We employed a grid of 100 equally spaced points under piecewise-linear interpolation, and assumed . Based on this approach, we ended up with an approximated policy function with Euler equation residuals of order (on average). We again find that the time series properties of the approximated policy may be substantially different from the equilibrium dynamics. As a simple illustration, consider Figures 3 and 4. These figures summarize portfolio holdings and the relative price of good two, respectively. In equilibrium bond holdings should equal zero, while the approximate policy yields positive values. Similarly, the relative price of good 2 should equal either 1 or 7.9, depending on the shock, while it takes a continuum of values ranging from 6.5 to 9 in the approximate policy. To further illustrate the differences between approximate and exact solutions, Table 1 reports a simulated sample for the exact and approximate solutions over the same sequence of shocks in a sample path of 10,000 periods.

In summary, for non-optimal economies standard solution methods may introduce substantial biases into our quantitative predictions.

4.2.1 The Theoretical Algorithm

A fundamental element of this approach is operator . An iterative procedure based on this operator converges to the equilibrium correspondence . This equilibrium correspondence is defined as the set of possible equilibrium values for , given . As illustrated presently, once the equilibrium correspondence has been secured, we can provide a recursive representation of equilibria on the enlarged state .

Let be any initial node, and be the set of immediate successor states. For convenience of computation, this set is assumed to be finite. Pick any correspondence , where is the set of possible shadow values of investment. Then, for each , we define operator as the set of all values with the property that there are current endogenous variables , and vectors and for each of the successors of , denoted by , that satisfy the temporary equilibrium conditions

The following result is proved in Feng et al. (2012):

Theorem 3 provides the theoretical foundations for computing equilibria for non-optimal economies. Specifically, this result states that operator can be applied to any initial guess (correspondence) of possible values and iterate until a desirable level of convergence to is attained. From operator we can select a measurable policy function , and a transition function , for all . These functions may not be continuous but the state space has been adequately chosen so that they yield a Markovian characterization of a dynamic equilibrium in the enlarged state space . An important advantage of this approach is that if multiple equilibria exist then all of them can be computed. If the equilibrium is always unique, then defines a continuous law of motion or Markovian equilibrium over state variables .

4.2.2 Numerical Implementation

We first partition the state space into a finite set of simplices with non-empty interior and maximum diameter . Over this partition define a family of step correspondences (defined as correspondences that take constant set values over each ). To obtain a computer representation of a step correspondence, the image must be discretized. We can employ an outer approximation in which each set value is defined by elements. Using these two discretizations we obtain a computable approximation of operator , which we denote by . By a suitable selection of an initial condition and of these outer approximations, the sequence defined recursively as converges to a limit point , which must contain the equilibrium correspondence . Again, if the equilibrium is always unique then these approximate solutions would converge uniformly to the continuous Markovian equilibrium law of motion. The following result is proved in Feng et al. (2012):

It should be stressed that we lack a theory of error bounds for non-optimal economies. Nevertheless, Theorem 4 establishes a strong form of uniform convergence. Moreover, under certain regularity conditions the analysis of Kubler and Schmedders (2005) implies that for an approximate equilibrium one can construct some nearby economy so that this equilibrium becomes exact. Kubler (2011) introduces some analytical conditions under which an -equilibrium is close to an exact equilibrium.

(i) : Transition correspondence has an invariant probability ; this invariant distribution is constructed as a limit of a sequence of empirical measures using a Krylov-Bogoliouboff type argument. This iterative process is extended to stochastic dynamical systems described by correspondences, and it works when the space of measures is compact and the equilibrium correspondence is upper semicontinuous.

(ii) . These laws of motion are obtained under operator . There are tight upper and lower bounds such that with probability one the corresponding moments from simulated paths of these approximate functions stay within the prescribed bounds. More precisely, let and be a function of interest. Let represent a simulated moment or some other statistic. Then, with probability one, every limit point of must be within the corresponding bounds and .

(iii) : For every we can consider a sufficiently good discretized operator and equilibrium correspondence such that for every simulated path there are equilibrium invariant distributions satisfying almost surely. Of course, the model has a unique invariant distribution then and the above expression reads as .

5.2.1 An Overlapping Generations Model

We now rewrite the OLG economy of Section 2 along the lines of the classical monetary models of Benhabib and Day (1982) and Grandmont (1985). This version of the model is useful for illustrative purposes because it can be solved with arbitrary accuracy. Hence, we can compare the true solution of the model with alternative numerical approximations. The model is deterministic. There are two agents that live for two periods (except for the initially old agent, who only lives for one period). Each individual receives an endowment of the perishable good when young and when old. There is a single asset, money, that pays zero dividends at each given period. The initial old agent is endowed with the existing money supply . Let be the price level at time . An agent born in period solves:

subject to

Equilibria can be characterized by the following first-order condition:

Let be real money balances at . Then,

It follows that all competitive equilibria can be generated by an offer curve in the space. A simple recursive equilibrium would be described by a function . We focus on the following parameterization:

In this case, the offer curve is backward bending (see Figure 5). Hence, the equilibrium correspondence is multivalued. Therefore, standard methods—based on the computation of a continuous equilibrium function —may portray a partial view of the equilibrium dynamics. There is a unique stationary solution at about , which is the point of crossing of the offer curve with the 45° line.

5.2.2 Asset-Pricing Models with Market Frictions

An important family of macroeconomic models incorporates financial frictions in the form of sequentially incomplete markets, borrowing constraints, transactions costs, cash-in-advance constraints, and margin and collateral requirements. Fairly general conditions rule out the existence of financial bubbles in these economies; hence, equilibrium asset prices are determined by the expected value of future dividends (Santos and Woodford, 1997). There is, however, no reliable algorithm for the numerical approximation and simulation of these economies. Here, we illustrate the workings of our algorithm in the economy of Kehoe and Levine (2001). These authors provide a characterization of steady-state equilibria for an economy with idiosyncratic risk under exogenous and endogenous borrowing constraints.

The basic economic environment stems from the asset-pricing model of Section 2. There are two possible values for the endowment, high, , or low, . There is no aggregate risk: one household gets the high endowment while the other one gets the low endowment at every date. There is only one asset, a Lucas tree with a constant dividend, . Households maximize expected utility (7) subject to the sequence of budget constraints (8). We now consider an important departure from the basic model of Section 2: endogenous credit limits. More specifically, allocations (and the implied borrowing) must satisfy the participation constraint

(35)

Here, denotes the expected discounted value of making consumption equal to the endowment from period onwards. This is the payoff of defaulting on credit obligations. The algorithm of Section 4 can be readily modified to accommodate this type of constraint. It simply requires iterating simultaneously on pairs of candidate shadow values of investment and values for participation (the lifetime utility of never defaulting). This operator is monotone (in the set inclusion sense) and thus the approximation results of Section 4 still hold (see Feng et al., 2012).