Skip to article content

EGMⁿ: The Sequential Endogenous Grid Method

EGM to the power of n

Appendix: Proofs

Notation. In the proofs below, subscripts on value functions denote partial derivatives (e.g., vlH12v1/lHv^1_{\lRat\HRat} \equiv \partial^2 v^1/\partial \lRat \partial \HRat). Superscripts serve two roles: on stage-numbered functions (v1,v2v^1, v^2), superscripts are stage labels and subscripts always denote partials; on w\wFunc, which carries no stage number, superscripts denote partial derivatives directly (waw/a\wFunc^\aRat \equiv \partial \wFunc/\partial \aRat, waH2w/aH\wFunc^{\aRat\HRat} \equiv \partial^2 \wFunc/\partial \aRat \partial \HRat). This follows the convention in the main text (Section 3).

1Proof of Grid Homeomorphism Theorem

2Proof of EGM Regularity Theorem

3Proof of ENGINE Complexity

4ENGINE Algorithm

The algorithm uses subscripts ll, mm, hh for low, mid, and high indices respectively. Pass 1 performs binary search over rows to find the bounding row band [kl,kh][k_l, k_h] satisfying y^ly<y^h\hat{y}_l \leq y^* < \hat{y}_h. Each probe at row kk finds the column bracket jj such that xjkx<xj+1,kx_{jk} \leq x^* < x_{j+1,k}, then interpolates y^\hat{y} along that row. The IPO property bounds the bracket search range at each probe: consecutive probes have brackets within α\alpha positions of each other, so binary search within the constrained window costs O(logJ)O(\log J) per probe in the worst case. Pass 2 interpolates function values at the bounding rows and combines them linearly.

For query points outside the grid domain, ENGINE performs linear extrapolation by extending boundary slopes. Each 1D interpolation step handles out-of-bounds queries by using the slope between the two nearest boundary points, ensuring continuous extension of the approximation beyond the grid’s convex hull.

EGM applications require extrapolation: simulation may occasionally produce state values slightly outside the solution grid due to shock realizations or numerical precision. The extrapolation extends boundary slopes: for x<x1x^* < x_1, the value is f1+(xx1)(f2f1)/(x2x1)f_1 + (x^* - x_1)(f_2 - f_1)/(x_2 - x_1), and symmetrically for x>xJx^* > x_J. Extrapolation reliability depends critically on grid placement. Near binding constraints, policy functions exhibit high curvature or kinks, making linear extrapolation unreliable. In wealth-rich regions, by contrast, policies typically become smooth and approximately linear as precautionary motives diminish and consumption approaches permanent income rules. Standard practice therefore extends the asset grid well beyond the constraint region, typically to several multiples of target wealth (steady-state assets), ensuring that (i) interpolation handles the economically relevant constrained region exactly, and (ii) any extrapolation occurs only in the smooth unconstrained region where linear approximation is accurate. Extrapolation to economically invalid regions (e.g., negative assets when borrowing is constrained) produces meaningless results regardless of smoothness.

Footnotes
  1. By the envelope theorem, (v1)l=wa(v^1)^\lRat = \wFunc^\aRat and (v1)H=wH(v^1)^\HRat = \wFunc^\HRat, so vlH1=/H[wa(a(l,H),H)]=waH+waaa/Hv^1_{\lRat\HRat} = \partial/\partial \HRat[\wFunc^\aRat(\aRat^*(\lRat,\HRat), \HRat)] = \wFunc^{\aRat\HRat} + \wFunc^{\aRat\aRat}\partial\aRat^*/\partial\HRat, where superscripts on w\wFunc denote partial derivatives. The first term waH0\wFunc^{\aRat\HRat} \geq 0 reflects health raising the return to saving through higher future income. The second term involves waa<0\wFunc^{\aRat\aRat} < 0 (concavity in assets) multiplied by a/H\partial\aRat^*/\partial\HRat, the response of optimal savings to health. The sign of this cross-partial depends on the balance of these two terms; we impose vlH10v^1_{\lRat\HRat} \geq 0 as an assumption rather than deriving it from primitives.

References
  1. Knupp, P. M. (1999). Winslow Smoothing on Two-Dimensional Unstructured Meshes. Engineering with Computers, 15(3), 263–268. 10.1007/s003660050021