Proof of Theorem 1, p. ec3 — the forest of all (N + 1)^{2^N} balanced trees with weights (EC.5) reproduces P(o | S)
ProvedDecisionForest.Universal.forest_marginaldecision-forestdiscrete-choicep2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1
Let be a discrete choice model on products. For every tuple of purchase options let be the balanced tree of the proof of Theorem 1 and its weight (EC.5). Then for every assortment and every option ,
the sum running over all tuples.
The left-hand side is the decision forest model (3) of the forest with weights , before the trees violating Requirement 2 are removed; this identity is the last step of the proof of Theorem 1.
Formalization Note The sum is over all functions o : Finset (Fin N) → Option (Fin N), and is if choose (fullTree o) S = o' then 1 else 0.
Differences from the source:
- encoding: the forest of trees and → the sum over tuples of ; reason: the trees of the forest are indexed by the tuples, same sum.
- encoding: products →
Fin N, options →Option (Fin N)withnonethe option ; reason: Lean convention, same instances.
Preamble
import Mathlib import Definitions.Def_DecisionForest_Universal_Setting
Formal statement
namespace DecisionForest.Universal
theorem forest_marginal (N : ℕ) (P : Option (Fin N) → Finset (Fin N) → ℝ)
(hP : IsChoiceModel P) (S : Finset (Fin N)) (o' : Option (Fin N)) :
∑ o : Finset (Fin N) → Option (Fin N),
prodWeight P o * (if choose (fullTree o) S = o' then 1 else 0) = P o' S := by sorry
end DecisionForest.Universal
Source
Chen and Mišić, Decision Forest: A Nonparametric Approach to Modeling Irrational Choice, arXiv:1904.11532v3, p. ec3 (PDF 32), proof of Theorem 1, final display
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.