EGMⁿ: The Sequential Endogenous Grid Method

1Introduction¶

Solving heterogeneous agent models with multiple decisions has traditionally required nested optimization, which is slow, or restrictive assumptions about preferences that limit economic relevance. Models featuring idiosyncratic risk, borrowing constraints, and rich household heterogeneity in the tradition of Aiyagari (1994) and Huggett (1993) have become central to macroeconomic analysis Krueger et al., 2016. The Endogenous Grid Method transformed computation of consumption-savings problems by inverting first-order conditions, but extending this insight to problems with multiple continuous choices and high-dimensional state spaces has proved difficult, with earlier attempts requiring either full triangularity of the FOC system Iskhakov, 2015 or hybrid methods that embed optimization within EGM loops Druedahl & Jørgensen, 2017.^[1]

A household choosing consumption, labor, and portfolio allocation makes these decisions based on the same information, but the computational problem can be decomposed into sequential stages. This paper shows how to structure such decompositions so that most stages admit an EGM inversion, with remaining stages solved by reduced-dimension optimization, accumulating efficiency gains across decisions.

1.1Background and literature¶

Dynamic heterogeneous agent models require solving high-dimensional optimization problems at each point in a potentially large state space. Standard grid search approaches impose real computational costs: a three-choice problem with $N$ grid points per dimension requires $O(N^3)$ evaluations per state, and this cost multiplies across all state space points.^[2] Carroll (2006) introduced the Endogenous Grid Method (EGM) to accelerate solution of dynamic stochastic consumption-savings problems. Starting from a grid of post-decision states, EGM inverts the first-order condition to recover the optimal consumption policy and the corresponding pre-decision state, converting problems that required hours of computation into tractable exercises. Originally restricted to models with a single control and state variable, EGM was extended by Barillas & Fernández-Villaverde (2007) to multiple controls (labor-leisure choice) in a neoclassical growth model, and subsequent work expanded its applicability further.^[3]

The decade after Carroll’s original method saw EGM’s scope broaden along two fronts: handling structural complications (non-convexities, constraints, discrete choices) and scaling to multidimensional problems.

On the structural side, handling non-convexities and constraints required new techniques. The Generalized Endogenous Grid Method (GEGM) of Fella (2014) relaxes continuity requirements by evaluating candidate solutions from first-order conditions in overlapping regions. Occasionally binding constraints among endogenous variables, as in durable goods models with collateral requirements, were addressed by Hintermaier & Koeniger (2010). Building on both advances, Druedahl & Jørgensen (2017) introduce G2EGM, which extends the generalized approach to multiple controls and states.

Discrete choices and non-standard preferences posed different challenges. How should EGM handle jumps between discrete alternatives? Iskhakov et al. (2017) incorporate discrete choices through extreme value errors, though their application remains restricted to single control and state variables; Clausen & Strub (2020) formalize the conditions under which this works and analyze nested solution approaches. On the preference side, Hallengreen et al. (2024) develop iEGM, extending EGM to utility functions lacking closed-form inverse marginal utility by using numerical inversion. Monte Carlo evidence from Jørgensen (2013) confirms that EGM dominates both standard value function iteration and MPEC in speed and robustness for structural estimation.

The frontier that matters most for this paper is the multivariate one. White (2015) formalized conditions under which EGM applies to multidimensional problems and developed interpolation methods for the curvilinear grids that result. Iskhakov (2015) characterize a triangular structure in systems of first-order conditions that permits sequential solution by substitution without root-finding. Triangular EGM requires triangularity of the entire FOC system; EGM$^n$ instead requires sequential invertibility of Euler equations at each stage, permitting mixed structures where some stages use separable utility, others use invertible transitions, and others use standard optimization. Druedahl (2021) provides a guide to solving non-convex consumption-saving models, combining an upper envelope algorithm with the nested EGM approach of Druedahl & Jørgensen (2017). Nested methods reduce computational complexity relative to joint optimization but still embed optimization or root-finding within outer EGM loops, retaining some grid search overhead. Ludwig & Schön (2018) propose Delaunay triangulation for interpolating on the curvilinear endogenous grids that arise in such problems, though triangulation costs can offset the gains from avoiding grid search.

A parallel line of research exploits first-order conditions without explicit EGM structure. Maliar & Maliar (2013) develop the Envelope Condition Method, which shares EGM’s strategy of avoiding numerical optimization, though the method’s forward-solution structure restricts it to infinite-horizon problems. Arellano et al. (2016) apply envelope condition methods to sovereign default models, achieving EGM-like efficiency gains. Mendoza & Villalvazo (2020) propose a fixed-point iteration algorithm (FiPIt) that avoids both root-finding and irregular interpolation in models with occasionally binding constraints, offering an alternative to EGM when constraint structures differ.

Machine learning offers a different path to high-dimensional problems, particularly models with aggregate uncertainty where the wealth distribution becomes a state variable Krusell & Smith, 1998. Scheidegger & Bilionis (2019) apply Gaussian Process Regression to compute global solutions for high-dimensional stochastic problems. Maliar et al. (2021) use neural networks to approximate systems of equations characterizing dynamic economic models. Azinovic et al. (2022) develop deep equilibrium nets that train neural networks to satisfy all equilibrium conditions along simulated paths, demonstrating applicability to life-cycle models with heterogeneity. These machine learning approaches trade the interpretability of explicit policy functions for scalability to very high dimensions, whereas EGM$^n$ maintains interpretable intermediate value functions at each decision stage. In a complementary direction, Bayer et al. (2026) develop an endogenous gridpoint method for distributional dynamics (DEGM), applying endogenous grid ideas to track the wealth distribution in heterogeneous agent models with aggregate risk, achieving an order of magnitude speedup over histogram methods.

1.2Methodology and contributions¶

EGM$^n$ (Sequential EGM) decomposes multidecision problems into stages that each admit an EGM inversion, passing efficiency gains forward from one stage to the next. Each stage applies EGM when the subproblem structure permits inversion of first-order conditions; when a subproblem lacks the required separability or invertibility, standard optimization methods apply. The method requires continuous choices satisfying smooth regularity conditions (Section 5). Compared to nested approaches that embed optimization within EGM loops, EGM$^n$ requires stronger structural assumptions (separable utility or independent transitions), but avoids optimization at applicable stages and exposes interpretable intermediate value functions at each stage. ENGINE addresses the resulting curvilinear interpolation challenge, achieving 2-3x speedups over existing methods (Section 4).

We develop the method through two models of increasing complexity: Section 2 uses a three-choice labor-consumption-portfolio problem to illustrate sequential decomposition, and Section 3 extends to a health investment model where two persistent state variables generate genuinely two-dimensional curvilinear grids. The interpolation challenge these grids pose motivates ENGINE (Section 4), while Section 5 formalizes the separability and invertibility conditions that determine when each stage admits EGM inversion. Section 6 discusses limitations and extensions.

2The Sequential Endogenous Grid Method¶

Models where households simultaneously choose consumption, labor supply, and portfolio allocation present a computational challenge. Joint optimization over all three choices requires evaluating a three-dimensional optimization at every state space point. Imposing strong separability restrictions speeds computation but may rule out economically interesting preference specifications. Sequential decomposition exploits partial separability: when decisions are separable in stages but not necessarily globally, each stage can be solved efficiently through EGM inversion.

2.1Problem setup¶

The baseline problem for demonstrating the Sequential Endogenous Grid Method (EGM$^n$) is a discrete time version of Bodie et al. (1992) where a consumer has the ability to adjust their labor as well as their consumption in response to financial risk. This model serves as an ideal pedagogical example for three reasons: it features three simultaneous decisions (labor, consumption, portfolio), it admits a natural sequential ordering where each stage sheds a state variable, and two of three stages permit EGM inversion while the portfolio stage requires optimization. The objective consists of maximizing the present discounted lifetime utility of consumption and leisure over a finite horizon of $T+1$ periods, where $t = 0$ denotes the beginning of the planning horizon (the first period of economic life) and $t = T$ denotes the terminal period.

where $\VFunc_0$ is the lifetime value function at the start of period zero, $\BLev_0$ is beginning-of-period bank balances, $\tShkEmp_0$ is the transitory wage shock, and $\Ex_0$ denotes the expectation conditional on information available at the start of the planning horizon.

In particular, this example makes use of a utility function adapted from Bodie et al. (1992), with additively separable utility of consumption and leisure that is homogeneous of degree $1-\CRRA$ in permanent income (ensuring a balanced growth path):

where $\leiShare > 0$ determines the curvature of leisure utility (and thus the Frisch elasticity of labor supply), the term $(\labShare\PLev)^{1-\CRRA}$ with $\labShare > 0$ scales leisure utility to have the same curvature and growth properties as consumption utility, and $\PLev$ is permanent income. This scaling follows Mertens & Ravn (2011) and ensures that both utility components are homogeneous of degree $1-\CRRA$ in $\PLev$, permitting normalization.^[4] The use of additively separable utility is deliberate: it enables multiple EGM steps in the solution process. Dividing through by $\PLev^{1-\CRRA}$ and defining normalized consumption $\cRat = \CLev/\PLev$, the normalized period utility becomes

For the remainder of the analysis, we work with these normalized variables.

This model represents a consumer who begins the period with a level of bank balances $\bRat_{t}$ and a given wage offer $\tShkEmp_{t}$. Simultaneously, they are able to choose consumption, labor intensity, and a risky portfolio share with the objective of maximizing their utility of consumption and leisure, as well as their future wealth.

Expressing the problem in normalized recursive form^[5] makes the stationarity of the decision rules apparent. The household solves

where $\DiscFac$ is the discount factor, $\PGro_{t+1}$ is the permanent income growth factor, $\Rfree$ is the risk-free gross return, $\Risky_{t+1}$ is the stochastic risky asset return, $\Rport_{t+1}$ is the portfolio return, and non-negativity constraints $\cRat_{t} \geq 0$, $\leisure_{t} \in [0,1]$, and $\riskyshare_{t} \in [0,1]$ restrict feasible choices. The terminal condition is $\vFunc_{T+1} \equiv 0$, so the agent in the final period $T$ consumes all remaining resources and chooses full leisure. Throughout, we assume standard constraint qualifications hold such that interior solutions satisfy first-order conditions.^[6] The constraints define a sequence of state transitions: labor supply $\labor_{t}$ determines market resources $\mRat_{t}$ (bank balances plus labor income), consumption determines liquid savings $\aRat_{t}$, and the portfolio choice $\riskyshare_{t}$ induces a stochastic return $\Rport_{t+1}$ that yields next period’s normalized bank balances $\bRat_{t+1}$.

Although the household makes all three decisions simultaneously from an economic perspective, the dependence structure permits sequential solution. The labor-leisure choice determines market resources; given those resources, the consumption-saving choice determines liquid assets; given liquid assets, the portfolio choice follows. This natural ordering reflects the problem’s information flow rather than introducing artificial timing. Each stage uses information from subsequent stages (through continuation values) while shedding state variables that later stages do not require.

The sequential decomposition begins at the start of the period with the labor-leisure problem. To distinguish value functions at different stages, we introduce stage superscripts: the original problem has $\vFunc_t \equiv v^0_t$, representing the value at the first decision stage (labor-leisure), and each subsequent stage $v^i_t$ represents the value function after making decisions at stages $0, 1, \ldots, i-1$. At this stage, the household observes bank balances $\bRat_{t}$ and the wage offer $\tShkEmp_{t}$, choosing leisure to maximize the sum of current leisure utility and the continuation value from market resources $\mRat_{t}$:

Once market resources are realized, the pure consumption-saving problem determines how to allocate $\mRat_{t}$ between current consumption and liquid assets. The state space has been reduced to a single dimension since the wage offer no longer matters:

The final stage allocates liquid savings $\aRat_{t}$ between risk-free and risky assets. This portfolio problem involves no within-period utility, only the expected continuation value from next period’s bank balances:

The sequential formulation follows the nested approaches of Clausen & Strub (2020) and Druedahl (2021) but composes EGM inversions without embedding optimization. Each choice is self-contained in a subproblem, with the structure chosen to minimize state variables at each stage. The sequential formulation is mathematically equivalent to the original joint problem by Bellman’s principle of optimality Bellman (1957): no uncertainty resolves between subproblems within a single period. From the agent’s information set at time $t$, all three decisions are made before any time-$t+1$ shocks realize. The expectation operator appears only in the final subproblem, ensuring identical information across decisions. If shocks were to resolve between stages, agents would have access to information unavailable in the original formulation, changing the problem’s solution.

Limiting cases confirm that the decomposition nests simpler models. When $\labShare \to 0$, leisure utility vanishes and the labor-leisure stage degenerates: the agent works full time regardless of wages, reducing the problem to the standard two-stage consumption-portfolio EGM of Carroll (2006). When $\DiscFac \to 0$, the fully impatient agent consumes all resources immediately and the portfolio stage becomes irrelevant, recovering the static consumption problem. These extremes verify that the sequential structure reduces to well-understood special cases, each lacking one of the three dimensions of choice.

2.2Sequential solution¶

Not every subproblem admits an EGM solution. The portfolio stage illustrates this limitation. By assigning leisure utility to the labor-leisure stage and consumption utility to the consumption-savings stage, we exhaust the separable utility components. No separable utility term remains for the risky share; it affects utility only through future wealth, not through contemporaneous utility. This subproblem requires standard convex optimization rather than EGM inversion.

Restating the problem in compact form gives

The first-order condition with respect to the risky portfolio share, after dividing through by $\DiscFac \aRat_t > 0$ (which is positive at interior solutions, so that the first-order conditions hold with equality), is

Finding the optimal risky share requires numerical root-finding of this condition. The envelope condition is

This completes the portfolio stage solution. The post-decision value $v^2_t$ captures the expectation over future shocks; Section 3 denotes this quantity $\wFunc_t$ to emphasize its post-decision interpretation following Powell (2011).^[7]

The consumption-saving EGM follows Carroll (2006) but we cover it for exposition. The consumption-savings subproblem in compact form, substituting the market resources constraint and ignoring the no-borrowing constraint for now, is:

The first-order condition with respect to $\cRat_{t}$ yields the familiar Euler equation:

The marginal utility of consuming one more unit today must equal the discounted expected marginal value of saving that unit for tomorrow, here expressed through the post-decision value function $(v^{2}_t)'$.

Inverting this equation is the first of three EGM inversions. Inversion requires strict monotonicity of $\util'$, which holds under CRRA preferences since $\util''(c) = -\CRRA c^{-\CRRA-1} < 0$ for $\CRRA > 0$, ensuring a one-to-one mapping between marginal utility and consumption levels. We adopt the notational convention that bracketed variables (e.g., $\aMat$, $\mMat$) denote exogenous grids, while gothic (fraktur) letters (e.g., $\cEndFunc$, $\mEndFunc$) denote endogenous quantities constructed by inverting first-order conditions. For single-variable value functions, primes denote ordinary derivatives; Section 3 switches to superscript notation for partial derivatives of multivariate functions. The inverted policy function is

Given the utility function above, the marginal utility of consumption and its inverse are

Carroll (2006) demonstrates that an exogenous grid of $\aMat$ points yields the unique $\cEndFunc_{t}(\aMat)$ that optimizes the consumption-saving problem. Using the market resources constraint, the exact amount of market resources consistent with this consumption-saving decision is

This $\mEndFunc_{t}(\aMat)$ is the “endogenous” grid that is consistent with the exogenous decision grid $\aMat$. Given a $(\mEndFunc_{t}(\aMat), \cEndFunc_{t}(\aMat))$ pair for each $\aRat \in \aMat$, an interpolating consumption function can be constructed for market resources values not on the endogenous grid.

The envelope condition pins down the marginal value of market resources at the optimum:

This chain of equalities links stages: the labor-leisure stage needs $(v^1_t)'$, which it obtains directly from the consumption-saving solution without additional computation.

The labor-leisure subproblem can be restated more compactly by substituting $\labor_t = 1 - \leisure_t$ and $\mRat_t = \bRat_t + \tShkEmp_t \labor_t$ directly into the objective:

Here market resources $\mRat_t = \bRat_t + \tShkEmp_t(1-\leisure_t)$ appear inside the value function, so the trade-off between leisure and labor income is mediated entirely through $v^1_t$.

The first-order condition with respect to leisure is

This equates the marginal utility of leisure to the opportunity cost of forgone labor income $\tShkEmp_t$, scaled by the marginal utility of consumption $(v^1_t)'(\mRat_t) = \util'(\cRat_t)$.

The marginal utility of leisure and its inverse are

Using an exogenous grid of market resources $\mMat$ and wage shocks $\tShkMat$, leisure follows as

However, agents with high market resources $\mRat_{t}$ and low wage offers $\tShkEmp_{t}$ may find the unconstrained optimum violates the feasibility constraint $\leisure_t \in [0,1]$. When this occurs, the solution is projected onto the constraint boundary, defining the constrained optimal function $\hat{\zEndFunc}_{t}(\mMat, \tShkMat)$ as

This projection onto the feasible set ensures that the leisure choice respects the time endowment constraint.^[8] In practice, the projection primarily addresses the upper bound $\leisure_t = 1$ (full leisure, zero labor supply), which binds for wealthy agents facing low wages. The lower bound $\leisure_t = 0$ rarely binds due to the Inada condition on leisure utility. In regions where constraints bind, the Kuhn-Tucker conditions replace the unconstrained first-order condition. Interpolation must handle potential non-differentiabilities at constraint boundaries by sorting the endogenous grid points and applying piecewise interpolation with separate segments on either side of each binding constraint, though these kink regions typically affect only small portions of the state space.

Labor follows as $\lEndFunc_{t}(\mRat_{t}, \tShkEmp_{t}) = 1 - \hat{\zEndFunc}_{t}(\mRat_{t}, \tShkEmp_{t})$. For each $\tShkEmp_{t}$ and $\mRat_{t}$ on the exogenous grid, the endogenous grid of bank balances is $\bEndFunc_{t}(\mRat_{t}, \tShkEmp_{t}) = \mRat_{t} - \tShkEmp_{t}\lEndFunc_{t}(\mRat_{t}, \tShkEmp_{t})$.

The envelope condition then provides the marginal value of bank balances. At interior solutions where $\leisure_t \in (0,1)$, the first-order condition $\h'(\leisure_t) = (v^1_t)'(\mRat_t)\tShkEmp_t$ holds, giving

At corner solutions ($\leisure_t = 0$ or $\leisure_t = 1$), the envelope theorem still yields $\partial v^0_t/\partial \bRat = (v^1_t)'(\mRat_t)$, but the second equality does not hold because the first-order condition is replaced by the Kuhn-Tucker inequality.

The resulting endogenous grid for the labor-leisure problem is curvilinear rather than rectilinear, requiring specialized interpolation methods discussed in Section 4.^[9]

Figure 1 shows the full solution: panel (a) displays the curvilinear endogenous grid colored by labor supply, panels (b-d) show the consumption, leisure, and portfolio policy functions. The labor-portfolio example demonstrates EGM$^n$’s core principle: decompose economically simultaneous decisions into computationally sequential stages, composing EGM inversions without optimization. Sequential decomposition exploited separability in utility (leisure) and transitions (portfolio returns). The labor-leisure stage used EGM inversion; the portfolio stage required convex optimization. Each stage required at most one post-decision state variable, keeping dimensionality manageable. The resulting curvilinear grid from the labor-leisure inversion requires specialized interpolation, addressed in Section 4. Retirement planning with multiple accounts requires tracking several state variables simultaneously across stages, presenting a more demanding test of the method’s applicability.

3The $\text{EGM}^n$ in Higher Dimensions¶

The labor-portfolio problem in Section 2 features at most one post-decision state variable per stage, keeping dimensionality manageable. Problems where multiple state variables persist across stages present a more demanding test: two state variables must be tracked simultaneously through the EGM inversion. Health investment, durable goods choices, and human capital accumulation all exhibit this structure. The health investment model requires the risk-aversion coefficient $\CRRA < 1$ for technical reasons detailed below; it serves to illustrate interpolation properties of curvilinear EGM grids rather than realistic calibration. The labor-portfolio model of Section 2 imposes no such restriction. The health investment problem demonstrates that EGM$^n$ extends to such settings, though the interpolation challenge intensifies: endogenous grids become curvilinear, requiring specialized interpolation methods.

3.1A health investment model¶

For a demonstration of multivariate EGM$^n$, we turn to a consumption-saving model with health investment adapted from White (2015), which itself builds on Ludwig & Schön (2018). This model tests EGM$^n$ more severely than the labor-portfolio example: two continuous state variables (wealth and health) persist across EGM stages, generating genuinely two-dimensional curvilinear grids. White (2015) designed this model specifically to demonstrate curvilinear interpolation for EGM, so comparing ENGINE against it on the same problem provides a direct test of interpolation methods. In this model, the agent makes decisions about consumption and health investment, subject to wage rate uncertainty, health depreciation risk, and mortality risk that depends on health status.

Each period $t$, the agent observes their market resources $\mRat_t$ and health capital $\hRat_t$. They choose consumption $\cRat_t$ and health investment $\nRat_t$ to maximize lifetime utility, where $t = 0$ denotes the beginning of the planning horizon and $t = T$ denotes the terminal period. Consumption yields CRRA utility, while health investment produces additional health capital through a concave production function. Health capital serves two purposes: it reduces mortality risk and increases labor income through higher productivity.

The recursive problem is:

where the utility function and health production function are:

The notation is as follows: $\HRat_t$ denotes post-investment health capital, $\aRat_t$ is end-of-period assets, $\Surv_t$ is the survival probability (with the maximum death probability $\DiePrb_t$ applying when health is zero, i.e., $\HRat_t = 0$), $\delta_{t+1}$ is the stochastic health depreciation rate, $\omega_{t+1}$ is the stochastic wage rate, and $\yRat_{t+1}$ is labor income. The health production scale factor $\HealthProdFac > 0$ and the health production elasticity $0 < \HealthProdExp < 1$ determine diminishing returns to health investment. The terminal condition is $\vFunc_{T+1} \equiv 0$, so the agent in the final period consumes all remaining resources. The agent trades off current consumption utility against the survival probability $\Surv_t$, which depends on health through $\DiePrb_t$: higher health investment raises $\Surv_t$ and thereby increases the weight placed on future value.^[11]

This model requires $\CRRA < 1$ so that utility is non-negative for all $\cRat > 0$, and that there is positive probability of zero wage ($\omega = 0$). These restrictions ensure that the first-order conditions are necessary and sufficient to characterize the solution. The $\CRRA < 1$ restriction implies low risk aversion (below log utility), which limits the model to less risk-averse agents than standard calibrations; the health model serves to illustrate the interpolation properties of curvilinear EGM grids rather than to represent empirically plausible household behavior. The labor-portfolio model of Section 2 imposes no such restriction and uses $\CRRA = 5$. As a limiting case, when the health production elasticity $\HealthProdExp \to 1$ (linear production), the marginal product $\gFunc'$ becomes constant, so the EGM inversion at the health investment stage yields a unique solution independent of the state variables, and the problem collapses to a standard consumption-savings problem with an exogenous health process.^[12]

3.2Sequential EGM solution¶

EGM$^n$ decomposes a problem with multiple controls into a sequence of subproblems, each handling a single control variable. This problem splits into three stages: a health investment stage, a consumption stage, and a post-decision stage that handles expectations. Using the stage superscript convention from Section 2, $\vFunc_t \equiv v^0_t$ is the value at the first decision stage (health investment). For the post-decision stage, we use $\wFunc_t$ rather than $v^2_t$ (the notation of Section 2) to emphasize that it represents a post-decision value function (capturing expectations over future shocks) rather than a decision stage. This notation follows Powell (2011) where $\wFunc$ denotes the post-decision state value.^[13] Since all value functions in this section have multiple arguments, we write partial derivatives as superscripts ($\wFunc_t^{\aRat} \equiv \partial \wFunc_t / \partial \aRat$) rather than the prime notation of Section 2; the Appendix uses subscript notation ($v^1_{\lRat\HRat}$) for second-order terms.

The post-decision stage represents the value of end-of-period states $(\aRat_t, \HRat_t)$ before the realization of next period’s shocks:

where $\yRat_{t+1} = \omega_{t+1} \HRat_t$, $\hRat_{t+1} = (1 - \delta_{t+1}) \HRat_t$, and $\mRat_{t+1} = \Rfree \aRat_t + \yRat_{t+1}$. Conceptualizing this subproblem as a separate stage allows the function $\wFunc_t$ to be constructed once and used in prior optimization problems without repeated expectation calculations.^[14]

After making their health investment decision, the agent has liquid wealth $\lRat_t$ and post-investment health $\HRat_t$. The consumption problem is:

Post-investment health $\HRat_t$ passes through this stage unaffected because it enters the continuation value but is not changed by the consumption decision. For each fixed value of $\HRat_t$, this is a standard one-dimensional consumption-saving problem that can be solved via EGM.^[15]

At the beginning of the period, the agent has market resources $\mRat_t$ and health capital $\hRat_t$. The health investment problem is:

This stage has no direct utility payoff, but the agent’s choice of health investment affects both their liquid wealth (through the budget) and their post-investment health (through the production function). The differentiable and invertible health production function $\gFunc$ enables an EGM step. The constraint $\nRat_t \geq 0$ is handled by the Inada condition $\lim_{\nRat \to 0}\gFunc'(\nRat) = \infty$: the marginal product of health investment grows without bound near zero, so interior solutions obtain whenever the marginal value of health is positive and the agent has resources to invest.^[16]

The consumption EGM¶

The consumption stage applies the same EGM inversion as Section 2, now with health $\HRat_t$ passing through as a parameter. On an exogenous grid of post-decision states $(\aMat, \HMat)$, the first-order condition $\util'(\cRat_t) = \wFunc_t^{\aRat}(\aRat_t, \HRat_t)$ inverts to

The endogenous liquid wealth grid is $\lEndFunc_t(\aMat, \HMat) = \aMat + \cEndFunc_t(\aMat, \HMat)$, and the envelope conditions provide the marginal values needed by the health investment stage:

The health investment stage uses EGM with a differentiable transition. The problem in compact form is:

The first-order condition with respect to $\nRat_t$ is:

Rearranging the first-order condition yields:

Since $\gFunc'(\nRat) = \HealthProdFac \nRat^{\HealthProdExp - 1}$ is invertible, optimal health investment follows:^[17]

The transition equations then recover the endogenous pre-decision states:

The envelope conditions provide:^[18]

Starting from a regular rectilinear grid of $(\aMat, \HMat)$, the health investment EGM step produces a curvilinear endogenous grid of $(\mEndFunc_t, \hEndFunc_t)$. Figure 2 illustrates this transformation.

Despite this warping, the endogenous grid maintains the topological structure of the exogenous grid: neighboring points in the $(\lRat, \HRat)$ grid map to neighboring points in the $(\mRat, \hRat)$ grid. This property enables efficient interpolation, as discussed in Section 4.

4Multivariate Interpolation on Curvilinear Grids¶

EGM’s efficiency comes from working on exogenous grids where calculations are straightforward, then using the inverted Euler equation to recover endogenous state variables. But this efficiency creates a problem. The resulting endogenous grid is curvilinear rather than rectilinear, and standard multilinear interpolation, which assumes each dimension varies independently, cannot handle it. What interpolation methods can respect the actual geometry of these grids while exploiting the topological structure that persists despite geometric distortion?

This section presents ENGINE (ENdogenous Grid INterpolation and Extrapolation), which relies on the index structure that endogenous grids inherit from exogenous grids despite geometric warping. ENGINE reduces multidimensional interpolation to a sequence of one-dimensional interpolations along these inherited indices, using the fact that row $k$ remains row $k$ after warping and neighbors remain neighbors, even when geometric regularity (uniform spacing, rectilinear alignment) is lost.

Consider a curvilinear grid indexed by $j \in \{1,\ldots,J\}$ and $k \in \{1,\ldots,K\}$, where each “row” (fixed $k$) contains $J$ points. Standard curvilinear interpolation locates the containing quadrilateral cell via sector-walking, then solves for normalized coordinates within that cell (a quadratic equation in 2D, Newton iteration in higher dimensions). ENGINE sidesteps both operations by reframing the problem: instead of asking “which cell contains this point?”, ENGINE asks “where does a vertical line at $x^*$ intersect each row?” For each of the $K$ rows, this is a one-dimensional interpolation problem: find where $x^*$ falls among the $J$ $x$-coordinates in that row, then interpolate the $y$-coordinate to produce an intermediate point. A final 1D interpolation across these $K$ intermediate points yields the answer. The approach works because EGM preserves index structure: point $(j,k)$ in the exogenous grid maps to a geometrically warped but topologically consistent location in the endogenous grid, so that row $k$ remains row $k$ and neighbors remain neighbors.

4.1Regularity conditions¶

The interpolation challenge arises because first-order conditions induce nonlinear mappings from exogenous to endogenous grids. Highly nonlinear or non-monotonic Euler equations can distort grid structure beyond the regular spacing assumed by standard methods. Binding constraints compound the problem by creating kinks in policy functions, introducing additional irregularity.

The pure consumption-savings problem illustrates the basic phenomenon. An exogenous grid of post-decision liquid assets $\aMat$ maps through the inverted Euler equation to an endogenous grid of market resources $\mMat$ with different spacing; the nonlinearity of marginal utility ensures this mapping is non-uniform. In one dimension, that is no obstacle: non-uniform linear interpolation handles the distortion.

Higher-dimensional problems inherit this warping in each dimension simultaneously, potentially destroying the regular structure assumed by standard multilinear interpolation. The degree of structural preservation determines the appropriate interpolation method. Figure 2 in the previous section illustrates this transformation for the health investment model.

Previous approaches to this problem include Delaunay triangulation Ludwig & Schön, 2018 and curvilinear interpolation White, 2015. Delaunay triangulation constructs a mesh of simplices over the scattered points and performs barycentric interpolation within each simplex. While general and robust, triangulation is computationally expensive, often requiring $O(N \log N)$ for construction alone, and must be recomputed when grids change during iterative solution procedures. The curvilinear method takes advantage of the grid structure to map irregular quadrilateral sectors to the unit square for bilinear interpolation; sector location uses a visibility walk algorithm, while coordinate calculation in 2D employs a closed-form quadratic solution (3D and higher require Newton iteration).

ENGINE requires structural conditions on the endogenous grid, but these conditions are not additional assumptions: they follow from the same economic structure that makes EGM applicable. Theorem 2 below proves that any grid produced by an EGM inversion automatically satisfies ENGINE’s requirements, provided the underlying value function is strictly concave and smooth. This applies to standard EGM Carroll, 2006, nested EGM Druedahl, 2021, and the EGM$^n$ of this paper alike. However, discrete choices pose a problem: when optimal policies jump discontinuously between discrete alternatives, the resulting grids violate monotonicity (IPM) and ENGINE does not apply. Such problems require upper envelope techniques as in G2EGM or DCEGM. The Endogenous Grid Method works when Euler equations are invertible, value functions are strictly concave, and both are twice continuously differentiable. These properties generate well-behaved endogenous grids automatically. A grid satisfying these conditions is homeomorphic to the rectangular index grid: the EGM mapping is a continuous bijection with continuous inverse from index space to physical space.^[20]

The conditions separate into two categories: geometric regularity (ensuring a well-defined grid) and algorithmic efficiency (ensuring ENGINE operates efficiently). We state these conditions formally, then prove that grids satisfying them support ENGINE interpolation, and finally show that EGM-generated grids satisfy these conditions automatically.

Nonlinear EGM mappings can distort cells severely enough to invert them. The fold-free condition, the classical validity condition from structured mesh generation Knupp, 1999, ensures each cell maintains proper orientation.

Fold-free ensures local cell validity, but ENGINE also requires that bracketing along rows and columns be well-defined. IPM ensures coordinates increase monotonically along each index direction.

Together, fold-free and IPM ensure the grid mapping is a homeomorphism, guaranteeing interpolation correctness. The final condition, IPO, ensures efficiency: it bounds how fast bracketing indices change across rows, enabling ENGINE to use binary search with bounded search ranges.

When $\alpha = 1$, adjacent rows’ brackets differ by at most one; when $\alpha = J$, IPO imposes no constraint and ENGINE degenerates to linear search along each row, yielding $O(K \cdot J)$ per query. ENGINE is built around IPO: binary search on rows bounds the search range for $j^*$ at each probe by $\alpha$.

The IPO constant $\alpha$ relates to the Lipschitz constant $L$ of the EGM mapping. To see this, consider how the bracketing index $j^*(k;x)$ changes across rows. The EGM mapping transforms exogenous grid points to endogenous coordinates. If this mapping has Lipschitz constant $L$, then $|x_{j,k_1} - x_{j,k_2}| \leq L \cdot |k_1 - k_2| \cdot \Delta_k$ for row spacing $\Delta_k$. For a fixed query $x$, the bracket $j^*$ can therefore shift by at most $L \cdot |k_1 - k_2| \cdot \Delta_k / \Delta_j$ indices when moving from row $k_1$ to $k_2$, where $\Delta_j$ is the column spacing. Thus $\alpha = L \cdot \Delta_k / \Delta_j$. Strict concavity of the value function bounds $L$ (the second derivative controls how fast optimal policies change), so for smooth EGM problems, $\alpha$ is typically small.^[23]

In practice, $\alpha$ can be estimated empirically after solving by computing $\max_{k_1,k_2} |j^*(k_1; x) - j^*(k_2; x)| / |k_1 - k_2|$ over a dense set of test points. For the models in this paper, $\alpha \leq 2$ on all grids tested, and empirical query times scale as $O(\log J + \log K)$ rather than the worst-case $O(\log J \cdot \log K)$.^[24]

With the regularity conditions defined, we now establish their implications. Fold-free and IPM together guarantee that any query point has exactly one location in the grid, so interpolation is well-defined (Theorem 1).

The homeomorphism ensures correctness, but we also need efficiency. The geometric conditions connect to concrete algorithmic guarantees (Corollary 1): IPO bounds how fast brackets change, enabling ENGINE to locate cells without exhaustive search.

The preceding results establish what conditions enable ENGINE. The practical question is whether these conditions impose additional restrictions on practitioners. Standard EGM assumptions (strict concavity, smoothness, monotone marginal utility) imply ENGINE’s conditions automatically (Theorem 2): no additional restrictions arise.

The health investment model of Section 3 illustrates these results: consumption and health investment policies are monotonic (IPM), policy functions vary smoothly (IPO), and the EGM mapping is locally invertible (fold-free). Violations of these conditions typically signal either numerical issues or economic features requiring special treatment.

Occasionally binding constraints, such as borrowing limits, merit explicit discussion. These constraints introduce kinks in policy functions but preserve monotonicity, satisfying IPM, IPO, and fold-free. EGM handles such constraints naturally: the exogenous grid defines the unconstrained (interior) region, and the constrained region is constructed by prepending a point at the constraint boundary (e.g., $\cFunc = 0$ at $\mRat = 0$ for a liquidity constraint). The kink occurs where the policy transitions from corner to interior solution, but on either side of this boundary the policy remains monotonic in wealth. Grid cells straddling the kink may exhibit elevated $\alpha$ locally, but ENGINE handles this gracefully by widening the search range. Discrete choices, by contrast, create discontinuities that violate these conditions.

4.2The ENGINE algorithm¶

ENGINE exploits the index correspondence between endogenous and exogenous grids: each point $(\mRat_t^{(j,k)}, \hRat_t^{(j,k)})$ in the endogenous grid corresponds to indices $(j,k)$ from the exogenous grid $(\lRat_t^{(j)}, \HRat_t^{(k)})$. This structure enables efficient cell location and interpolation without explicit geometric constructions.

There exists a homeomorphism between the curvilinear grid in physical space and the rectilinear grid in index space. Figure 3 illustrates this correspondence: the warped grid on the left maps bijectively and continuously to the regular index grid on the right, with the inverse also continuous, preserving neighborhood relationships. ENGINE works in index space where bracketing is efficient, then inverts the homeomorphism to recover physical coordinates.

The full algorithm is provided in the Appendix. Figure 4 illustrates this process: the vertical line at $x = x^*$ intersects each $k$-slice of the curvilinear grid, with Pass 1 finding the intermediate $y$-coordinates at these intersections. Pass 2 then interpolates across these intermediate values to produce the final result.

The choice of dimension order (rows versus columns) can affect accuracy when grid warping is highly anisotropic. For the health investment problem, interpolating first along the liquid wealth dimension (which varies more smoothly) and then along the health dimension typically yields better results.

ENGINE sidesteps the cell search and coordinate inversion required by curvilinear methods, requiring only sequential 1D interpolations. The tradeoff is that ENGINE requires IPM and IPO in addition to fold-free, but for EGM-generated grids these conditions hold automatically.

For sorted query points, an additional optimization applies: given sorted queries $\{q_i\}$ and sorted grid coordinates $\{x_j\}$, a “walking pointer” bracket index $j$ only advances (never backtracks) as queries are processed in order. Finding the enclosing interval for query $q_i$ requires checking whether $q_i < x_{j+1}$; if so, interpolation occurs within $[x_j, x_{j+1}]$; otherwise, $j$ advances until the condition holds. This reduces per-query complexity from $O(\log J)$ to $O(1)$ when queries are monotonically ordered, as occurs with meshgrid evaluation.

For a query point $(x^*, y^*)$, the interpolated value is:

where $\hat{y}_k$ and $\hat{f}_k$ are the intermediate coordinates and values from Pass 1.

The preceding theorems established that ENGINE is well-defined and efficient on EGM-generated grids. Decomposing 2D interpolation into sequential 1D operations does not sacrifice accuracy: the method achieves the same second-order convergence as standard bilinear interpolation (Proposition 1).

With accuracy established, Proposition 2 formalizes the complexity analysis. IPO bounds how fast brackets change across rows, enabling ENGINE to reuse bracket information from previous probes rather than searching from scratch.

The method offers several computational advantages: natural parallelization across query points (each query is independent), efficient memory access patterns from sequential array traversal, and no preprocessing or Newton iteration in any dimension.^[27]

Extension to higher dimensions¶

ENGINE extends naturally to $N$ dimensions via $N$ sequential passes. For a problem with indices $(j_1, j_2, \ldots, j_N)$:

1. Pass 1 interpolates along the $j_1$ direction for each combination of $(j_2, \ldots, j_N)$.

2. Pass 2 interpolates along the $j_2$ direction using the results from Pass 1.

3. Continue until Pass $N$ produces the final interpolated value.

The total complexity for a single query scales as $O(\sum_{n=1}^{N-1} (\prod_{m=n+1}^{N} J_m) \log J_n + \log J_N)$ when using the naive approach that evaluates all intermediate slices. Binary search optimizations analogous to the 2D case can reduce this, but the gains depend on higher-dimensional analogues of IPO that bound bracket displacement across multiple index dimensions simultaneously.^[28]

4.3Comparison with alternative methods¶

The three approaches to multi-dimensional EGM interpolation differ in their algorithmic strategy for handling curvilinear endogenous grids:

ENGINE achieves $O(\log J \cdot \log K)$ per query, which is asymptotically faster than curvilinear’s $O(J+K)$ sector-walking. For smooth EGM problems with small IPO constant $\alpha$, empirical performance approaches $O(\log J + \log K)$. Benchmarks show 2-3x speedups depending on grid size, with larger gains at larger grids.

Figure 5 illustrates how these three methods partition the state space. Bilinear interpolation identifies the containing quadrilateral cell and computes normalized coordinates within it. Delaunay triangulation constructs a mesh of triangles and uses barycentric coordinates. ENGINE processes the grid slice-by-slice, interpolating along indexed rows before combining intermediate results.

Figure 6 compares ENGINE against the curvilinear interpolation of White (2015) across both time horizon (cycles) and grid resolution.^[29] The benchmarks use the health investment model of Section 3 with $\CRRA = 0.5$, providing a direct comparison on the same model class for which curvilinear interpolation was developed. As noted in Section 3, the $\CRRA < 1$ restriction is specific to this health formulation; the benchmarks illustrate interpolation performance on curvilinear grids rather than an economically calibrated model. Speedups scale with grid size as the complexity advantage materializes; accuracy matches standard bilinear interpolation per Proposition 1.

For the health investment model, the dominant cost components in the backward induction loop are: expectation calculations (computing marginal value functions on the exogenous grid via quadrature), interpolation (evaluating value and marginal value functions on the curvilinear endogenous grid), and EGM inversion (recovering endogenous states from first-order conditions). At typical grid sizes ($44 \times 50$), interpolation accounts for roughly 40-50% of solve time, expectations for 30-40%, and EGM inversion for the remainder. ENGINE’s speedup therefore translates most directly into the interpolation component, explaining why total solve-time speedups (2-3x) are smaller than the asymptotic complexity ratio might suggest.

ENGINE provides efficient interpolation when grids satisfy fold-free, IPM, and IPO. By Theorem 2, any EGM inversion under standard conditions (strict concavity, smoothness) produces such grids automatically. The next section addresses a separate question: when can a multidecision problem be decomposed into EGM$^n$ stages? The separability and invertibility conditions there determine when EGM$^n$ applies, completing the practical toolkit for applying these methods to new problems.

5Conditions for Sequential Decomposition¶

When does EGM$^n$ apply? The labor-portfolio problem (Section 2) and health investment problem (Section 3) illustrated two key structures: separable utility functions and invertible transitions. This section formalizes these requirements and provides practical guidance for decomposing new problems. The examples demonstrated specific instances; we now characterize the general conditions that make sequential decomposition with EGM inversion possible.

5.1Splitting the problem into subproblems¶

Decomposition begins by counting independent control variables. A problem with $n$ control variables typically decomposes into $n$ subproblems. One must take care not to double-count: the consumption-savings choice ($\cRat + \aRat = \mRat$) represents one decision, not two. Similarly, labor-leisure is a single choice despite involving two variables.

Each control variable requires an enabling structure that permits EGM inversion. Two mathematical structures suffice: separable, differentiable, and invertible utility functions (as in the leisure utility of Section 2); or differentiable and invertible transition functions (as in the health production function of Section 3). Match each control variable to its enabling structure. The labor-portfolio example features additive utility separability: leisure utility enables the labor-leisure EGM step, consumption utility enables the consumption-savings EGM step. When no structure applies (as in the portfolio choice stage), standard optimization is required.

The ordering of subproblems should shed state variables early. Poor sequencing propagates unnecessary state variables through later stages. In the consumption-leisure-portfolio problem, placing labor-leisure first resolves the wage rate before the consumption stage, keeping that subproblem one-dimensional. Choosing consumption first would force the labor decision to track both bank balances and wages, doubling its dimensionality.^[30]

5.2Formal conditions¶

We now abstract from specific models to general conditions. The notation shifts to uppercase calligraphic functions ($\VFunc$, $\WFunc$, $\UFunc$, $\TFunc$, $\GFunc$) for generic value, continuation, utility, transition, and shock functions, with generic state variables $\xRat$, $\yRat$, $\sRat$ in place of the model-specific variables: consumption $\cRat$, assets $\aRat$, and cash-on-hand $\mRat$ of preceding sections.

Consider a utility function of the form

where $\mathbf{a} = (a^1, \ldots, a^n)$ is the vector of control variables, $a^{i}$ is the $i$-th control variable, and $\mathbf{a}^{-i}$ is the vector of all control variables except the $i$-th one. This utility function is separable in the control variable corresponding to index $i$.

We collect the discounted continuation value into a single function:

Substituting, the problem reduces to:

When post-decision states are multidimensional, with components $\yRat^j$ for $j = 1, \ldots, n$ and transition functions $\TFunc^j$ mapping controls to each component (here superscripts on $\yRat$ and $\TFunc$ index components, not derivatives), the first-order condition (FOC) with respect to control $a^i$ (assuming an interior solution) becomes

The requirement $\frac{\partial \TFunc^j(\xRat, \mathbf{a})}{\partial a^i} = 0$ for $j \neq i$ (separability in the transition) is sufficient to solve for $a^i$ independently. This condition ensures that control $a^i$ affects only the $i$-th post-decision state, decoupling the FOC from other transition equations. When transition separability fails, the first-order conditions couple across stages, requiring simultaneous solution of all controls — exactly the computational burden that sequential EGM is designed to avoid.^[31]

Under transition separability, the first-order condition for stage $i$ simplifies to:

Each stage’s optimality condition depends only on its own control and the continuation value, not on controls chosen at other stages.

Separable utility¶

Once the problem is split into subproblems, the Endogenous Grid Method applies to each applicable subproblem while iterating backwards from the terminal period. The EGM step applies when there is a separable, differentiable and invertible utility function in the subproblem or when there is a differentiable and invertible transition in the subproblem.

To see when the method fails, consider non-separable CES preferences $\UFunc(\cRat, \leisure) = \frac{(\cRat^\theta \leisure^{1-\theta})^{1-\CRRA}}{1-\CRRA}$. The first-order condition (FOC) for consumption involves leisure: $\frac{\partial \UFunc}{\partial \cRat} = \theta \cRat^{\theta(1-\CRRA)-1} \leisure^{(1-\theta)(1-\CRRA)}$. Inverting for $\cRat$ requires knowing $\leisure$, and the symmetric condition for $\leisure$ requires knowing $\cRat$. The FOCs are coupled, so neither can be solved in isolation by EGM inversion. Such problems require joint root-finding (NEGM) or upper envelope techniques (G2EGM).

Consider a generic subproblem with a differentiable and invertible utility function:

where $\WFunc(\yRat) = \DiscFac \Ex[\VFunc_{+1}(\yRat)]$ is the continuation value. For an interior solution, the first-order condition is

When corner solutions occur (e.g., $\aRat$ at constraint boundaries), the unconstrained optimum from inverting the first-order condition must be projected onto the feasible set, as demonstrated in Section 2 for the leisure choice.

The question is when this first-order condition can be inverted to yield the optimal control directly. Proposition 3 gives the standard case: separable utility with a transition linear in the control, which covers most consumption-savings applications.

The linearity assumption $\frac{\partial \TFunc}{\partial \aRat} = k$ is satisfied by standard budget constraints appearing in consumption-savings models. For example, $\aRat = \mRat - \cRat$ implies $\frac{\partial \aRat}{\partial \cRat} = -1$, so $k = -1$. Similarly, the labor income constraint $\mRat = \bRat + \tShkEmp \cdot \labor$ has $\frac{\partial \mRat}{\partial \labor} = \tShkEmp$, which varies with the wage shock but is constant with respect to the control $\labor$. Linearity in the control allows the first-order condition to be inverted analytically, which is the computational step that replaces root-finding. State-dependent coefficients (like $\tShkEmp$) are permissible provided they are known when solving the subproblem.

Using an exogenous grid of the post-decision state $\yRat$, the optimal decision rule $\aRat$ follows at each point on the grid. This inversion replaces a numerical root-find with a single function evaluation, the core speed advantage of EGM. The monotonicity requirement ensures that the mapping from the post-decision state to the control is well-defined, while concavity guarantees uniqueness of the optimal decision at each grid point.

Proposition 3 covers the standard case where utility is separable. But some subproblems have no within-period utility at all, only transitions affecting multiple post-decision states. Health investment in Section 3 is such a case: there is no immediate utility from health spending, only effects on future health and wealth. Proposition 4 shows that EGM still applies when transitions are invertible, even without separable utility. Consider a problem with two endogenous state variables and two post-decision states:

where the continuation value is