AFTD Auto-Formalizing Theoretical Domains

not_single_box_valid_is_partially_adaptive

theoremverifiedoriginal

The statement single_box_valid_is_partially_adaptive is false: The statement is false. IsValidPolicy only constrains the continuation cont v for values v ∈ (inst.dist b).support. In contrast, IsPartiallyAdaptive requires aux order (cont v) for ALL v : ℝ. Because the real line has infinitely many values outside the finite support of the distribution, an adversary policy can make the depth of cont v grow unboundedly with v (e.g. chain (Nat.floor (max 0 v))). Such a policy satisfies IsValidPolicy (since for v ∈ support = {0}, the continuation is stop), but cannot satisfy IsPartiallyAdaptive because any predetermined order : List (Fin n) is finite and cannot bound execution branches of arbitrary depth.

Statement

theorem not_single_box_valid_is_partially_adaptive : ¬ (∀ (inst : PandoraDeadlineInstance) (h1 : inst.n = 1)
    (π : AdaptivePolicy inst.n) (hπ : IsValidPolicy inst π), IsPartiallyAdaptive π)
Related work
refutes `single_box_valid_is_partially_adaptive`
Verified
26 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 6
  • PandoraDeadlineInstanceAn instance of Pandora's problem with deadlines consisting of n boxes, each with a non-negative opening cost, a positive integer deadline,…
  • 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…
  • 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…
  • DiscreteDistA discrete probability distribution with finite support on non-negative real values, defined by a finite support set, non-negative…

The proof, explained

The theorem disproves the claim by constructing an explicit single-box counterexample with deadline 1 and a reward distribution supported only on {0}. While policy validity (`IsValidPolicy`) only constrains continuation policies on outcomes within the distribution's support, the definition of partial adaptiveness (`IsPartiallyAdaptive`) universally quantifies over all real outcomes v ∈ ℝ. We construct an adversary policy that immediately stops when v = 0 (making it valid), but continues with a chain of ⌊max 0 v⌋ box openings for arbitrary v. Since any candidate execution order for partial adaptiveness is a finite list, evaluating the continuation at v = length + 1 forces an execution chain of depth exceeding the list's length, deriving a contradiction.

  1. Define a family of policies `chain k` that sequentially opens box 0 exactly k times before stopping.

    For each natural number k, `chain k` is defined by recursion on k: `chain 0` is the terminating policy `AdaptivePolicy.stop`, and `chain (k + 1)` opens box 0 and continues as `chain k` regardless of the observed value.

    lines 3–4

      let chain : ℕ → AdaptivePolicy 1 := fun k =>
        Nat.recOn k AdaptivePolicy.stop (fun _ ih => AdaptivePolicy.openBox 0 (fun _ => ih))
  2. Any opening sequence witnessing partial adaptiveness for `chain k` must have length at least k.

    We proceed by induction on k. For k = 0, the inequality 0 ≤ order.length holds trivially. For k + 1, the policy opens box 0. If order is empty, unfolding `IsPartiallyAdaptive.aux` via `IsPartiallyAdaptive.aux.eq_def` immediately yields False. If order is b :: rest, `IsPartiallyAdaptive.aux.eq_def` requires that rest witnesses partial adaptiveness for the continuation at every real value v; evaluating at v = 0 gives that rest is valid for `chain k`. By the induction hypothesis, k ≤ rest.length, and rewriting with `List.length_cons` confirms k + 1 ≤ (b :: rest).length.

    lines 5–22

    uses IsPartiallyAdaptive.aux.eq_def, List.length_cons

      have aux_chain_length : ∀ (k : ℕ) (order : List (Fin 1)),
          IsPartiallyAdaptive.aux order (chain k) → k ≤ order.length := by
        intro k
        induction k with
        | zero => intros; simp
        | succ k ih =>
          intro order h
          cases order with
          | nil =>
            change IsPartiallyAdaptive.aux [] (AdaptivePolicy.openBox 0 (fun _ => chain k)) at h
            rw [IsPartiallyAdaptive.aux.eq_def] at h
            contradiction
          | cons b rest =>
            change IsPartiallyAdaptive.aux (b :: rest) (AdaptivePolicy.openBox 0 (fun _ => chain k)) at h
            rw [IsPartiallyAdaptive.aux.eq_def] at h
            have := ih rest (h.2 0)
            simp only [List.length_cons]
            omega
  3. Construct a single-box instance `myInst` with deadline 1 and deterministic reward 0.

    We define a discrete probability distribution `myDist` supported solely on {0} with probability 1 at 0, verifying that probabilities and values are non-negative and sum to 1. We then assemble `myInst` as an instance with 1 box, zero cost, deadline 1, and distribution `myDist`.

    lines 23–37

      let myDist : DiscreteDist := {
        support := {0}
        prob := fun v => if v = 0 then 1 else 0
        prob_nonneg := by intro v hv; aesop
        sum_prob_one := by simp
        val_nonneg := by intro v hv; aesop
      }
      let myInst : PandoraDeadlineInstance := {
        n := 1
        cost := fun _ => 0
        deadline := fun _ => 1
        dist := fun _ => myDist
        cost_nonneg := by intro _; norm_num
        deadline_pos := by intro _; norm_num
      }
  4. Define an adversary policy `bad_policy` whose continuation depth grows unboundedly with the outcome value.

    `bad_policy` opens box 0 and, upon receiving value v ∈ ℝ, continues as `chain ⌊max 0 v⌋`. If v ≤ 0, this continuation is `chain 0 = stop`, but for large v, it opens box 0 arbitrarily many times.

    lines 38–39

      let bad_policy : AdaptivePolicy 1 :=
        .openBox 0 (fun v => chain (Nat.floor (max 0 v)))
  5. `bad_policy` is a valid policy for the instance `myInst`.

    By unfolding validity with `IsValidPolicyAux.eq_def`, we check that box 0 has not yet been opened, that the deadline constraint 0 + 1 ≤ 1 holds, and that the continuation is valid for all values v in `myDist.support`. By `Finset.mem_singleton`, the only value in the support is v = 0. For v = 0, ⌊max 0 0⌋ = 0, so the continuation is `chain 0 = AdaptivePolicy.stop`. Applying `IsValidPolicyAux.eq_def` again confirms that the stopping policy is valid.

    lines 40–53

    uses IsValidPolicyAux.eq_def, Finset.mem_singleton

      have bad_policy_valid : IsValidPolicy myInst bad_policy := by
        dsimp [IsValidPolicy]
        rw [IsValidPolicyAux.eq_def]
        refine ⟨by simp, by decide, ?_⟩
        intro v hv
        change v ∈ myDist.support at hv
        simp only [myDist, Finset.mem_singleton] at hv
        subst hv
        have : Nat.floor (max 0 (0 : ℝ)) = 0 := by simp
        change IsValidPolicyAux myInst rfl [0] (chain (Nat.floor (max 0 0)))
        rw [this]
        change IsValidPolicyAux myInst rfl [0] AdaptivePolicy.stop
        rw [IsValidPolicyAux.eq_def]
        trivial
  6. `bad_policy` is not partially adaptive.

    Suppose for contradiction that `bad_policy` is partially adaptive, so there is an execution order with `IsPartiallyAdaptive.aux order bad_policy`. The list cannot be empty by `IsPartiallyAdaptive.aux.eq_def`. If order = b :: rest, `IsPartiallyAdaptive.aux.eq_def` requires that rest witnesses partial adaptiveness for the continuation at ALL real numbers v. Specializing to v = rest.length + 1, since v ≥ 0 by `Nat.cast_nonneg` and `max_eq_right`, we have ⌊max 0 v⌋ = rest.length + 1 by `Nat.floor_natCast`. The continuation is therefore `chain (rest.length + 1)`. Applying `aux_chain_length` then gives rest.length + 1 ≤ rest.length, an integer arithmetic contradiction.

    lines 54–73

    uses IsPartiallyAdaptive.aux.eq_def, Nat.cast_nonneg, max_eq_right, Nat.floor_natCast

      have not_pa : ¬ IsPartiallyAdaptive bad_policy := by
        intro ⟨order, h⟩
        cases order with
        | nil =>
          simp only [bad_policy] at h
          rw [IsPartiallyAdaptive.aux.eq_def] at h
          contradiction
        | cons b rest =>
          simp only [bad_policy] at h
          rw [IsPartiallyAdaptive.aux.eq_def] at h
          rcases h with ⟨-, hcont⟩
          have h_v := hcont ((rest.length + 1 : ℕ) : ℝ)
          dsimp only at h_v
          have h_floor : Nat.floor (max 0 (((rest.length + 1 : ℕ) : ℝ))) = rest.length + 1 := by
            have h0 : (0 : ℝ) ≤ ((rest.length + 1 : ℕ) : ℝ) := Nat.cast_nonneg _
            rw [max_eq_right h0]
            exact Nat.floor_natCast (rest.length + 1)
          rw [h_floor] at h_v
          have h_le := aux_chain_length (rest.length + 1) rest h_v
          omega
  7. Conclude the theorem by contradiction.

    Assuming the universal statement holds, specializing it to `myInst` and `bad_policy` implies that `bad_policy` is partially adaptive, which directly contradicts `not_pa`.

    lines 74–76

      intro h
      have h_pa := h myInst rfl bad_policy bad_policy_valid
      exact not_pa h_pa
IsPartiallyAdaptive.aux.eq_def
Unfolds the recursive definition of `IsPartiallyAdaptive.aux`: stopping is always valid, opening a box with an empty list is false, and opening box b' with sequence b :: rest requires b' = b and that the continuation at every real value v satisfies `IsPartiallyAdaptive.aux rest`.
List.length_cons
The length of prepending an element to a list is one more than the original length: (a :: as).length = as.length + 1.
IsValidPolicyAux.eq_def
Unfolds the recursive definition of `IsValidPolicyAux`: stopping is valid, while opening box b requires that b has not yet been opened, the number of opened boxes does not exceed the deadline, and the continuation is valid for all outcomes in the support of b's distribution.
Finset.mem_singleton
An element b belongs to the singleton set {a} if and only if b = a.
Nat.cast_nonneg
The coercion of any natural number into an ordered semiring (such as ℝ) is non-negative: 0 ≤ (n : ℝ).
max_eq_right
If a ≤ b, then max a b = b.
Nat.floor_natCast
The floor of a natural number cast to the real numbers is the natural number itself: ⌊(n : ℝ)⌋ = n.

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

theorem not_single_box_valid_is_partially_adaptive : ¬ (∀ (inst : PandoraDeadlineInstance) (h1 : inst.n = 1)    (π : AdaptivePolicy inst.n) (hπ : IsValidPolicy inst π), IsPartiallyAdaptive π) := by  let chain : ℕ → AdaptivePolicy 1 := fun k =>    Nat.recOn k AdaptivePolicy.stop (fun _ ih => AdaptivePolicy.openBox 0 (fun _ => ih))  have aux_chain_length : ∀ (k : ℕ) (order : List (Fin 1)),      IsPartiallyAdaptive.aux order (chain k) → k ≤ order.length := by    intro k    induction k with    | zero => intros; simp    | succ k ih =>      intro order h      cases order with      | nil =>        change IsPartiallyAdaptive.aux [] (AdaptivePolicy.openBox 0 (fun _ => chain k)) at h        rw [IsPartiallyAdaptive.aux.eq_def] at h        contradiction      | cons b rest =>        change IsPartiallyAdaptive.aux (b :: rest) (AdaptivePolicy.openBox 0 (fun _ => chain k)) at h        rw [IsPartiallyAdaptive.aux.eq_def] at h        have := ih rest (h.2 0)        simp only [List.length_cons]        omega  let myDist : DiscreteDist := {    support := {0}    prob := fun v => if v = 0 then 1 else 0    prob_nonneg := by intro v hv; aesop    sum_prob_one := by simp    val_nonneg := by intro v hv; aesop  }  let myInst : PandoraDeadlineInstance := {    n := 1    cost := fun _ => 0    deadline := fun _ => 1    dist := fun _ => myDist    cost_nonneg := by intro _; norm_num    deadline_pos := by intro _; norm_num  }  let bad_policy : AdaptivePolicy 1 :=    .openBox 0 (fun v => chain (Nat.floor (max 0 v)))  have bad_policy_valid : IsValidPolicy myInst bad_policy := by    dsimp [IsValidPolicy]    rw [IsValidPolicyAux.eq_def]    refine ⟨by simp, by decide, ?_⟩    intro v hv    change v ∈ myDist.support at hv    simp only [myDist, Finset.mem_singleton] at hv    subst hv    have : Nat.floor (max 0 (0 : ℝ)) = 0 := by simp    change IsValidPolicyAux myInst rfl [0] (chain (Nat.floor (max 0 0)))    rw [this]    change IsValidPolicyAux myInst rfl [0] AdaptivePolicy.stop    rw [IsValidPolicyAux.eq_def]    trivial  have not_pa : ¬ IsPartiallyAdaptive bad_policy := by    intro ⟨order, h⟩    cases order with    | nil =>      simp only [bad_policy] at h      rw [IsPartiallyAdaptive.aux.eq_def] at h      contradiction    | cons b rest =>      simp only [bad_policy] at h      rw [IsPartiallyAdaptive.aux.eq_def] at h      rcases h with ⟨-, hcont⟩      have h_v := hcont ((rest.length + 1 : ℕ) : ℝ)      dsimp only at h_v      have h_floor : Nat.floor (max 0 (((rest.length + 1 : ℕ) : ℝ))) = rest.length + 1 := by        have h0 : (0 : ℝ) ≤ ((rest.length + 1 : ℕ) : ℝ) := Nat.cast_nonneg _        rw [max_eq_right h0]        exact Nat.floor_natCast (rest.length + 1)      rw [h_floor] at h_v      have h_le := aux_chain_length (rest.length + 1) rest h_v      omega  intro h  have h_pa := h myInst rfl bad_policy bad_policy_valid  exact not_pa h_pa
See it in the graphDiscuss this resultChallenge it