Theorem 1, p. 11 — every customer choice model is a decision forest model over the purchase decision trees of depth at most N + 1
ProvedDecisionForest.Universal.theorem_1Consider products and the purchase options , where is the no-purchase option. A customer choice model gives, for every assortment (the empty one included), a probability distribution on with for every product . Let be the set of purchase decision trees that satisfy Requirements 1–3 of §3.2 and have depth at most , and for a finite forest with weights let be the decision forest model (3).
Theorem 1. For every customer choice model there is a probability distribution over such that
for every assortment and every purchase option .
The theorem says that the decision forest model is universal: it represents every choice model, whether or not it is a random utility model or satisfies regularity, and trees of depth always suffice.
Formalization Note The distribution is given by a finite set F of trees contained in (FSet N (N + 1)) and weights lam that are nonnegative on F and sum to one over F; weights outside F never enter. Products are Fin N, options Option (Fin N) with none the no-purchase option, assortments Finset (Fin N).
Differences from the source:
- encoding: a distribution over → a finite set with weights nonnegative on summing to one over ; reason: is finite (p. 8), so every distribution on it is of this form (take or its support), and when vanishes off .
- encoding: products →
Fin N(product isk - 1), options →Option (Fin N)withnonethe option ; reason: Lean convention, same instances. - encoding: Requirement 1 → built into the type of trees
PTree N; reason: every split carries a product by construction, same trees.
import Mathlib import Definitions.Def_DecisionForest_Universal_Setting
namespace DecisionForest.Universal
theorem theorem_1 (N : ℕ) (P : Option (Fin N) → Finset (Fin N) → ℝ) (hP : IsChoiceModel P) :
∃ (F : Finset (PTree N)) (lam : PTree N → ℝ),
(↑F ⊆ FSet N (N + 1)) ∧ (∀ t ∈ F, 0 ≤ lam t) ∧ ∑ t ∈ F, lam t = 1 ∧
∀ (S : Finset (Fin N)) (o : Option (Fin N)), P o S = forestProb F lam o S := by sorry
end DecisionForest.Universal
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.