pandora_threshold_policy
def
The threshold policy on a list of boxes: open them in the given order and stop as soon as an opened value exceeds t (stop after the last box otherwise).
Statement
noncomputable def pandora_threshold_policy {n : ℕ} (order : List (Fin n)) (t : ℝ) : AdaptivePolicy n
- Defined in
- arXiv:2610.13775 Section 3, Section 3.2, policy T^+(S,t)
- 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 6
- pandora_threshold_policy_nilSanity: the threshold policy on the empty list stops at once.
- pandora_threshold_policy_consSanity: the threshold policy on b :: rest opens b, stops if its value exceeds t, and otherwise continues with the threshold policy on rest.
- pandora_deadline_feasible_emptySanity: the empty set of boxes is deadline-feasible.
- 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_threshold_policy_validA threshold policy on a duplicate-free list whose j-th box has deadline at least j is a valid policy and is partially adaptive.
Lean source view module on GitHub
/-- The threshold policy: open the boxes of `order` in turn and stop at the first value above `t`. -/ noncomputable def pandora_threshold_policy {n : ℕ} (order : List (Fin n)) (t : ℝ) : AdaptivePolicy n := order.foldr (fun b acc => .openBox b (fun v => if t < v then .stop else acc)) .stop