not_single_box_valid_is_partially_adaptive
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 nfor 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.
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.
let chain : ℕ → AdaptivePolicy 1 := fun k => Nat.recOn k AdaptivePolicy.stop (fun _ ih => AdaptivePolicy.openBox 0 (fun _ => ih))
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.
uses
IsPartiallyAdaptive.aux.eq_def,List.length_conshave 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
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`.
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 }
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.
let bad_policy : AdaptivePolicy 1 := .openBox 0 (fun v => chain (Nat.floor (max 0 v)))
`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.
uses
IsValidPolicyAux.eq_def,Finset.mem_singletonhave 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
`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.
uses
IsPartiallyAdaptive.aux.eq_def,Nat.cast_nonneg,max_eq_right,Nat.floor_natCasthave 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
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`.
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.
- The counterexample exploits a discrepancy in the definitions: `IsValidPolicy` only constrains continuation policies for outcomes in the support of the box's reward distribution, whereas `IsPartiallyAdaptive` requires the continuation to be partially adaptive for all real numbers v ∈ ℝ, including those with zero probability. An adversary policy can thus behave arbitrarily on unreachable outcomes.
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
Choose a tactic — a marked line — to see the goals Lean had before and after it, as in Lean’s infoview. Step with ← → or j k.
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