Greedy investment sequence proof sketch

greedy-portfolio-sequence-theorem-sketch.md

# Theorem: Nested Optimal Investment Portfolios

Consider a set of investment opportunities {1,...,n} with:
- Base returns μᵢ (ordered so μ₁ > μ₂ > ... > μₙ)
- Pairwise interaction terms fᵢⱼ representing complementarities/substitutions between investments
- Unit costs (each investment costs 1)

Let V(P) = Σᵢ∈P μᵢ + Σᵢ,ⱼ∈P fᵢⱼ be the total value of portfolio P.
Let P*ₖ be the optimal portfolio of size k.

## Statement

The optimal portfolios are nested (P*ₖ ⊂ P*ₖ₊₁ for all k) if and only if for all k and m > k:

Σᵢ∈P*ₖ (fᵢₘ - fᵢ,ₖ₊₁) < μₖ₊₁ - μₘ

### Economic Interpretation
- LHS represents the net interaction advantage from choosing asset m instead of k+1, considering all interactions with the existing optimal k-portfolio
- RHS represents the direct return advantage of choosing k+1 over m
- The condition requires that the direct return advantage always exceeds any possible interaction advantages from skipping ahead

## Proof of Sufficiency

We prove by induction that P*ₖ = {1,...,k} for all k, which implies the nested structure.

### Base Case (k=1)
- V({i}) = μᵢ for any single asset i
- Since μ₁ > μᵢ for all i>1, P*₁ = {1}

### Inductive Step
Assume P*ₖ = {1,...,k} for some k ≥ 1. We need to prove P*ₖ₊₁ = {1,...,k+1}.

To show this, we must rule out all other possible k+1 size portfolios. These come in two types:

#### Case 1 (About the next addition)
Given we have {1,...,k}, is k+1 the best next asset to add?
- For any m > k+1, our condition directly ensures:
 μₖ₊₁ - μₘ > Σᵢ≤ₖ (fᵢₘ - fᵢ,ₖ₊₁)
- Therefore adding k+1 beats adding any higher-indexed asset

#### Case 2 (About keeping P*ₖ)
Could we do better by dropping some i ≤ k when we expand to size k+1?
- Any such portfolio is dominated because:
 1. P*ₖ is optimal at size k (by inductive hypothesis)
 2. By Case 1, adding k+1 to P*ₖ beats adding any m > k+1 to P*ₖ

Therefore P*ₖ₊₁ must equal P*ₖ ∪ {k+1} = {1,...,k+1}, completing the induction.