AFTD Auto-Formalizing Theoretical Domains

pandora_threshold_policy_cons

theoremverified

Sanity: the threshold policy on b :: rest opens b, stops if its value exceeds t, and otherwise continues with the threshold policy on rest.

Statement

theorem pandora_threshold_policy_cons {n : ℕ} (b : Fin n) (rest : List (Fin n)) (t : ℝ) :
    pandora_threshold_policy (b :: rest) t =
      .openBox b (fun v => if t < v then .stop else pandora_threshold_policy rest t)
Source
Sanity lemma for the definitions of arXiv:2610.13775 Section 3
Verified
26 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 3
  • pandora_threshold_policyThe threshold policy on a list of boxes: open them in the given order and stop as soon as an opened value exceeds t (stop after the last…
  • pandora_deadline_feasibleA set S of boxes is deadline-feasible if for every j at most j of its boxes have deadline at most j (equivalently, by Lemma 2, its boxes…
  • AdaptivePolicyA fully adaptive search policy for Pandora's problem with n boxes, represented as a decision tree that at each step either stops or opens…
Used by 1
  • pandora_threshold_policy_validA threshold policy on a duplicate-free list whose j-th box has deadline at least j is a valid policy and is partially adaptive.

The proof, explained

The statement holds by definitional equality. Because `pandora_threshold_policy` is defined via `List.foldr`, unfolding the definition on a cons-cell `b :: rest` immediately yields an opening step for box `b` that transitions to `pandora_threshold_policy rest t` whenever the opened value does not exceed `t`. Reflexivity (`rfl`) closes the goal.

  1. The threshold policy on a list `b :: rest` evaluates definitionally to opening box `b`, stopping if the observed value exceeds `t`, and continuing with `pandora_threshold_policy rest t` otherwise.

    The policy `pandora_threshold_policy` is defined as a right fold (`List.foldr`) over the list of boxes with base value `AdaptivePolicy.stop`. Applying `foldr` to `b :: rest` unrolls by definition into `AdaptivePolicy.openBox b (fun v => if t < v then AdaptivePolicy.stop else pandora_threshold_policy rest t)`. Because both sides of the equation are definitionally equal, the proof is completed by reflexivity (`rfl`).

    line 3

          .openBox b (fun v => if t < v then .stop else pandora_threshold_policy rest t) := rfl

Written by a model (gemini-3.8-flash) from the Lean source alone (no goal states were available). Lean verified the proof; this explanation is a reading aid and is not itself machine-checked.

Lean source view module on GitHub

theorem pandora_threshold_policy_cons {n : ℕ} (b : Fin n) (rest : List (Fin n)) (t : ℝ) :    pandora_threshold_policy (b :: rest) t =      .openBox b (fun v => if t < v then .stop else pandora_threshold_policy rest t) := rfl
See it in the graphDiscuss this resultChallenge it