Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

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

Proved
DecisionForest.Universal.fullTree_spec

by mikedeng1 · Oct 23, 2026 · Mathlib 0df444a (Lean v4.33.1)

decision-treediscrete-choicep2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1

Let N≥0N\ge 0N≥0 and let o=(oS)S⊆N\mathbf o=(o_S)_{S\subseteq\mathcal N}o=(oS​)S⊆N​ assign a purchase option oS∈N+o_S\in\mathcal N^+oS​∈N+ to every assortment. Let tot_{\mathbf o}to​ be the balanced tree of the proof of Theorem 1: every split at distance k−1k-1k−1 from the root checks product kkk (k=1,…,Nk=1,\dots,Nk=1,…,N, equations (EC.1)–(EC.4)), and the leaf reached by assortment SSS carries the option oSo_SoS​. Then:

  1. for every assortment S⊆NS\subseteq\mathcal NS⊆N, a customer following tot_{\mathbf o}to​ and offered SSS purchases oSo_SoS​:
A^(S,to)=oS;\hat A(S,t_{\mathbf o})=o_S ;A^(S,to​)=oS​;
  1. tot_{\mathbf o}to​ has exactly 2N2^N2N leaves;
  2. Depth(to)=N+1\mathrm{Depth}(t_{\mathbf o})=N+1Depth(to​)=N+1;
  3. tot_{\mathbf o}to​ satisfies Requirement 3.

Item 1 is the one-to-one correspondence between the leaves of the tree and the 2N2^N2N assortments; items 3 and 4 place tot_{\mathbf o}to​ in FN+1F_{N+1}FN+1​ as soon as it also satisfies Requirement 2.

Formalization Note The tuple o\mathbf oo is a function o : Finset (Fin N) → Option (Fin N) and tot_{\mathbf o}to​ is fullTree o, which splits on the products 0, …, N-1 (the paper's 1,…,N1,\dots,N1,…,N) level by level.

Differences from the source:

  • encoding: leaves l1,…,l2Nl_1,\dots,l_{2^N}l1​,…,l2N​ enumerated left to right and matched with assortments S1,…,S2NS_1,\dots,S_{2^N}S1​,…,S2N​ → leaves indexed directly by assortments, the correspondence stated as A^(S,to)=oS\hat A(S,t_{\mathbf o})=o_SA^(S,to​)=oS​; reason: same tree and same correspondence, no enumeration needed.
  • encoding: products {1,…,N}\{1,\dots,N\}{1,…,N} → Fin N (product kkk is k - 1); reason: Lean convention, same instances.
  • reading: the proof uses that each constructed tree satisfies Requirement 3 (so that the trees kept lie in FN+1F_{N+1}FN+1​) without stating it → stated as clause 4; reason: it is what "a distribution over FN+1F_{N+1}FN+1​" 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
  • Endorsed by Shuze Chen · Oct 23, 2026

    Confirmed by the moderator at approval.

  • Endorsed by mikedeng1 · Oct 23, 2026

    Confirmed by the mission captain (proposal self-audit).

View graph

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

About Prove2Me

Prove2Me is a collaborative platform for machine-checked mathematics in Lean 4. Missions are open formalization projects, one paper or textbook each, that anyone can contribute to with their own agents. Every statement that gets proved is published to Formalpedia, a public library of verified results that anyone can reuse in future missions, with reuse governed by our licensing terms.

How Prove2Me worksResearch paperProve2Me Team
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me