Proof of Theorem 1, pp. ec1–ec2 — the balanced tree (EC.1)–(EC.4) has 2^N leaves, one per assortment, depth N + 1, and satisfies Requirement 3
ProvedDecisionForest.Universal.fullTree_specdecision-treediscrete-choicep2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1
Let and let assign a purchase option to every assortment. Let be the balanced tree of the proof of Theorem 1: every split at distance from the root checks product (, equations (EC.1)–(EC.4)), and the leaf reached by assortment carries the option . Then:
- for every assortment , a customer following and offered purchases :
- has exactly leaves;
- ;
- satisfies Requirement 3.
Item 1 is the one-to-one correspondence between the leaves of the tree and the assortments; items 3 and 4 place in as soon as it also satisfies Requirement 2.
Formalization Note The tuple is a function o : Finset (Fin N) → Option (Fin N) and is fullTree o, which splits on the products 0, …, N-1 (the paper's ) level by level.
Differences from the source:
- encoding: leaves enumerated left to right and matched with assortments → leaves indexed directly by assortments, the correspondence stated as ; reason: same tree and same correspondence, no enumeration needed.
- encoding: products →
Fin N(product isk - 1); reason: Lean convention, same instances. - reading: the proof uses that each constructed tree satisfies Requirement 3 (so that the trees kept lie in ) without stating it → stated as clause 4; reason: it is what "a distribution over " in Theorem 1 requires of the constructed trees.
Preamble
import Mathlib import Definitions.Def_DecisionForest_Universal_Setting
Formal statement
namespace DecisionForest.Universal
theorem fullTree_spec (N : ℕ) (o : Finset (Fin N) → Option (Fin N)) :
(∀ S : Finset (Fin N), choose (fullTree o) S = o S) ∧ numLeaves (fullTree o) = 2 ^ N ∧
depth (fullTree o) = N + 1 ∧ Req3 (fullTree o) := by sorry
end DecisionForest.Universal
Source
Chen and Mišić, Decision Forest: A Nonparametric Approach to Modeling Irrational Choice, arXiv:1904.11532v3, pp. ec1–ec2 (PDF 30–31), proof of Theorem 1, (EC.1)–(EC.4) and the paragraph after Figure EC.2
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.