AFTD Auto-Formalizing Theoretical Domains

pandora_threshold_policy_valid

theoremverified

A threshold policy on a duplicate-free list whose j-th box has deadline at least j is a valid policy and is partially adaptive.

Statement

theorem pandora_threshold_policy_valid (inst : PandoraDeadlineInstance) (t : ℝ)
    (order : List (Fin inst.n)) (hnd : order.Nodup)
    (hdl : ∀ (j : ℕ) (hj : j < order.length), j + 1 ≤ inst.deadline (order.get ⟨j, hj⟩)) :
    IsValidPolicy inst (pandora_threshold_policy order t) ∧
      IsPartiallyAdaptive (pandora_threshold_policy order t)
Source
Helper for op184_partially_adaptive_half_approximation: arXiv:2610.13775 Section 3, Theorem 1 proof (the algorithm respects deadlines and is partially adaptive)
Verified
26 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 10
  • PandoraDeadlineInstanceAn instance of Pandora's problem with deadlines consisting of n boxes, each with a non-negative opening cost, a positive integer deadline,…
  • DiscreteDistA discrete probability distribution with finite support on non-negative real values, defined by a finite support set, non-negative…
  • 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…
  • IsValidPolicyA policy is valid for a Pandora's problem instance with deadlines if it respects opening deadlines and never opens any box more than once.
  • IsPartiallyAdaptiveA search policy π : AdaptivePolicy n for Pandora's problem is partially adaptive if there exists a predetermined ordered list of boxes…
  • expectedUtilityDUSThe expected net utility of an adaptive policy π : AdaptivePolicy inst.n under deferred-until-stopping commitment on a Pandora's problem…
  • 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…
  • IsValidPolicyAuxA policy execution is valid if it never re-opens an already opened box, respects the deadline of each opened box, and remains valid on all…
  • pandora_threshold_policy_nilSanity: the threshold policy on the empty list stops at once.
  • pandora_threshold_policy_consSanity: the threshold policy on b :: rest opens b, stops if its value exceeds t, and otherwise continues with the threshold policy on rest.
Used by 1

The proof, explained

The theorem proves that a threshold policy with threshold t following box order `order` is both partially adaptive and valid, assuming `order` contains no duplicates and each box's deadline permits it to be opened in turn. Partial adaptiveness is proved by induction on the list of boxes: the policy commits to the predetermined box order, stopping only when the observed prize exceeds t. Validity is established by generalizing to an auxiliary induction over remaining boxes with an accumulator of already opened boxes, verifying at each step that the next box is unopened, on time, and preserves disjointness and deadline bounds for the subsequent boxes. Finally, the main result specializes this auxiliary validity to an initially empty set of opened boxes and combines it with partial adaptiveness.

  1. Partial adaptiveness of the threshold policy reduces to induction on the box order, and holds trivially for the empty list.

    To prove that the threshold policy is partially adaptive, we witness the execution order using `order` and proceed by induction on `order`. In the base case where `order` is empty, the policy is `.stop`, which is trivially partially adaptive.

    lines 3–5

      use order
      induction' order with b rest ih
      · trivial
  2. In the inductive step, the threshold policy on b :: rest is partially adaptive.

    Rewriting with `pandora_threshold_policy_cons` and unfolding the definition of `IsPartiallyAdaptive.aux`, opening box b must lead to partially adaptive continuations for every observed value v. A case split on whether t < v shows that if v > t, the policy stops, which is partially adaptive for any remaining list; if v ≤ t, the policy continues with `pandora_threshold_policy rest t`, which is partially adaptive by the induction hypothesis.

    lines 6–11

    uses pandora_threshold_policy_cons

      · rw [pandora_threshold_policy_cons]
        dsimp [IsPartiallyAdaptive.aux]
        refine ⟨rfl, fun v => ?_⟩
        split_ifs
        · cases rest <;> trivial
        · exact ih
  3. For an empty remaining list of boxes, the threshold policy is valid with respect to any list of already opened boxes.

    We set up an induction on the remaining boxes `rem`, generalizing over the accumulator `opened` of boxes opened so far. In the base case rem = [], the policy is `.stop` by `pandora_threshold_policy_nil`, which vacuously satisfies the validity condition `IsValidPolicyAux`.

    lines 19–21

    uses pandora_threshold_policy_nil

      induction' rem with b rest ih generalizing opened
      · rw [pandora_threshold_policy_nil]
        trivial
  4. For a nonempty list of remaining boxes b :: rest, box b is valid to open: it has not been opened yet, satisfies its deadline, and stopping when v > t is valid.

    Rewriting with `pandora_threshold_policy_cons` and unfolding `IsValidPolicyAux`, opening b requires verifying three obligations. First, b ∉ opened holds because b ∈ b :: rest by `List.mem_cons_self` and `rem` is disjoint from `opened` by hypothesis `hdisj`. Second, |opened| + 1 ≤ deadline(b) follows from the deadline hypothesis `hdl` at index 0, using `Nat.succ_pos`. Third, if the prize v exceeds threshold t, the policy stops, which is trivially valid.

    lines 22–28

    uses pandora_threshold_policy_cons, List.mem_cons_self, Nat.succ_pos

      · rw [pandora_threshold_policy_cons]
        dsimp [IsValidPolicyAux]
        have hb_not_in : b ∉ opened := hdisj b List.mem_cons_self
        have hdl_b : opened.length + 1 ≤ inst.deadline b := hdl 0 (Nat.succ_pos rest.length)
        refine ⟨hb_not_in, hdl_b, fun v hv => ?_⟩
        split_ifs
        · trivial
  5. When the observed value satisfies v ≤ t, the remaining boxes rest have no duplicates and remain disjoint from b :: opened.

    When v ≤ t, the policy proceeds with `pandora_threshold_policy rest t` and the updated opened list b :: opened. We apply the induction hypothesis for b :: opened. The first obligation, `rest.Nodup`, follows from (b :: rest).Nodup via `List.nodup_cons.mp`. The second obligation requires that every x ∈ rest is not in b :: opened. By `List.mem_cons.mp`, if x ∈ b :: opened, then either x = b, which contradicts b ∉ rest by `List.nodup_cons.mp`, or x ∈ opened, which contradicts the disjointness of b :: rest and opened using `List.mem_cons_of_mem`.

    lines 29–35

    uses List.nodup_cons.mp, List.mem_cons.mp, List.mem_cons_of_mem

        · apply ih (b :: opened)
          · exact (List.nodup_cons.mp hnd).2
          · intro x hx h_in
            rcases List.mem_cons.mp h_in with heq | h_in_opened
            · subst heq
              exact (List.nodup_cons.mp hnd).1 hx
            · exact hdisj x (List.mem_cons_of_mem b hx) h_in_opened
  6. The deadline condition is preserved for every remaining box in rest when the opened list is extended to b :: opened.

    To verify the final precondition of the induction hypothesis, let j index a box in rest. Its index in b :: rest is j + 1, with index inequality preserved by `Nat.succ_lt_succ`. The original deadline hypothesis at index j + 1 states that |opened| + (j + 1) + 1 ≤ deadline((b :: rest)[j+1]). Since the (j+1)-th element of b :: rest is identical to the j-th element of rest, and |b :: opened| + j + 1 = |opened| + 1 + j + 1 = |opened| + (j + 1) + 1, the inequality holds by linear integer arithmetic (`omega`).

    lines 36–41

    uses Nat.succ_lt_succ

          · intro j hj
            have h := hdl (j + 1) (Nat.succ_lt_succ hj)
            change (opened.length + 1) + j + 1 ≤ inst.deadline (rest.get ⟨j, hj⟩)
            have heq : (b :: rest).get ⟨j + 1, Nat.succ_lt_succ hj⟩ = rest.get ⟨j, hj⟩ := rfl
            rw [← heq]
            omega
  7. The main conjunction splits into partial adaptiveness and validity, reducing the latter to the auxiliary lemma with an initially empty list of opened boxes.

    We split the goal into two parts: partial adaptiveness is established directly by `pandora_threshold_policy_valid_partially_adaptive`, while validity reduces by `pandora_threshold_policy_valid_aux` applied to the full list `order` and an initially empty opened list opened = [].

    lines 48–49

    uses pandora_threshold_policy_valid_partially_adaptive, pandora_threshold_policy_valid_aux

      refine ⟨?_, pandora_threshold_policy_valid_partially_adaptive order t⟩
      apply pandora_threshold_policy_valid_aux inst t [] order hnd
  8. The initial conditions for an empty opened list hold, concluding the proof of the theorem.

    The disjointness precondition ∀ x ∈ order, x ∉ [] holds vacuously because the empty list contains no elements (`List.not_mem_nil`). The deadline precondition [].length + j + 1 ≤ deadline(order[j]) simplifies to j + 1 ≤ deadline(order[j]), which is given directly by hypothesis `hdl`.

    lines 50–53

    uses List.not_mem_nil

      · intro x _ h_in
        exact List.not_mem_nil h_in
      · intro j hj
        simpa using hdl j hj
pandora_threshold_policy_cons
Expanding the threshold policy on a nonempty list b :: rest yields a policy that opens box b, stops if the observed value exceeds threshold t, and continues with the threshold policy on rest otherwise.
pandora_threshold_policy_nil
The threshold policy on an empty list of boxes stops immediately without opening any box.
List.mem_cons_self
The head element of a nonempty list belongs to that list.
Nat.succ_pos
The successor of any natural number is strictly positive.
List.nodup_cons.mp
If a list a :: l has no duplicate elements, then a is not in l and l has no duplicates.
List.mem_cons.mp
An element belongs to a :: l if and only if it equals a or belongs to l.
List.mem_cons_of_mem
If an element belongs to a list l, then it also belongs to y :: l for any element y.
Nat.succ_lt_succ
If n < m, then n + 1 < m + 1.
pandora_threshold_policy_valid_partially_adaptive
A threshold policy on any list of boxes with threshold t is partially adaptive.
pandora_threshold_policy_valid_aux
A threshold policy on remaining boxes rem is valid relative to already opened boxes opened, provided rem has no duplicates, is disjoint from opened, and satisfies all deadline constraints.
List.not_mem_nil
No element belongs to the empty list.

Written by a model (gemini-3.8-flash) from the Lean proof and the goal states Lean reported at each step. Lean verified the proof; this explanation is a reading aid and is not itself machine-checked.

Lean source view module on GitHub

lemma pandora_threshold_policy_valid_partially_adaptive {n : ℕ} (order : List (Fin n)) (t : ℝ) :    IsPartiallyAdaptive (pandora_threshold_policy order t) := by  use order  induction' order with b rest ih  · trivial  · rw [pandora_threshold_policy_cons]    dsimp [IsPartiallyAdaptive.aux]    refine ⟨rfl, fun v => ?_⟩    split_ifs    · cases rest <;> trivial    · exact ihlemma pandora_threshold_policy_valid_aux (inst : PandoraDeadlineInstance) (t : ℝ)    (opened : List (Fin inst.n)) (rem : List (Fin inst.n))    (hnd : rem.Nodup)    (hdisj : ∀ x ∈ rem, x ∉ opened)    (hdl : ∀ (j : ℕ) (hj : j < rem.length), opened.length + j + 1 ≤ inst.deadline (rem.get ⟨j, hj⟩)) :    IsValidPolicyAux inst rfl opened (pandora_threshold_policy rem t) := by  induction' rem with b rest ih generalizing opened  · rw [pandora_threshold_policy_nil]    trivial  · rw [pandora_threshold_policy_cons]    dsimp [IsValidPolicyAux]    have hb_not_in : b ∉ opened := hdisj b List.mem_cons_self    have hdl_b : opened.length + 1 ≤ inst.deadline b := hdl 0 (Nat.succ_pos rest.length)    refine ⟨hb_not_in, hdl_b, fun v hv => ?_⟩    split_ifs    · trivial    · apply ih (b :: opened)      · exact (List.nodup_cons.mp hnd).2      · intro x hx h_in        rcases List.mem_cons.mp h_in with heq | h_in_opened        · subst heq          exact (List.nodup_cons.mp hnd).1 hx        · exact hdisj x (List.mem_cons_of_mem b hx) h_in_opened      · intro j hj        have h := hdl (j + 1) (Nat.succ_lt_succ hj)        change (opened.length + 1) + j + 1 ≤ inst.deadline (rest.get ⟨j, hj⟩)        have heq : (b :: rest).get ⟨j + 1, Nat.succ_lt_succ hj⟩ = rest.get ⟨j, hj⟩ := rfl        rw [← heq]        omegatheorem pandora_threshold_policy_valid (inst : PandoraDeadlineInstance) (t : ℝ)    (order : List (Fin inst.n)) (hnd : order.Nodup)    (hdl : ∀ (j : ℕ) (hj : j < order.length), j + 1 ≤ inst.deadline (order.get ⟨j, hj⟩)) :    IsValidPolicy inst (pandora_threshold_policy order t) ∧      IsPartiallyAdaptive (pandora_threshold_policy order t) := by  refine ⟨?_, pandora_threshold_policy_valid_partially_adaptive order t⟩  apply pandora_threshold_policy_valid_aux inst t [] order hnd  · intro x _ h_in    exact List.not_mem_nil h_in  · intro j hj    simpa using hdl j hj
See it in the graphDiscuss this resultChallenge it