AFTD Auto-Formalizing Theoretical Domains

pandora_exists_reservation

theoremverified

Every Pandora instance with deadlines has reservation values: for every box i there is r_i with E[(v_i - r_i)^+] = c_i.

Statement

theorem pandora_exists_reservation (inst : PandoraDeadlineInstance) :
    ∃ r : Fin inst.n → ℝ, pandora_is_reservation inst r
Source
Helper for op184_partially_adaptive_half_approximation: arXiv:2610.13775 Section 3, Lemma 1 / Section 3.1 (existence of reservation values)
Verified
26 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 7
  • PandoraDeadlineInstanceAn instance of Pandora's problem with deadlines consisting of n boxes, each with a non-negative opening cost, a positive integer deadline,…
  • DiscreteDistA discrete probability distribution with finite support on non-negative real values, defined by a finite support set, non-negative…
  • 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…
  • expectedUtilityDUSThe expected net utility of an adaptive policy π : AdaptivePolicy inst.n under deferred-until-stopping commitment on a Pandora's problem…
  • pandora_is_reservationr is a vector of reservation values: for every box i, the expected excess E[(v_i - r_i)^+] of its value over r_i equals its opening cost…
Used by 1

The proof, explained

To show that every box in a Pandora deadline instance admits a reservation price, the proof establishes existence for each box individually and then uses Skolemization (the Axiom of Choice) to combine them into a reservation vector. For a fixed box with non-negative inspection cost c, the expected payoff function f(r) = E[(v - r)^+] is continuous. At a = -c, the non-negativity of values ensures f(a) ≥ c, while at b = max(0, ∑ v), every payoff is zero so f(b) = 0 ≤ c. The Intermediate Value Theorem then guarantees the existence of a reservation value r_i ∈ [a, b] with f(r_i) = c.

  1. For each box i, it suffices to find a reservation price r_i satisfying the reservation equation on an interval [a, b].

    Fix an arbitrary box i. We set up its value distribution, its non-negative inspection cost c = cost(i) ≥ 0, and define the expected gain function f(r) = ∑_v p(v) max(v - r, 0). To prepare to apply the Intermediate Value Theorem, we define the search interval endpoints a = -c and b = max(0, ∑_v v).

    lines 3–10

      have h : ∀ i : Fin inst.n, ∃ r_i : ℝ, ∑ v ∈ (inst.dist i).support, (inst.dist i).prob v * max (v - r_i) 0 = inst.cost i := by
        intro i
        let dist := inst.dist i
        let c := inst.cost i
        have hc : 0 ≤ c := inst.cost_nonneg i
        let f := fun r : ℝ => ∑ v ∈ dist.support, dist.prob v * max (v - r) 0
        let a := -c
        let b := max 0 (∑ v ∈ dist.support, v)
  2. The search interval is valid: a ≤ b.

    Since cost c is non-negative, its negation satisfies a = -c ≤ 0 by `neg_nonpos.mpr`. Furthermore, 0 ≤ max(0, ∑ v) = b by `le_max_left`. By transitivity (`le_trans`), a ≤ b.

    lines 11–14

    uses neg_nonpos.mpr, le_trans, le_max_left

        have hab : a ≤ b := by
          dsimp [a, b]
          have : -c ≤ 0 := neg_nonpos.mpr hc
          exact le_trans this (le_max_left 0 _)
  3. The function f is continuous on the closed interval [a, b]. automation

    The function f is a finite sum of continuous functions r ↦ max(v - r, 0), so it is continuous everywhere on ℝ as verified by the `continuity` tactic. By `Continuous.continuousOn`, it is continuous on [a, b].

    lines 15–17

    uses Continuous.continuousOn

        have hcont : ContinuousOn f (Set.Icc a b) := by
          apply Continuous.continuousOn
          continuity
  4. At the lower bound a, the expected gain is at least the cost: c ≤ f(a).

    At a = -c, every value v in the support is non-negative, so v - (-c) = v + c ≥ c, which implies c ≤ max(v - (-c), 0) using `le_max_left` and `le_trans`. Multiplying by probabilities (`mul_le_mul_of_nonneg_left`) and summing over the support (`Finset.sum_le_sum`) gives ∑_v p(v) * c ≤ f(a). Since the probabilities sum to 1, factoring out c (`Finset.sum_mul`, `one_mul`) shows this sum equals c, proving c ≤ f(a).

    lines 18–32

    uses le_trans, le_max_left, mul_le_mul_of_nonneg_left, Finset.sum_le_sum, Finset.sum_mul, one_mul

        have hfa : c ≤ f a := by
          dsimp [f, a]
          have h1 : ∀ v ∈ dist.support, c ≤ max (v - (-c)) 0 := by
            intro v hv
            have hv_nonneg : 0 ≤ v := dist.val_nonneg v hv
            have : c ≤ v - (-c) := by linarith
            exact le_trans this (le_max_left (v - (-c)) 0)
          have h2 : ∀ v ∈ dist.support, dist.prob v * c ≤ dist.prob v * max (v - (-c)) 0 := by
            intro v hv
            exact mul_le_mul_of_nonneg_left (h1 v hv) (dist.prob_nonneg v hv)
          have h3 : ∑ v ∈ dist.support, dist.prob v * c ≤ ∑ v ∈ dist.support, dist.prob v * max (v - (-c)) 0 :=
            Finset.sum_le_sum h2
          have h4 : ∑ v ∈ dist.support, dist.prob v * c = c := by
            rw [← Finset.sum_mul, dist.sum_prob_one, one_mul]
          rwa [h4] at h3
  5. At the upper bound b, the expected gain is at most the cost: f(b) ≤ c.

    For any value v in the support, v is bounded by the sum of all values (`Finset.single_le_sum`), which is at most b = max(0, ∑ w) (`le_max_right`). By transitivity (`le_trans`), v ≤ b, so v - b ≤ 0 (`sub_nonpos.mpr`) and max(v - b, 0) = 0 (`max_eq_right`). Each term in the sum defining f(b) is therefore zero (`mul_zero`), giving f(b) = 0 by `Finset.sum_eq_zero`. Since c ≥ 0, f(b) = 0 ≤ c.

    lines 33–47

    uses Finset.single_le_sum, le_max_right, le_trans, sub_nonpos.mpr, max_eq_right, Finset.sum_eq_zero, mul_zero

        have hfb : f b ≤ c := by
          dsimp [f, b]
          have hb : ∀ v ∈ dist.support, max (v - max 0 (∑ v ∈ dist.support, v)) 0 = 0 := by
            intro v hv
            have hle1 : v ≤ ∑ w ∈ dist.support, w := Finset.single_le_sum (fun w hw => dist.val_nonneg w hw) hv
            have hle2 : ∑ w ∈ dist.support, w ≤ max 0 (∑ v ∈ dist.support, v) := le_max_right 0 _
            have hle : v ≤ b := le_trans hle1 hle2
            have : v - b ≤ 0 := sub_nonpos.mpr hle
            exact max_eq_right this
          have hsum : ∑ v ∈ dist.support, dist.prob v * max (v - max 0 (∑ v ∈ dist.support, v)) 0 = 0 := by
            apply Finset.sum_eq_zero
            intro v hv
            rw [hb v hv, mul_zero]
          rw [hsum]
          exact hc
  6. There exists a reservation value r_i for box i such that f(r_i) = c.

    Since f(b) ≤ c ≤ f(a), the cost c lies in the interval [f(b), f(a)]. By the Intermediate Value Theorem (`intermediate_value_Icc'`) applied to the continuous function f on [a, b], there is an r_i ∈ [a, b] such that f(r_i) = c.

    lines 48–51

    uses intermediate_value_Icc'

        have hc_mem : c ∈ Set.Icc (f b) (f a) := ⟨hfb, hfa⟩
        have hivt := intermediate_value_Icc' hab hcont hc_mem
        rcases hivt with ⟨r, _, hr⟩
        exact ⟨r, hr⟩
  7. There exists a vector of reservation prices r satisfying the condition for all boxes.

    Unfolding `pandora_is_reservation`, which requires the reservation equality to hold for all boxes, the pointwise existence statement ∀ i, ∃ r_i is converted into the existence of a global vector r : Fin n → ℝ by Skolemization / the axiom of choice (`Classical.skolem.mp`).

    lines 52–53

    uses Classical.skolem.mp

      dsimp [pandora_is_reservation]
      exact Classical.skolem.mp h
neg_nonpos.mpr
If a real number x is non-negative (0 ≤ x), then its negation is non-positive (-x ≤ 0).
le_trans
Transitivity of inequality: if a ≤ b and b ≤ c, then a ≤ c.
le_max_left
For any elements a and b in a linear order, a ≤ max a b.
Continuous.continuousOn
A function continuous on its whole domain is continuous on any subset of that domain.
mul_le_mul_of_nonneg_left
Multiplying an inequality b ≤ c by a non-negative element a ≥ 0 preserves the inequality: a * b ≤ a * c.
Finset.sum_le_sum
If f(i) ≤ g(i) for all elements i in a finite set s, then the sum of f over s is bounded by the sum of g over s.
Finset.sum_mul
Right-distributivity of multiplication over a finite sum: (∑ i ∈ s, f i) * a = ∑ i ∈ s, f i * a.
one_mul
Multiplying an element by 1 leaves it unchanged: 1 * a = a.
Finset.single_le_sum
A single non-negative term f(a) from a finite set s is bounded by the sum of all terms over s.
le_max_right
For any elements a and b in a linear order, b ≤ max a b.
sub_nonpos.mpr
If x ≤ y, then x - y ≤ 0.
max_eq_right
If a ≤ b, then max a b = b.
Finset.sum_eq_zero
A finite sum of terms is 0 if every term in the sum is 0.
mul_zero
Multiplying any element by zero yields zero: a * 0 = 0.
intermediate_value_Icc'
The Intermediate Value Theorem: if a function f is continuous on [a, b] with a ≤ b, then f achieves every value in the interval [f(b), f(a)].
Classical.skolem.mp
The axiom of choice (Skolemization): a pointwise existence statement ∀ x, ∃ y, P(x, y) implies the existence of a choice function f such that ∀ x, P(x, f(x)).

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 pandora_exists_reservation (inst : PandoraDeadlineInstance) :    ∃ r : Fin inst.n → ℝ, pandora_is_reservation inst r := by  have h : ∀ i : Fin inst.n, ∃ r_i : ℝ, ∑ v ∈ (inst.dist i).support, (inst.dist i).prob v * max (v - r_i) 0 = inst.cost i := by    intro i    let dist := inst.dist i    let c := inst.cost i    have hc : 0 ≤ c := inst.cost_nonneg i    let f := fun r : ℝ => ∑ v ∈ dist.support, dist.prob v * max (v - r) 0    let a := -c    let b := max 0 (∑ v ∈ dist.support, v)    have hab : a ≤ b := by      dsimp [a, b]      have : -c ≤ 0 := neg_nonpos.mpr hc      exact le_trans this (le_max_left 0 _)    have hcont : ContinuousOn f (Set.Icc a b) := by      apply Continuous.continuousOn      continuity    have hfa : c ≤ f a := by      dsimp [f, a]      have h1 : ∀ v ∈ dist.support, c ≤ max (v - (-c)) 0 := by        intro v hv        have hv_nonneg : 0 ≤ v := dist.val_nonneg v hv        have : c ≤ v - (-c) := by linarith        exact le_trans this (le_max_left (v - (-c)) 0)      have h2 : ∀ v ∈ dist.support, dist.prob v * c ≤ dist.prob v * max (v - (-c)) 0 := by        intro v hv        exact mul_le_mul_of_nonneg_left (h1 v hv) (dist.prob_nonneg v hv)      have h3 : ∑ v ∈ dist.support, dist.prob v * c ≤ ∑ v ∈ dist.support, dist.prob v * max (v - (-c)) 0 :=        Finset.sum_le_sum h2      have h4 : ∑ v ∈ dist.support, dist.prob v * c = c := by        rw [← Finset.sum_mul, dist.sum_prob_one, one_mul]      rwa [h4] at h3    have hfb : f b ≤ c := by      dsimp [f, b]      have hb : ∀ v ∈ dist.support, max (v - max 0 (∑ v ∈ dist.support, v)) 0 = 0 := by        intro v hv        have hle1 : v ≤ ∑ w ∈ dist.support, w := Finset.single_le_sum (fun w hw => dist.val_nonneg w hw) hv        have hle2 : ∑ w ∈ dist.support, w ≤ max 0 (∑ v ∈ dist.support, v) := le_max_right 0 _        have hle : v ≤ b := le_trans hle1 hle2        have : v - b ≤ 0 := sub_nonpos.mpr hle        exact max_eq_right this      have hsum : ∑ v ∈ dist.support, dist.prob v * max (v - max 0 (∑ v ∈ dist.support, v)) 0 = 0 := by        apply Finset.sum_eq_zero        intro v hv        rw [hb v hv, mul_zero]      rw [hsum]      exact hc    have hc_mem : c ∈ Set.Icc (f b) (f a) := ⟨hfb, hfa⟩    have hivt := intermediate_value_Icc' hab hcont hc_mem    rcases hivt with ⟨r, _, hr⟩    exact ⟨r, hr⟩  dsimp [pandora_is_reservation]  exact Classical.skolem.mp h
See it in the graphDiscuss this resultChallenge it