RECURSIVE PROBLEM DEFINITION

Stages and Their Structure: - A stage is defined by three fundamental components: 1. Static Perches: Three static collections of state spaces and functions: - Arrival perch: State space 𝓧ₐ and arrival value function 𝒜(xₐ) - Decision perch: State space 𝓧ᵥ, decision value function 𝒱(xᵥ), and policy function - Continuation perch: State space 𝓧ₑ and continuation value function ℰ(xₑ)

1. Transition Functions: Mappings between perch state spaces:

   • Arrival → Decision: gₐᵥ maps xₐ (and possibly ζ) to xᵥ
   • Decision → Continuation: gᵥₑ maps (xᵥ, 𝜋) (and possibly ζ) to xₑ

2. Operational Processes: Mathematical operators that use the transitions:

   • Expectation operator for arrival: E_ζ[·] applied to 𝒱(gₐᵥ(xₐ, ζ))
   • Maximization operator for decision: max_𝜋{·} applied to r(xᵥ, 𝜋) + β(xᵥ)ℰ(gᵥₑ(xᵥ, 𝜋))

3. The stage is fully defined only when all three components (perches, transitions, and operators) are specified

4. The sequential flow through a stage involves applying these operators along with transitions:
5. At arrival: Agent has state xₐ ∈ 𝓧ₐ, then shock ζ realizes
6. At decision: Agent observes state xᵥ = gₐᵥ(xₐ,ζ) and makes choice 𝜋 ∈ Π(xᵥ)
7. At continuation: Stage concludes with state xₑ = gᵥₑ(xᵥ, 𝜋)
8. Each perch has an associated state space
9. Within-stage perch transitions (with directional mapping functions):
10. Arrival → Decision: gₐᵥ maps (xₐ, ζ) to xᵥ
11. Decision → Continuation: gᵥₑ maps (xᵥ, 𝜋) to xₑ
12. Each stage is defined independently of its position in any period sequence
13. Within a stage:
14. Parameters 𝔭 have fixed values
15. The continuation value function ℰ is taken as given
16. All functions and variables are defined solely in terms of internal structure
17. Only within-stage perch transitions (gₐᵥ and gᵥₑ) are specified
18. Connector functions (gₑₐ₊ and gᵥₐ₊) are defined at period level

Shock Spaces and Timing: Each stage has two shock spaces, one for each within-stage transition: - 𝒵ₐᵥ: Shock space for the arvl→dcsn transition (may be trivial: 𝒵ₐᵥ = {∅}) - 𝒵ᵥₑ: Shock space for the dcsn→cntn transition (may be trivial: 𝒵ᵥₑ = {∅})

The general transition function signatures are: - gₐᵥ: 𝓧ₐ × 𝒵ₐᵥ → 𝓧ᵥ (arrival to decision, with pre-decision shocks ζₐᵥ) - gᵥₑ: 𝓧ᵥ × Π × 𝒵ᵥₑ → 𝓧ₑ (decision to continuation, with post-decision shocks ζᵥₑ)

When a shock space is trivial, the corresponding argument is omitted from notation.

Common Shock Configurations:

Configuration	𝒵ₐᵥ	𝒵ᵥₑ	Example	Value Function Structure
Pre-decision only	non-trivial	trivial	Standard cons	𝒜(xₐ) = E_{ζₐᵥ}[𝒱(gₐᵥ(xₐ, ζₐᵥ))]
Post-decision only	trivial	non-trivial	port-with-shocks	𝒱(xᵥ) = max_𝜋 E_{ζᵥₑ}[r + β ℰ(gᵥₑ(xᵥ, 𝜋, ζᵥₑ))]
Both transitions	non-trivial	non-trivial	(general case)	𝒜(xₐ) = E_{ζₐᵥ}[max_𝜋 E_{ζᵥₑ}[...]]
Deterministic	trivial	trivial	Pure computation	𝒱(xᵥ) = max_𝜋{r + β ℰ(gᵥₑ(xᵥ, 𝜋))}

Unless otherwise specified, the default notation in this document uses pre-decision timing (𝒵ₐᵥ non-trivial, 𝒵ᵥₑ trivial). Specific examples will note their shock configuration explicitly in their Rosetta Stone tables.

Period and Stage Notation Rules: - Use 𝕊₀ and ℰ₀ to denote the terminal period and its value function - these are special cases that serve as anchors for backward induction - Subscript plus (₊) denotes the next stage relative to the current stage: - For states: xₐ₊ denotes the arrival state of the next stage - For periods: 𝕊₊ denotes the stages of the next period - For value functions: ℰ₊ denotes the continuation value for the next stage - Stage positions [i] are shown only when emphasizing specific positions in a sequence: - [0] for the first stage of a period - [-1] for the last stage of a period - When describing period structure: 𝕊[0], 𝕊[1], …, 𝕊[-1] - Stage kind κ is shown only when emphasizing transitions between different kinds - Time period t is shown only when emphasizing inter-period relationships - Otherwise these indices are omitted for clarity when discussing a stage's internal structure - Value function notation: - General form: 𝒱ₜ(s, xᵥ) shows dependence on time and stage - Stage-specific forms: - 𝒜(xₐ): Value at arrival state, before shock realization - 𝒱(xᵥ): Value at decision state, after shock but before choice - ℰ(xₑ): Value at continuation state, after choice but before transition - Value function relationships: - At arrival states: 𝒜(xₐ) = E_ζ[𝒱(gₐᵥ(xₐ, ζ))] - At decision states: - Sequential within period: 𝒱(xᵥ) = max_𝜋{r(xᵥ, 𝜋) + β(xᵥ)ℰ(gᵥₑ(xᵥ, 𝜋))} - Sequential at period end: 𝒱(xᵥ) = max_𝜋{r(xᵥ, 𝜋) + β(xᵥ)𝒜₊(gₑₐ₊(gᵥₑ(xᵥ, 𝜋)))} - Branching stages: 𝒱(xᵥ) = max_𝜋{r(xᵥ, 𝜋) + β(xᵥ)∑_{j∈N₊} p(j|xᵥ,𝜋)𝒜₊ⱼ(gᵥₐ₊(xᵥ, 𝜋))} where 𝒜₊ⱼ is the arrival value function for stage kind j ∈ N₊ - Subscript plus indicates next stage's value function - For terminal period: ℰ₀(xₑ) is specified directly - For branching stages: - Each possible next stage j ∈ N₊ has its own arrival value function 𝒜₊ⱼ - Expected continuation value is probability-weighted sum across branches - Value functions must be compatible with stage kind of each branch

Period Structure: - A period 𝕊 consists of an ordered sequence of stages: 𝕊[0], 𝕊[1], …, 𝕊[-1] - Sequential stages follow this ordering directly - Branching stages can transition to: - Within period: Any stage with higher index in 𝕊 - Between periods: Any stage in 𝕊₊[0], 𝕊₊[1], …, 𝕊₊[-1] - Stage positions [i] are shown when emphasizing sequence position - Time period t is shown when emphasizing inter-period relationships

Modularity Principle: - Stages are independent, reusable modules that define only their internal structure - Stages define only their internal transitions (gₐᵥ and gᵥₑ) - Connector functions (gₑₐ₊ and gᵥₐ₊) must be defined at the period or problem-assembly level - This separation ensures stages remain reusable modules, agnostic to how they connect to other stages

Connector Functions:

Terminology note: This document uses the single term connector for all rename/composition adapters that link stages or periods, qualified by scope: within-period connectors map between stages in the same period, while between-period connectors map from one period's continuation to the next period's arrival. Both are structurally identical — bijective maps on the variable namespace. Some other documents in this codebase (notably spec_0.1h-periods-nests.md and the builder code) use the term twister for what this document calls a "between-period connector," reserving "connector" for within-period mappings only. The distinction is purely one of scope, not of mathematical structure.

• Abstract Definition:
• Connector functions map states from one stage to arrival states of the next stage
• Two types based on stage kind:
  • Sequential: gₑₐ₊: 𝓧ₑ → 𝓧ₐ₊ maps from continuation to next arrival
  • Branching: gᵥₐ₊: 𝓧ᵥ × Π → 𝓧ₐ₊ maps from decision to next arrival

• When the target stage has optional state components (𝓧ₐᵒᵖᵗ⊥), the connector function may either provide a value in 𝓧ₐᵒᵖᵗ or map to ⊥. This choice is made at the period level when assembling stages.

• Stage Positions:

• Added when emphasizing sequence position
• Sequential case: gₑₐ₊(𝕊[-1]): 𝓧ₑ(𝕊[-1]) → 𝓧ₐ₊(𝕊₊[0])

• Branching case: gᵥₐ₊(𝕊[-1]): 𝓧ᵥ(𝕊[-1]) × Π → 𝓧ₐ₊(𝕊₊[j]) for j ∈ N₊

• Stage Kinds:

• Sequential case: gₑₐ₊ maps to unique next stage
• Branching case: gᵥₐ₊ maps to possible next stages, selection via p(j|xᵥ,𝜋)

• Source stage kind is always understood from context

• Compatibility:

• N₊ denotes the set of stage kinds that can meaningfully follow the current stage
• For sequential stages:
  • |N₊| = 1 as there is exactly one valid next stage
  • Within period: N₊ = {κ(𝕊[i+1])} where κ(s) denotes kind of stage s
  • Between periods: N₊ = {κ(𝕊₊[0])} where 𝕊₊ is the next period
• For branching stages:
  • N₊ is constrained by position and period structure:
  • Within period: N₊ ⊆ {κ(𝕊[j]) | j > i} where i is current position
  • Between periods: N₊ ⊆ {κ(𝕊₊[j]) | j ≥ 0} where 𝕊₊ is next period
  • |N₊| ≥ 1 with probabilities p(j | xᵥ, 𝜋) for each j ∈ N₊
  • Probabilities must respect N₊ constraints:
  • Only assign positive probability to valid next stages
  • Conservation: ∑_{j∈N₊} p(j|xᵥ,𝜋) = 1 ensures all mass transitions
  • Connector function gᵥₐ₊ must be well-defined for all j ∈ N₊

Setup: - Define the set of stage kinds Κ and assign each kind a type (Sequential or Branching) - For each stage kind κ ∈ Κ, define the following objects: - State spaces: - 𝓧ₐ: Arrival states - 𝓧ᵥ: Decision states - 𝓧ₑ: Continuation states - Shock spaces (see "Shock Spaces and Timing" above): - 𝒵ₐᵥ: Shock space for arvl→dcsn transition, with measure Pₐᵥ(ζₐᵥ) - 𝒵ᵥₑ: Shock space for dcsn→cntn transition, with measure Pᵥₑ(ζᵥₑ) - Either or both may be trivial (𝒵 = {∅}) - Within-stage perch transitions (with directional mapping functions): - gₐᵥ: 𝓧ₐ × 𝒵ₐᵥ → 𝓧ᵥ maps arrival and shock to decision state - gᵥₑ: 𝓧ᵥ × Π × 𝒵ᵥₑ → 𝓧ₑ maps decision, choice, and shock to continuation state - Economic primitives: - Choice set Π(xᵥ) for each decision state - Reward function r(xᵥ, 𝜋) - Discount factor β(xᵥ) - For branching stages only: - Branching probabilities p(j | xᵥ, 𝜋) for each j ∈ N₊

Branching Probabilities: - Individual Level (Decision-Making): - Each agent in decision state xᵥ choosing 𝜋: - Can only transition to stages j ∈ N₊ - Faces transition probabilities p(j|xᵥ,𝜋) for each eligible j - Probabilities must respect stage ordering: - Within period: Only to higher-index stages to prevent loops - Between periods: Only to stages present in next period - Must satisfy ∑_{j∈N₊} p(j|xᵥ,𝜋) = 1 for all xᵥ, 𝜋

• Population Level (Aggregation):
• Same probabilities determine population distribution:
  • For all branching transitions: Via gᵥₐ₊ for each branch j ∈ N₊
• Conservation properties:
  • Preserves population mass: ∑_{j∈N₊} μₐ₊ⱼ(𝓧ₐ) = μᵥ(𝓧ᵥ)
  • Preserves measure normalization: If E_μᵥ[1] = 1 then E_μₐ₊[1] = 1

Dispatch (deterministic routing by inherited state):

When the branch is determined by an inherited discrete state component ι ∈ 𝒥 (rather than by optimization or exogenous randomness), the branching probability degenerates to:

p(j | xᵥ, π) = 𝟙[j = ι]

where ι is a component of xᵥ. The decision value function becomes:

𝒱(xᵥ) = 𝒱_{succ,ι}(g_ι(xᵥ))

This is the "dispatch" mode — deterministic routing based on an inherited state component. It arises naturally when a previous period's divergent branching produces tagged union exit states (a, ι), and the current period must route agents to the appropriate branch based on ι. The dispatch mode is distinguished from stochastic branching (no probability weighting — each agent goes to exactly one branch with certainty) and from choice/optimization-based branching (the branch selection is not value-maximizing — it is determined by inherited state).

Optional State Components:

A stage's arrival state space may include components that are not always provided by the preceding connector function. Formally, the arrival state space may decompose as:

𝓧ₐ = 𝓧ₐʳᵉᵠ × 𝓧ₐᵒᵖᵗ⊥

where: - 𝓧ₐʳᵉᵠ is the space of required components (always provided by the connector) - 𝓧ₐᵒᵖᵗ⊥ = 𝓧ₐᵒᵖᵗ ∪ {⊥} is the space of optional components, extended with the sentinel value ⊥ ("absent")

Because ⊥ is a point in the extended space 𝓧ₐᵒᵖᵗ⊥, the full arrival state space remains a fixed-dimensional product space. All existing mathematical machinery — population measures, bijectivity conditions, contraction arguments — applies to this extended space without modification.

When an optional component equals ⊥, the stage determines that component internally. The specific semantics are defined per-stage. Common patterns include: - Optimize when absent: The stage treats the absent component as a choice variable and optimizes over it. When the component is provided, the choice set collapses to the singleton {provided value}. - Default when absent: The stage substitutes a default value. When the component is provided, it uses the given value.

For instance, a portfolio-and-returns stage may accept an optional portfolio share ς̄ ∈ [0,1] ∪ {⊥} as part of its arrival state. When ς̄ is provided, the stage uses that fixed share for transitions; when ς̄ = ⊥, the stage optimizes over ς. In both cases the stage can compute and report the optimal share as auxiliary output.

Although arrival states are the most common case, the same decomposition can apply to any perch state space. When stages have no optional components (the default), 𝓧ₐᵒᵖᵗ is empty and 𝓧ₐ = 𝓧ₐʳᵉᵠ, reducing to the standard formulation used throughout this document.

State Transitions and Population Dynamics:

The transition functions defined above (gₐᵥ, gᵥₑ, gₑₐ₊, gᵥₐ₊) induce a corresponding evolution of population measures through the stage structure. At each transition: - Individual-level state mappings are bijective (for each fixed shock realization) - Population measures evolve via pushforward through the transition functions - Mass and normalization are conserved through all transitions

For the complete specification of measure evolution formulas and conservation properties, see the Population Dynamics section. Key results used here: - Within-stage: μᵥ(B) = E_μₐ[P({ζₐᵥ: gₐᵥ(xₐ,ζₐᵥ) ∈ B})] and μₑ(C) = E_μᵥ[1{gᵥₑ(xᵥ,𝜋(xᵥ)) ∈ C}] - Sequential between-stage: μₐ₊(A) = E_μₑ[1{gₑₐ₊(xₑ) ∈ A}] - Branching between-stage: μₐ₊ⱼ(A) = E_μᵥ[p(j|xᵥ,𝜋(xᵥ))1{gᵥₐ₊(xᵥ,𝜋*(xᵥ)) ∈ A}]

Terminal period: No transitions from final stage 𝕊₀[-1]; terminal value ℰ₀(xₑ) specified directly.

Simulate Forward - Starting from initial population measure μₐ⁰, iterate through stages: - Apply within-stage perch transitions: 1. Arrival → Decision using gₐᵥ 2. Decision → Continuation using gᵥₑ - Apply between-stage transitions: - For sequential stages: Use gₑₐ₊ - For branching stages: Sample j ∈ N₊, then use gᵥₐ₊ - Update population measures according to transition formulas - Continue until reaching termination condition

Construct and Solve Final Period: - Define the stages 𝕊₀ for the final period - For the final stage 𝕊₀[-1]: - Specify terminal value function ℰ₀(xₑ) over 𝓧ₑ(𝕊₀[-1]) - Solve backward through stages s ∈ 𝕊₀: 1. At each decision state xᵥ: - For sequential stages within period: 𝒱(xᵥ) = max_𝜋{r(xᵥ, 𝜋) + β(xᵥ)ℰ(gᵥₑ(xᵥ, 𝜋))} - For sequential stages at period end: 𝒱(xᵥ) = max_𝜋{r(xᵥ, 𝜋) + β(xᵥ)𝒜₊(gₑₐ₊(gᵥₑ(xᵥ, 𝜋)))} - For branching stages (both within period and between periods): 𝒱(xᵥ) = max_𝜋{r(xᵥ, 𝜋) + β(xᵥ)∑_{j∈N₊} p(j|xᵥ,𝜋)𝒜₊ⱼ(gᵥₐ₊(xᵥ, 𝜋))} 2. At each arrival state: 𝒜(xₐ) = E_ζ[𝒱(gₐᵥ(xₐ, ζ))]

Construct and Solve Earlier Periods Recursively: - For each period t, working backward from the final period: - Define the stages 𝕊 for period t (e.g., 𝕊[0], 𝕊[1], …, 𝕊[-1]) - Define period-level connector functions: - For sequential stages at period end: gₑₐ₊: 𝓧ₑ(𝕊[-1]) → 𝓧ₐ(𝕊₊[0]) Maps continuation states to arrival states of next period's first stage - For branching stages: gᵥₐ₊: 𝓧ᵥ(𝕊[-1]) × Π → 𝓧ₐ(𝕊₊[j]) for each j ∈ N₊ Maps decision states to arrival states of all possible next stages - Define the stochastic shock distributions for each stage in period t - Solve the problem for period t using backward induction: 1. At each decision state xᵥ: - For sequential stages within period: 𝒱(xᵥ) = max_𝜋{r(xᵥ, 𝜋) + β(xᵥ)ℰ(gᵥₑ(xᵥ, 𝜋))} - For sequential stages at period end: 𝒱(xᵥ) = max_𝜋{r(xᵥ, 𝜋) + β(xᵥ)𝒜₊(gₑₐ₊(gᵥₑ(xᵥ, 𝜋)))} - For branching stages: 𝒱(xᵥ) = max_𝜋{r(xᵥ, 𝜋) + β(xᵥ)∑_{j∈N₊} p(j|xᵥ,𝜋)𝒜₊ⱼ(gᵥₐ₊(xᵥ, 𝜋))} 2. At each arrival state: 𝒜(xₐ) = E_ζ[𝒱(gₐᵥ(xₐ, ζ))] - Use arrival value functions 𝒜₊(xₐ) from all possible next stages

Recursive Process: - Continue backward induction until reaching either: - A chosen starting point (e.g., in life-cycle models), or - A steady state determined by convergence criteria: - Value function convergence: Compare successive iterations - Policy function stability: Check for changes in optimal choices - Population measure stability: Track distribution changes - Specific criteria depend on application needs - At each step, ensure: - Sequential transitions preserve stage ordering - Branching transitions respect valid next-stage constraints - Population measures maintain required properties - Value functions properly account for all possible transitions

Specify Initial Conditions: - Define the initial population measure μₐ⁰ over the arrival state space 𝓧ₐ(𝕊[0]) - The measure must be: - Non-negative: μₐ⁰(A) ≥ 0 for all measurable A - Normalized: E_μₐ⁰[1] = 1 - Defined on the Borel σ-algebra ℬ(𝓧ₐ)

Value Function Solution Approaches

The decision value function equation:

𝒱(xᵥ) = max_𝜋{r(xᵥ, 𝜋) + β(xᵥ)ℰ(gᵥₑ(xᵥ, 𝜋))}

May be solved through different algorithmic approaches:

1. Direct maximization: Explicitly search for the optimal 𝜋
2. First-order conditions: When the problem is differentiable:
3. ∂r/∂𝜋(xᵥ, 𝜋) + β(xᵥ)(∂ℰ/∂xₑ)(gᵥₑ(xᵥ, 𝜋))∇_𝜋gᵥₑ(xᵥ, 𝜋) = 0
4. Endogenous grid methods: Work backwards from continuation values to decision states
5. Parametric approximation: Approximate the policy function with basis functions

Each approach represents the same mathematical concept but with different computational properties.

Computational Implementation Notes

The mathematical recursive problem definition maps to computational objects as follows:

Stage Implementation

A mathematical stage maps to a stage instance in code:

# Create a computational representation of a stage
stage = Stage(stage_path="configs/stages/example")

Each stage contains three perch instances representing the three mathematical perches:

# The three perches map to mathematical state spaces and value functions
stage.perch_arvl  # Implements 𝓧ₐ and 𝒜(xₐ)
stage.perch_dcsn  # Implements 𝓧ᵥ, 𝒱(xᵥ), and policy function
stage.perch_cntn  # Implements 𝓧ₑ and ℰ(xₑ)

Transition Implementation

Mathematical transition functions map to mover instances:

# Transitions between perches in a stage
stage.mover_arvl_to_dcsn  # Implements gₐᵥ
stage.mover_dcsn_to_cntn  # Implements gᵥₑ

For each mover instance, the purely mathematical information it implements (the transition functions gₐᵥ, gᵥₑ, the pushforward formulas, and any related operator definitions given elsewhere in this document) is that mover's mover-spec—the collection of all mathematical information needed to execute the corresponding forward or backward act of creation.

Transitions, Connectors, and Movers

It is important to distinguish three kinds of objects:

• Transitions (gₐᵥ, gᵥₑ): Mathematical functions mapping state variables between perches within a stage.
• Connectors (𝒞 / 𝙲): Objects that link stages or periods. The mathematical connector 𝒞 is a pure namespace mapping (e.g., 𝒞(k_{t+1} ↔ a_t)) defined at model-specification time. The computational connector 𝙲 is the runtime object carrying the mapping plus bridging metadata. Connectors are passive once created and do not hold value functions.
• Movers (𝙼←, 𝙼→): Computational processes (mover-comps) that, when evaluated, use connectors and mover-specs to create new computational objects. The backward mover 𝙼← constructs and populates value functions on upstream perches; the forward mover 𝙼→ propagates distributions forward. Subscripts indicate (source, target) for the flow: between-period backward 𝙼←{a+,e}, within-period backward 𝙼←; between-period forward 𝙼→{e,a+}, within-period forward 𝙼→.

Note that backward induction is a sequence of backward mover (𝙼←_prd) invocations, each using a connector and populating perches on the current period. Whether the user's code creates the connector as a separate step or the backward mover creates it implicitly is a design choice (see computational-framework.md).

Contract: Pre/Postconditions for Composability

A contract specifies the preconditions that must hold before a mover or connector can operate, and the postconditions it guarantees upon completion. This concept, inspired by Hoare logic ({P} C {Q}), ensures composability: stages and periods can be freely reordered or substituted so long as contracts are satisfied.

Example — Shock-free consumption stage backward mover: - Precondition {P}: Continuation-value function v_cntn(a) exists on the cntn perch. - Postcondition {Q}: Arrival-value function v_arvl(m) and optimal policy c(m) exist on the arvl and dcsn perches respectively, with v_arvl(m) = 𝔼[v_dcsn(m)] and c(m) = argmax_c{u(c) + v_cntn(m−c)}.

Computational Functions

The computational functions are exposed through the .comp attribute:

# Access mathematical functions in computational form
stage.perch_arvl.comp.value_function(state)  # Implements 𝒜(xₐ)
stage.perch_dcsn.comp.value_function(state)  # Implements 𝒱(xᵥ)
stage.perch_dcsn.comp.dcsn_rule(state)      # Implements policy function
stage.perch_cntn.comp.value_function(state)  # Implements ℰ(xₑ)

Solution Process vs. Mathematical Structure

The mathematical formulation describes operators (maximization, expectation) applied to value functions. In the computational implementation, these operations are handled by the whisperer and horse:

# Mathematical operators are implemented internally by the whisperer/horse
whisperer.solve_stage(stage)  # Implements both maximization and expectation

Branching Implementation

Mathematical branching (where an agent's state might evolve in multiple possible ways) is implemented using a DAG structure in the computational framework:

# Create period with branching stages
period = Period(period_id="example")
period.add_stage("consumption", consumption_stage)
period.add_stage("portfolio", portfolio_stage)
period.add_stage("work", work_stage)

# Define mathematical branching through connections
period.connect_stages("consumption", "portfolio")
period.connect_stages("consumption", "work")

This implementation note provides a bridge between the abstract mathematical concepts and their concrete computational representations, helping users translate between the mathematical formulation and code implementation.

Christopher Carroll and Akshay Shanker — repository in development, please do not cite.