AFTD Auto-Formalizing Theoretical Domains

op182_deferred_to_deadline_beyond_half_self_benchmark

theoremverifiedformalization

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 inst under deferred-to-deadline commitment for a Pandora's problem instance with deadlines…
  • expectedUtilityDTDThe expected net utility of an adaptive policy π : AdaptivePolicy inst.n under 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,…

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.

  1. 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`.

    lines 9–27

    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_bddAbove

      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⟩
  2. 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`.

    lines 28–29

      refine ⟨3/4, by norm_num, fun inst => ?_⟩
      -- the stop-now policy is valid and gives utility `0`, hence the supremum is nonnegative
  3. 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`).

    lines 30–34

    uses ciSup_pos, le_of_eq

      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
  4. 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$.

    lines 35–38

      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π
  5. 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})$.

    lines 39–40

    uses ciSup_pos

      by_cases hv : IsValidPolicy inst π
      · exact ⟨π, hv, by rwa [ciSup_pos hv] at hπ'⟩
  6. 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.

    lines 41–47

    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$.

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

/-- 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π'⟩
See it in the graphDiscuss this resultChallenge it