pandora_is_reservation
def
r 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 c_i.
Statement
def pandora_is_reservation (inst : PandoraDeadlineInstance) (r : Fin inst.n → ℝ) : Prop
- Defined in
- arXiv:2610.13775 Section 3, Section 3.1 (reservation values of Weitzman's rule)
- Verified
- 26 Oct 2026
- Axioms
- none listed
- Built on 6
- 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…
- Used by 4
- op184_partially_adaptive_half_approximationFor every Pandora's problem instance with deadlines
inst : PandoraDeadlineInstance, there exists a valid partially adaptive policy… - pandora_threshold_policy_lower_boundLemma 3: for reservation values r, t >= 0 and a duplicate-free list of boxes each with positive capped surplus at t, the threshold policy…
- pandora_adaptive_surplus_upper_boundLemma 1: for reservation values r and any threshold t >= 0, every valid adaptive policy has expected DUS utility at most t plus the total…
- pandora_exists_reservationEvery Pandora instance with deadlines has reservation values: for every box i there is r_i with E[(v_i - r_i)^+] = c_i.
- op184_partially_adaptive_half_approximationFor every Pandora's problem instance with deadlines
Lean source view module on GitHub
/-- `r` is a vector of reservation values: `E[(v_i - r_i)^+] = c_i` for every box. -/ def pandora_is_reservation (inst : PandoraDeadlineInstance) (r : Fin inst.n → ℝ) : Prop := ∀ i, ∑ v ∈ (inst.dist i).support, (inst.dist i).prob v * max (v - r i) 0 = inst.cost i