pandora_exists_reservation
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 nfor 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.nunder 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
- op184_partially_adaptive_half_approximationFor every Pandora's problem instance with deadlines
inst : PandoraDeadlineInstance, there exists a valid partially adaptive policy…
- op184_partially_adaptive_half_approximationFor every Pandora's problem instance with deadlines
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.
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).
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)
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.
uses
neg_nonpos.mpr,le_trans,le_max_lefthave hab : a ≤ b := by dsimp [a, b] have : -c ≤ 0 := neg_nonpos.mpr hc exact le_trans this (le_max_left 0 _)
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].
uses
Continuous.continuousOnhave hcont : ContinuousOn f (Set.Icc a b) := by apply Continuous.continuousOn continuity
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).
uses
le_trans,le_max_left,mul_le_mul_of_nonneg_left,Finset.sum_le_sum,Finset.sum_mul,one_mulhave 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
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.
uses
Finset.single_le_sum,le_max_right,le_trans,sub_nonpos.mpr,max_eq_right,Finset.sum_eq_zero,mul_zerohave 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
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.
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⟩
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`).
uses
Classical.skolem.mpdsimp [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)).
- The continuity of the expected surplus function f on line 17 is established by Mathlib's automated `continuity` tactic without an explicit manual epsilon-delta or algebraic breakdown.
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 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