opt_dtd_le_opt_dus
For every Pandora's problem instance with deadlines inst : PandoraDeadlineInstance, the optimal expected utility under deferred-to-deadline commitment optDTD inst is at most the optimal expected utility under deferred-until-stopping commitment optDUS inst.
Statement
theorem opt_dtd_le_opt_dus (inst : PandoraDeadlineInstance) :
optDTD inst ≤ optDUS inst- Formalizes
- arXiv:2610.13775 Sec. 2.1
- Verified
- 19 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 10
- optDTDThe optimal expected net utility
optDTD instunder deferred-to-deadline commitment for a Pandora's problem instance with deadlines… - optDUSThe optimal expected net utility
optDUS instunder deferred-until-stopping commitment for a Pandora's problem instance with deadlines… - expected_utility_dtd_le_dusFor every Pandora's problem instance with deadlines
inst : PandoraDeadlineInstanceand every adaptive policy… - 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…
- DiscreteDistA discrete probability distribution with finite support on non-negative real values, defined by a finite support set, non-negative…
- PandoraDeadlineInstanceAn instance of Pandora's problem with deadlines consisting of n boxes, each with a non-negative opening cost, a positive integer deadline,…
- expectedUtilityDTDThe expected net utility of an adaptive policy
π : AdaptivePolicy inst.nunder deferred-to-deadline commitment on a Pandora's problem… - expectedUtilityDUSThe expected net utility of an adaptive policy
π : AdaptivePolicy inst.nunder deferred-until-stopping commitment on a Pandora's problem… - 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.
- supportThe support $\mathrm{supp}(p) \subseteq \mathrm{Fin}\,n$ consists of coordinates where $p(i) \neq I$; the weight is…
- optDTDThe optimal expected net utility
Read back from the Lean
For every Pandora deadline instance inst, the optimal expected utility under the deadline-to-decision model (optDTD inst) is less than or equal to the optimal expected utility under the deadline-upon-stopping model (optDUS inst).
Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.
The proof, explained
The proof shows that the optimal expected utility under deferred-to-deadline commitment (optDTD) is at most that under deferred-until-stopping commitment (optDUS) by comparing policies pointwise. Because DTD allows claiming a box only if stopping occurs before that box's deadline while DUS allows claiming any opened box upon stopping, every policy achieves at least as much expected utility under DUS as under DTD (`expected_utility_dtd_le_dus`). To lift this pointwise inequality to the supremum over all valid policies via `ciSup_mono`, the proof establishes that DUS utilities are bounded above by the sum of all possible prize values (`opt_dtd_le_opt_dus_bddAbove`), using structural induction on policies and an auxiliary bound on list fold-max operations.
Folding `max` over the empty list starting at x is at most max(x, M). automation
For an empty list `[]`, `List.foldl` returns the initial accumulator x. Since x ≤ max(x, M) holds for any M, the base case is closed immediately by simplification.
open Finset in /-- A `List.foldl` of `max` starting at `x` is at most `max x M` when every entry is at most `M`. -/ lemma opt_dtd_le_opt_dus_foldl_max_le {α : Type*} : ∀ (l : List (α × ℝ)) (x M : ℝ), (∀ bv ∈ l, bv.2 ≤ M) → List.foldl (fun acc bv => max acc bv.2) x l ≤ max x M | [], x, M, _ => by simp
If every element in hd :: tl has its second component bounded by M, folding `max` over hd :: tl starting at x is at most max(x, M).
The head satisfies hd.2 ≤ M. Unfolding `List.foldl` on a cons list updates the accumulator to max(x, hd.2). By the induction hypothesis on the tail tl, folding over tl is at most max(max(x, hd.2), M). By associativity of `max` and the fact that max(hd.2, M) = M since hd.2 ≤ M, this bound simplifies to max(x, M).
uses
List.foldl_cons,le_trans,opt_dtd_le_opt_dus_foldl_max_le,List.mem_cons_of_mem,max_assoc,max_eq_right| hd :: tl, x, M, h => by have h1 : hd.2 ≤ M := h hd (by simp) simp only [List.foldl_cons] refine le_trans (opt_dtd_le_opt_dus_foldl_max_le tl (max x hd.2) M (fun bv hbv => h bv (List.mem_cons_of_mem _ hbv))) ?_ rw [max_assoc, max_eq_right h1]
For the stopping policy `AdaptivePolicy.stop`, the deferred-until-stopping expected utility from any history bounded by M ≥ 0 is at most M.
We proceed by structural induction on the adaptive policy. When the policy stops, its utility is defined as folding `max` over the history starting at 0. Applying our list-folding lemma (`opt_dtd_le_opt_dus_foldl_max_le`) shows the result is at most max(0, M), which equals M because 0 ≤ M.
uses
le_trans,opt_dtd_le_opt_dus_foldl_max_le,max_eq_right/-- If every value that can be revealed lies below `M ≥ 0`, then the deferred-until-stopping expected utility of any policy is at most `M`. -/ lemma opt_dtd_le_opt_dus_aux_bound (inst : PandoraDeadlineInstance) (M : ℝ) (hM0 : 0 ≤ M) (hMv : ∀ (i : Fin inst.n) (v : ℝ), v ∈ (inst.dist i).support → v ≤ M) : ∀ (a : AdaptivePolicy inst.n) (hist : List (Fin inst.n × ℝ)), (∀ bv ∈ hist, bv.2 ≤ M) → expectedUtilityDUS.aux inst hist a ≤ M := by intro a induction a using AdaptivePolicy.rec with | stop => intro hist hh rw [show expectedUtilityDUS.aux inst hist (AdaptivePolicy.stop : AdaptivePolicy inst.n) = List.foldl (fun acc bv => max acc bv.2) 0 hist from rfl] exact le_trans (opt_dtd_le_opt_dus_foldl_max_le hist 0 M hh) (by rw [max_eq_right hM0])
For an open-box policy `AdaptivePolicy.openBox b cont`, the deferred-until-stopping expected utility from any history bounded by M is at most M.
Opening box b yields the expected utility of the continuation policies minus the box opening cost cost(b). For each revealed prize value v in the support of box b, the extended history (b, v) :: hist remains bounded by M because v ≤ M by assumption and the previous history is bounded by hypothesis. By the induction hypothesis, each continuation utility is at most M. Because probabilities are non-negative and sum to 1, the expected continuation utility is at most ∑ v, prob(v) * M = M. Finally, since the opening cost is non-negative, subtracting it leaves a quantity at most M.
uses
Finset.sum_le_sum,mul_le_mul_of_nonneg_left,List.mem_cons.mp,Finset.sum_mul,one_mul| openBox b cont ih => intro hist hh rw [show expectedUtilityDUS.aux inst hist (AdaptivePolicy.openBox b cont) = ∑ v ∈ (inst.dist b).support, (inst.dist b).prob v * expectedUtilityDUS.aux inst ((b, v) :: hist) (cont v) - inst.cost b from rfl] have hsum : ∑ v ∈ (inst.dist b).support, (inst.dist b).prob v * expectedUtilityDUS.aux inst ((b, v) :: hist) (cont v) ≤ M := by have h1 : ∑ v ∈ (inst.dist b).support, (inst.dist b).prob v * expectedUtilityDUS.aux inst ((b, v) :: hist) (cont v) ≤ ∑ v ∈ (inst.dist b).support, (inst.dist b).prob v * M := by apply Finset.sum_le_sum intro v hv apply mul_le_mul_of_nonneg_left _ ((inst.dist b).prob_nonneg v hv) exact ih v ((b, v) :: hist) (fun bv hbv => by rcases List.mem_cons.mp hbv with hmem | hmem · rw [hmem]; exact hMv b v hv · exact hh bv hmem) calc ∑ v ∈ (inst.dist b).support, (inst.dist b).prob v * expectedUtilityDUS.aux inst ((b, v) :: hist) (cont v) ≤ ∑ v ∈ (inst.dist b).support, (inst.dist b).prob v * M := h1 _ = (∑ v ∈ (inst.dist b).support, (inst.dist b).prob v) * M := by rw [Finset.sum_mul] _ = M := by rw [(inst.dist b).sum_prob_one, one_mul] linarith [inst.cost_nonneg b]The set of deferred-until-stopping expected utilities across all adaptive policies is bounded above.
We choose the candidate bound B = ∑ i, ∑ v ∈ (inst.dist i).support, v. Since all prize values are non-negative, B ≥ 0, and every possible revealed prize value v is a single term in this finite sum and therefore satisfies v ≤ B. Applying `opt_dtd_le_opt_dus_aux_bound` with empty history, the expected utility of every policy π is bounded above by B.
uses
opt_dtd_le_opt_dus_aux_bound,Finset.sum_nonneg,le_trans,Finset.single_le_sum,Finset.mem_univ/-- The family of deferred-until-stopping expected utilities over all policies is bounded above by the total mass of the value distributions. -/ lemma opt_dtd_le_opt_dus_bddAbove (inst : PandoraDeadlineInstance) : BddAbove (Set.range fun π : AdaptivePolicy inst.n => expectedUtilityDUS inst π) := by refine ⟨∑ i : Fin inst.n, ∑ v ∈ (inst.dist i).support, v, ?_⟩ rintro _ ⟨π, rfl⟩ apply opt_dtd_le_opt_dus_aux_bound inst _ ?_ ?_ π [] (by simp) · exact Finset.sum_nonneg fun i _ => Finset.sum_nonneg fun v hv => (inst.dist i).val_nonneg v hv · intro i v hv refine le_trans (Finset.single_le_sum (f := fun v => v) (fun v hv => (inst.dist i).val_nonneg v hv) hv) ?_ exact Finset.single_le_sum (f := fun i => ∑ v ∈ (inst.dist i).support, v) (fun i _ => Finset.sum_nonneg fun v hv => (inst.dist i).val_nonneg v hv) (Finset.mem_univ i) /-- The deferred-to-deadline optimum is at most the deferred-until-stopping optimum. -/
The policy-indexed family of suprema ⨆ (_ : IsValidPolicy inst π), expectedUtilityDUS inst π is bounded above.
By `BddAbove.range_iSup_of_iUnion_range`, it suffices to bound the union of ranges over all valid policies. Every element of this union is the expected utility of some policy under deferred-until-stopping commitment, so the global bound from `opt_dtd_le_opt_dus_bddAbove` bounds the entire union.
uses
BddAbove.range_iSup_of_iUnion_range,opt_dtd_le_opt_dus_bddAbove,Set.mem_iUnion,Set.mem_range,Set.mem_range_selftheorem opt_dtd_le_opt_dus (inst : PandoraDeadlineInstance) : optDTD inst ≤ optDUS inst := by have hbdd : BddAbove (Set.range fun π : AdaptivePolicy inst.n => ⨆ (_ : IsValidPolicy inst π), expectedUtilityDUS inst π) := by refine BddAbove.range_iSup_of_iUnion_range ?_ obtain ⟨B, hB⟩ := opt_dtd_le_opt_dus_bddAbove inst refine ⟨B, ?_⟩ intro x hx simp only [Set.mem_iUnion, Set.mem_range] at hx obtain ⟨π, -, rfl⟩ := hx exact hB (Set.mem_range_self π)
The optimal expected utility under deferred-to-deadline commitment is at most that under deferred-until-stopping commitment: optDTD inst ≤ optDUS inst.
Unfolding `optDTD` and `optDUS`, we apply monotonicity of the supremum (`ciSup_mono`) using the boundedness established in the previous step. For each policy π, we split into cases on whether π is valid: if π is valid, the inner supremum simplifies via `ciSup_const` to `expectedUtilityDTD inst π`, which by `expected_utility_dtd_le_dus` is at most `expectedUtilityDUS inst π`, and this in turn is at most the supremum over valid policies by `le_ciSup`. If π is invalid, both inner suprema are over an empty type and both evaluate to sSup ∅ by `iSup_of_empty'`.
uses
ciSup_mono,ciSup_const,expected_utility_dtd_le_dus,le_ciSup,le_rfl,iSup_of_empty'unfold optDTD optDUS refine ciSup_mono hbdd (fun π => ?_) by_cases hv : IsValidPolicy inst π · have hn : Nonempty (IsValidPolicy inst π) := ⟨hv⟩ calc (⨆ (_ : IsValidPolicy inst π), expectedUtilityDTD inst π) = expectedUtilityDTD inst π := ciSup_const _ ≤ expectedUtilityDUS inst π := expected_utility_dtd_le_dus inst π _ ≤ ⨆ (_ : IsValidPolicy inst π), expectedUtilityDUS inst π := le_ciSup ⟨expectedUtilityDUS inst π, by rintro _ ⟨_, rfl⟩; exact le_rfl⟩ hv · have he : IsEmpty (IsValidPolicy inst π) := ⟨fun h => hv h⟩ rw [iSup_of_empty' (fun _ : IsValidPolicy inst π => expectedUtilityDTD inst π), iSup_of_empty' (fun _ : IsValidPolicy inst π => expectedUtilityDUS inst π)]
List.foldl_cons- Folding an operation over a list `a :: l` starting from accumulator `b` equals folding over `l` starting from `f b a`.
le_trans- Inequality is transitive: if a ≤ b and b ≤ c, then a ≤ c.
opt_dtd_le_opt_dus_foldl_max_le- Folding `max` over a list whose second components are all bounded by M, starting from x, is at most max(x, M).
List.mem_cons_of_mem- An element of a list l is also an element of y :: l.
max_assoc- The maximum operation on a linear order is associative: max(max(a, b), c) = max(a, max(b, c)).
max_eq_right- If a ≤ b, then max(a, b) = b.
Finset.sum_le_sum- A finite sum of pointwise smaller terms is less than or equal to the sum of the larger terms.
mul_le_mul_of_nonneg_left- Multiplying an inequality b ≤ c on the left by a non-negative number a preserves the inequality: a * b ≤ a * c.
List.mem_cons.mp- An element of a cons list a :: l is either equal to a or belongs to l.
Finset.sum_mul- Multiplication by a constant distributes over finite summation on the right: (∑ i ∈ s, f i) * a = ∑ i ∈ s, f i * a.
one_mul- Multiplying any element by 1 on the left leaves it unchanged: 1 * a = a.
opt_dtd_le_opt_dus_aux_bound- If all values in the support of every box distribution are bounded by M ≥ 0, then the deferred-until-stopping expected utility of any policy from any history bounded by M is at most M.
Finset.sum_nonneg- A finite sum of non-negative elements is non-negative.
Finset.single_le_sum- Any single term in a finite sum of non-negative elements is at most the total sum.
Finset.mem_univ- Every element of a finite type belongs to its universal finset Finset.univ.
BddAbove.range_iSup_of_iUnion_range- If the union of the ranges of a family of functions is bounded above, then the range of their pointwise suprema is also bounded above.
opt_dtd_le_opt_dus_bddAbove- The set of expected utilities under deferred-until-stopping commitment across all adaptive policies is bounded above.
Set.mem_iUnion- An element belongs to an indexed union if and only if it belongs to at least one set in the family.
Set.mem_range- An element belongs to the range of a function if and only if it is the image of some input.
Set.mem_range_self- Every value in the image of a function belongs to the range of that function.
ciSup_mono- If g has a range that is bounded above and f(x) ≤ g(x) pointwise, then ⨆ x, f x ≤ ⨆ x, g x.
ciSup_const- The supremum of a constant function over a nonempty index type equals the constant itself.
expected_utility_dtd_le_dus- For every adaptive policy π, its expected utility under deferred-to-deadline commitment is at most its expected utility under deferred-until-stopping commitment.
le_ciSup- Any value in the range of a function that is bounded above is at most the supremum of that function.
le_rfl- The order relation ≤ is reflexive: a ≤ a.
iSup_of_empty'- The supremum of a function indexed by an empty type equals the supremum of the empty set.
- In Step 4, linear arithmetic (`linarith`) is used to close the inequality after bounding the expectation, using non-negativity of the box opening cost `inst.cost_nonneg b`.
- In Step 7, for invalid policies `¬IsValidPolicy inst π`, both suprema are indexed by an empty type; in Mathlib's conditionally complete lattice convention, the supremum of an empty family is formally defined as `sSup ∅`, making the two sides equal via `iSup_of_empty'`.
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.
open Finset in/-- A `List.foldl` of `max` starting at `x` is at most `max x M` when every entry is at most `M`. -/lemma opt_dtd_le_opt_dus_foldl_max_le {α : Type*} : ∀ (l : List (α × ℝ)) (x M : ℝ), (∀ bv ∈ l, bv.2 ≤ M) → List.foldl (fun acc bv => max acc bv.2) x l ≤ max x M | [], x, M, _ => by simp | hd :: tl, x, M, h => by have h1 : hd.2 ≤ M := h hd (by simp) simp only [List.foldl_cons] refine le_trans (opt_dtd_le_opt_dus_foldl_max_le tl (max x hd.2) M (fun bv hbv => h bv (List.mem_cons_of_mem _ hbv))) ?_ rw [max_assoc, max_eq_right h1]/-- If every value that can be revealed lies below `M ≥ 0`, then the deferred-until-stoppingexpected utility of any policy is at most `M`. -/lemma opt_dtd_le_opt_dus_aux_bound (inst : PandoraDeadlineInstance) (M : ℝ) (hM0 : 0 ≤ M) (hMv : ∀ (i : Fin inst.n) (v : ℝ), v ∈ (inst.dist i).support → v ≤ M) : ∀ (a : AdaptivePolicy inst.n) (hist : List (Fin inst.n × ℝ)), (∀ bv ∈ hist, bv.2 ≤ M) → expectedUtilityDUS.aux inst hist a ≤ M := by intro a induction a using AdaptivePolicy.rec with | stop => intro hist hh rw [show expectedUtilityDUS.aux inst hist (AdaptivePolicy.stop : AdaptivePolicy inst.n) = List.foldl (fun acc bv => max acc bv.2) 0 hist from rfl] exact le_trans (opt_dtd_le_opt_dus_foldl_max_le hist 0 M hh) (by rw [max_eq_right hM0]) | openBox b cont ih => intro hist hh rw [show expectedUtilityDUS.aux inst hist (AdaptivePolicy.openBox b cont) = ∑ v ∈ (inst.dist b).support, (inst.dist b).prob v * expectedUtilityDUS.aux inst ((b, v) :: hist) (cont v) - inst.cost b from rfl] have hsum : ∑ v ∈ (inst.dist b).support, (inst.dist b).prob v * expectedUtilityDUS.aux inst ((b, v) :: hist) (cont v) ≤ M := by have h1 : ∑ v ∈ (inst.dist b).support, (inst.dist b).prob v * expectedUtilityDUS.aux inst ((b, v) :: hist) (cont v) ≤ ∑ v ∈ (inst.dist b).support, (inst.dist b).prob v * M := by apply Finset.sum_le_sum intro v hv apply mul_le_mul_of_nonneg_left _ ((inst.dist b).prob_nonneg v hv) exact ih v ((b, v) :: hist) (fun bv hbv => by rcases List.mem_cons.mp hbv with hmem | hmem · rw [hmem]; exact hMv b v hv · exact hh bv hmem) calc ∑ v ∈ (inst.dist b).support, (inst.dist b).prob v * expectedUtilityDUS.aux inst ((b, v) :: hist) (cont v) ≤ ∑ v ∈ (inst.dist b).support, (inst.dist b).prob v * M := h1 _ = (∑ v ∈ (inst.dist b).support, (inst.dist b).prob v) * M := by rw [Finset.sum_mul] _ = M := by rw [(inst.dist b).sum_prob_one, one_mul] linarith [inst.cost_nonneg b]/-- The family of deferred-until-stopping expected utilities over all policies is bounded aboveby the total mass of the value distributions. -/lemma opt_dtd_le_opt_dus_bddAbove (inst : PandoraDeadlineInstance) : BddAbove (Set.range fun π : AdaptivePolicy inst.n => expectedUtilityDUS inst π) := by refine ⟨∑ i : Fin inst.n, ∑ v ∈ (inst.dist i).support, v, ?_⟩ rintro _ ⟨π, rfl⟩ apply opt_dtd_le_opt_dus_aux_bound inst _ ?_ ?_ π [] (by simp) · exact Finset.sum_nonneg fun i _ => Finset.sum_nonneg fun v hv => (inst.dist i).val_nonneg v hv · intro i v hv refine le_trans (Finset.single_le_sum (f := fun v => v) (fun v hv => (inst.dist i).val_nonneg v hv) hv) ?_ exact Finset.single_le_sum (f := fun i => ∑ v ∈ (inst.dist i).support, v) (fun i _ => Finset.sum_nonneg fun v hv => (inst.dist i).val_nonneg v hv) (Finset.mem_univ i)/-- The deferred-to-deadline optimum is at most the deferred-until-stopping optimum. -/theorem opt_dtd_le_opt_dus (inst : PandoraDeadlineInstance) : optDTD inst ≤ optDUS inst := by have hbdd : BddAbove (Set.range fun π : AdaptivePolicy inst.n => ⨆ (_ : IsValidPolicy inst π), expectedUtilityDUS inst π) := by refine BddAbove.range_iSup_of_iUnion_range ?_ obtain ⟨B, hB⟩ := opt_dtd_le_opt_dus_bddAbove inst refine ⟨B, ?_⟩ intro x hx simp only [Set.mem_iUnion, Set.mem_range] at hx obtain ⟨π, -, rfl⟩ := hx exact hB (Set.mem_range_self π) unfold optDTD optDUS refine ciSup_mono hbdd (fun π => ?_) by_cases hv : IsValidPolicy inst π · have hn : Nonempty (IsValidPolicy inst π) := ⟨hv⟩ calc (⨆ (_ : IsValidPolicy inst π), expectedUtilityDTD inst π) = expectedUtilityDTD inst π := ciSup_const _ ≤ expectedUtilityDUS inst π := expected_utility_dtd_le_dus inst π _ ≤ ⨆ (_ : IsValidPolicy inst π), expectedUtilityDUS inst π := le_ciSup ⟨expectedUtilityDUS inst π, by rintro _ ⟨_, rfl⟩; exact le_rfl⟩ hv · have he : IsEmpty (IsValidPolicy inst π) := ⟨fun h => hv h⟩ rw [iSup_of_empty' (fun _ : IsValidPolicy inst π => expectedUtilityDTD inst π), iSup_of_empty' (fun _ : IsValidPolicy inst π => expectedUtilityDUS inst π)]