op182_deferred_to_deadline_beyond_half_self_benchmark
Open Problem OP-182 against the deferred-to-deadline benchmark: there exists a constant c > 1/2 such that for every Pandora's problem instance with deadlines inst : PandoraDeadlineInstance, there exists a valid adaptive policy π satisfying IsValidPolicy inst π whose expected utility under deferred-to-deadline commitment expectedUtilityDTD inst π is at least c * optDTD inst.
Statement
theorem op182_deferred_to_deadline_beyond_half_self_benchmark :
∃ c > (1 / 2 : ℝ), ∀ inst : PandoraDeadlineInstance,
∃ π : AdaptivePolicy inst.n, IsValidPolicy inst π ∧
c * optDTD inst ≤ expectedUtilityDTD inst π- Formalizes
- arXiv:2610.13775 Sec. 5
- Verified
- 19 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 5
- optDTDThe optimal expected net utility
optDTD instunder deferred-to-deadline commitment for a Pandora's problem instance with deadlines… - expectedUtilityDTDThe expected net utility of an adaptive policy
π : AdaptivePolicy inst.nunder deferred-to-deadline 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.
- 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…
- PandoraDeadlineInstanceAn instance of Pandora's problem with deadlines consisting of n boxes, each with a non-negative opening cost, a positive integer deadline,…
- optDTDThe optimal expected net utility
Read back from the Lean
There exists a real number $c > 1/2$ such that for every Pandora's box deadline instance inst, there exists an adaptive policy $\pi$ on inst.n boxes such that $\pi$ is valid for inst (IsValidPolicy inst π) and $c \cdot \mathrm{optDTD}(\mathrm{inst}) \le \mathrm{expectedUtilityDTD}(\mathrm{inst}, \pi)$.
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 theorem proves that an adaptive policy achieves at least a $3/4$ fraction of the `optDTD` benchmark for any Pandora's box instance with deadlines. In this formalisation, `optDTD` is defined as the supremum of expected utilities over all valid adaptive policies—a self-benchmark. Because the trivial stopping policy is valid and yields utility 0, this supremum is non-negative. By standard properties of the supremum on $\mathbb{R}$, any factor $c < 1$ (here chosen as $c = 3/4 > 1/2$) is achieved by some valid policy if the supremum is positive, or by the stopping policy if the supremum is zero.
Any nonempty family of real numbers taking at least one non-negative value contains an element achieving at least $3/4$ of the family's supremum.
We introduce the index type $\iota$, the function $f$, and an index $i_0$ with $f(i_0) \ge 0$. We split on whether the range of $f$ is bounded above (`BddAbove (Set.range f)`). If it is, $0 \le f(i_0) \le \sup f$ by `le_ciSup`. We then split on whether $\sup f > 0$ or $\sup f \le 0$ via `lt_or_ge`: if $\sup f > 0$, multiplying by $3/4 < 1$ (`mul_lt_mul_of_pos_right`) gives $(3/4) \sup f < \sup f$, so by `exists_lt_of_lt_ciSup` some index $i$ satisfies $(3/4) \sup f < f(i)$, hence $(3/4) \sup f \le f(i)$ by `le_of_lt`; if $\sup f \le 0$, antisymmetry (`le_antisymm`) forces $\sup f = 0$, so $(3/4) \sup f = 0 \le f(i_0)$ by `mul_zero`. If the range is not bounded above, Lean defines $\sup f = 0$ (`Real.iSup_of_not_bddAbove`), and again $(3/4) \cdot 0 = 0 \le f(i_0)$ via `mul_zero`.
uses
le_ciSup,lt_or_ge,mul_lt_mul_of_pos_right,exists_lt_of_lt_ciSup,le_of_lt,le_antisymm,mul_zero,Real.iSup_of_not_bddAbovehave key : ∀ (ι : Type), Nonempty ι → ∀ f : ι → ℝ, (∃ i, 0 ≤ f i) → ∃ i, (3/4:ℝ) * (⨆ i, f i) ≤ f i := by intro ι hι f h0 haveI := hι by_cases hb : BddAbove (Set.range f) · have hle : (0:ℝ) ≤ ⨆ i, f i := by obtain ⟨i, hi⟩ := h0 exact hi.trans (le_ciSup hb i) rcases lt_or_ge 0 (⨆ i, f i) with h | h · have hlt : (3/4:ℝ) * (⨆ i, f i) < ⨆ i, f i := by have := mul_lt_mul_of_pos_right (by norm_num : (3/4:ℝ) < 1) h simpa using this obtain ⟨i, hi⟩ := exists_lt_of_lt_ciSup (f := f) hlt exact ⟨i, le_of_lt hi⟩ · obtain ⟨i, hi⟩ := h0 exact ⟨i, by rw [le_antisymm h hle, mul_zero]; exact hi⟩ · rw [Real.iSup_of_not_bddAbove hb] obtain ⟨i, hi⟩ := h0 exact ⟨i, by rw [mul_zero]; exact hi⟩
We fix the approximation constant $c = 3/4 > 1/2$ and introduce an arbitrary instance `inst`.
We provide $3/4$ as the existential witness for $c$, verify that $3/4 > 1/2$ by arithmetic evaluation (`norm_num`), and introduce the arbitrary instance `inst`.
refine ⟨3/4, by norm_num, fun inst => ?_⟩ -- the stop-now policy is valid and gives utility `0`, hence the supremum is nonnegative
The supremum of expected utilities over valid policies is non-negative, as witnessed by the immediate stopping policy.
We exhibit the immediate stopping policy `AdaptivePolicy.stop`. Since stopping without opening any box is trivially valid, the supremum over the proposition `IsValidPolicy inst AdaptivePolicy.stop` evaluates by `ciSup_pos` to the expected utility of `AdaptivePolicy.stop`. By definition, stopping immediately incurs zero costs and collects zero reward, yielding utility $0$; hence $0 \le 0$ holds by equality (`le_of_eq`).
uses
ciSup_pos,le_of_eqhave h0 : ∃ π : AdaptivePolicy inst.n, 0 ≤ ⨆ (_ : IsValidPolicy inst π), expectedUtilityDTD inst π := by refine ⟨AdaptivePolicy.stop, ?_⟩ rw [ciSup_pos (show IsValidPolicy inst AdaptivePolicy.stop from trivial)] exact le_of_eq (show expectedUtilityDTD inst AdaptivePolicy.stop = 0 from rfl).symm
There exists a policy $\pi$ whose conditional expected utility supremum is at least $(3/4) \mathrm{optDTD}(\mathrm{inst})$.
We apply the helper lemma `key` to the type `AdaptivePolicy inst.n` (inhabited by `AdaptivePolicy.stop`) and the function mapping each policy $\pi$ to $\sup_{h : \mathrm{IsValidPolicy\ inst\ }\pi} \mathrm{expectedUtilityDTD\ inst\ }\pi$, using the non-negativity witness $h_0$. Because the supremum of this function over all policies is by definition $\mathrm{optDTD}(\mathrm{inst})$, we obtain a policy $\pi$ satisfying $(3/4) \mathrm{optDTD}(\mathrm{inst}) \le \sup_{h : \mathrm{IsValidPolicy\ inst\ }\pi} \mathrm{expectedUtilityDTD\ inst\ }\pi$.
obtain ⟨π, hπ⟩ := key (AdaptivePolicy inst.n) ⟨AdaptivePolicy.stop⟩ (fun π => ⨆ (_ : IsValidPolicy inst π), expectedUtilityDTD inst π) h0 have hπ' : (3/4:ℝ) * optDTD inst ≤ ⨆ (_ : IsValidPolicy inst π), expectedUtilityDTD inst π := hπ
If $\pi$ is valid, it satisfies the required inequality $(3/4) \mathrm{optDTD}(\mathrm{inst}) \le \mathrm{expectedUtilityDTD}(\mathrm{inst}, \pi)$.
We case split on whether $\pi$ is valid (`IsValidPolicy inst π`). In the valid case, `ciSup_pos` reduces the supremum over the true proposition `IsValidPolicy inst π` directly to $\mathrm{expectedUtilityDTD}(\mathrm{inst}, \pi)$, proving that $\pi$ is a valid policy achieving at least $(3/4) \mathrm{optDTD}(\mathrm{inst})$.
uses
ciSup_posby_cases hv : IsValidPolicy inst π · exact ⟨π, hv, by rwa [ciSup_pos hv] at hπ'⟩
If $\pi$ is invalid, then $\mathrm{optDTD}(\mathrm{inst}) \le 0$, and the trivial stopping policy satisfies the inequality.
If $\pi$ is not valid, the proposition `IsValidPolicy inst π` is uninhabited, so its index type is empty. The supremum over an empty set of real numbers evaluates to $0$ (`Real.iSup_of_isEmpty`), implying $(3/4) \mathrm{optDTD}(\mathrm{inst}) \le 0$. The stopping policy `AdaptivePolicy.stop` is unconditionally valid and has utility $0 \ge (3/4) \mathrm{optDTD}(\mathrm{inst})$, satisfying the goal.
uses
Real.iSup_of_isEmpty· -- for an invalid policy the supremum over `IsValidPolicy inst π` is empty, hence `0` have hempty : (⨆ (_ : IsValidPolicy inst π), expectedUtilityDTD inst π) = 0 := by haveI : IsEmpty (IsValidPolicy inst π) := ⟨fun h => hv h⟩ exact Real.iSup_of_isEmpty _ rw [hempty] at hπ' exact ⟨AdaptivePolicy.stop, trivial, by rw [show expectedUtilityDTD inst AdaptivePolicy.stop = 0 from rfl]; exact hπ'⟩
le_ciSup- In a conditionally complete lattice, any element of a function's range is less than or equal to the supremum of the function, provided the range is bounded above.
lt_or_ge- In any linearly ordered type, for any two elements $a$ and $b$, either $a < b$ or $b \le a$.
mul_lt_mul_of_pos_right- Multiplying a strict inequality $b < c$ on the right by a strictly positive element $a > 0$ preserves the strict inequality: $b \cdot a < c \cdot a$.
exists_lt_of_lt_ciSup- If a value $b$ is strictly less than the supremum of a nonempty family $f$, there exists an index $i$ such that $b < f(i)$.
le_of_lt- A strict inequality $a < b$ implies the non-strict inequality $a \le b$.
le_antisymm- If $a \le b$ and $b \le a$, then $a = b$.
mul_zero- Multiplying any element by zero yields zero: $a \cdot 0 = 0$.
Real.iSup_of_not_bddAbove- In Lean's real numbers, if the range of a function is not bounded above, its supremum defaults to $0$.
ciSup_pos- The supremum of a function indexed by a proposition that is true evaluates to the value of the function at that truth witness.
le_of_eq- An equality $a = b$ implies the inequality $a \le b$.
Real.iSup_of_isEmpty- The supremum of a real-valued function indexed by an empty type evaluates to $0$.
- The theorem is formulated as a self-benchmark: `optDTD inst` is defined directly as the supremum of `expectedUtilityDTD inst π` over all valid adaptive policies `π`. Because the benchmark is the supremum of the very class of policies being chosen from, any competitive ratio $c < 1$ is achievable purely by the definition of the supremum; no algorithmic or probabilistic analysis of Pandora's box is required.
- In Lean's conditionally complete lattice on $\mathbb{R}$, the supremum of a set not bounded above defaults to $0$ (`Real.iSup_of_not_bddAbove`). The helper lemma handles this formal artifact by showing that in this case $c \cdot 0 \le 0$ is trivially satisfied by any non-negative element.
- The definition of `optDTD` uses a nested supremum over all policies $\pi$ and proofs of `IsValidPolicy inst π`. For an invalid policy, the inner index type is empty, which Lean evaluates to $0$ (`Real.iSup_of_isEmpty`). This requires an explicit case split in the formal proof even though on paper one would index the supremum directly over valid policies.
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 Problem OP-182: whether an adaptive policy with deferred-to-deadline commitment can achieve ratio > 1/2 against optDTD. -/theorem op182_deferred_to_deadline_beyond_half_self_benchmark : ∃ c > (1 / 2 : ℝ), ∀ inst : PandoraDeadlineInstance, ∃ π : AdaptivePolicy inst.n, IsValidPolicy inst π ∧ c * optDTD inst ≤ expectedUtilityDTD inst π := by -- The self-benchmark case is immediate from the definition of `optDTD` as a supremum: -- the stop-now policy is valid and yields utility `0`, so `optDTD inst ≥ 0`, and any -- constant `c < 1` is dominated by the supremum itself. have key : ∀ (ι : Type), Nonempty ι → ∀ f : ι → ℝ, (∃ i, 0 ≤ f i) → ∃ i, (3/4:ℝ) * (⨆ i, f i) ≤ f i := by intro ι hι f h0 haveI := hι by_cases hb : BddAbove (Set.range f) · have hle : (0:ℝ) ≤ ⨆ i, f i := by obtain ⟨i, hi⟩ := h0 exact hi.trans (le_ciSup hb i) rcases lt_or_ge 0 (⨆ i, f i) with h | h · have hlt : (3/4:ℝ) * (⨆ i, f i) < ⨆ i, f i := by have := mul_lt_mul_of_pos_right (by norm_num : (3/4:ℝ) < 1) h simpa using this obtain ⟨i, hi⟩ := exists_lt_of_lt_ciSup (f := f) hlt exact ⟨i, le_of_lt hi⟩ · obtain ⟨i, hi⟩ := h0 exact ⟨i, by rw [le_antisymm h hle, mul_zero]; exact hi⟩ · rw [Real.iSup_of_not_bddAbove hb] obtain ⟨i, hi⟩ := h0 exact ⟨i, by rw [mul_zero]; exact hi⟩ refine ⟨3/4, by norm_num, fun inst => ?_⟩ -- the stop-now policy is valid and gives utility `0`, hence the supremum is nonnegative have h0 : ∃ π : AdaptivePolicy inst.n, 0 ≤ ⨆ (_ : IsValidPolicy inst π), expectedUtilityDTD inst π := by refine ⟨AdaptivePolicy.stop, ?_⟩ rw [ciSup_pos (show IsValidPolicy inst AdaptivePolicy.stop from trivial)] exact le_of_eq (show expectedUtilityDTD inst AdaptivePolicy.stop = 0 from rfl).symm obtain ⟨π, hπ⟩ := key (AdaptivePolicy inst.n) ⟨AdaptivePolicy.stop⟩ (fun π => ⨆ (_ : IsValidPolicy inst π), expectedUtilityDTD inst π) h0 have hπ' : (3/4:ℝ) * optDTD inst ≤ ⨆ (_ : IsValidPolicy inst π), expectedUtilityDTD inst π := hπ by_cases hv : IsValidPolicy inst π · exact ⟨π, hv, by rwa [ciSup_pos hv] at hπ'⟩ · -- for an invalid policy the supremum over `IsValidPolicy inst π` is empty, hence `0` have hempty : (⨆ (_ : IsValidPolicy inst π), expectedUtilityDTD inst π) = 0 := by haveI : IsEmpty (IsValidPolicy inst π) := ⟨fun h => hv h⟩ exact Real.iSup_of_isEmpty _ rw [hempty] at hπ' exact ⟨AdaptivePolicy.stop, trivial, by rw [show expectedUtilityDTD inst AdaptivePolicy.stop = 0 from rfl]; exact hπ'⟩