IsValidPolicy
A policy is valid for a Pandora's problem instance with deadlines if it respects opening deadlines and never opens any box more than once.
Statement
def IsValidPolicy (inst : PandoraDeadlineInstance) (π : AdaptivePolicy inst.n) : Prop
- Defined in
- arXiv:2610.13775, Sec. 2.1
- Verified
- 18 Oct 2026
- Axioms
- none listed
- Built on 3
- IsValidPolicyAuxA policy execution is valid if it never re-opens an already opened box, respects the deadline of each opened box, and remains valid on all…
- PandoraDeadlineInstanceAn instance of Pandora's problem with deadlines consisting of n boxes, each with a non-negative opening cost, a positive integer deadline,…
- 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…
- Used by 23
- two_box_pi01_validThe policy "open box 0, then box 1, then stop" is valid for the two-box instance.
- optDUSThe optimal expected net utility
optDUS instunder deferred-until-stopping commitment for a Pandora's problem instance with deadlines… - expected_utility_dus_le_opt_dusFor any Pandora's problem instance with deadlines
instand any valid policyπ,expectedUtilityDUS inst π ≤ optDUS inst. - 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…
- pandora_exists_deadline_orderLemma 2: a deadline-feasible set can be listed without repetition so that the j-th box (j from 1) has deadline at least j.
- two_box_dtd_le_oneUnder deferred-to-deadline commitment, every valid policy on the two-box instance gets expected utility at most 1.
- not_single_box_valid_is_partially_adaptiveThe statement
single_box_valid_is_partially_adaptiveis false: The statement is false.IsValidPolicyonly constrains the continuation… - pandora_deadline_feasibleA set S of boxes is deadline-feasible if for every j at most j of its boxes have deadline at most j (equivalently, by Lemma 2, its boxes…
- opt_dtd_le_opt_dusFor every Pandora's problem instance with deadlines
inst : PandoraDeadlineInstance, the optimal expected utility under… - optDTDThe optimal expected net utility
optDTD instunder deferred-to-deadline commitment for a Pandora's problem instance with deadlines… - is_valid_policy_stopFor every Pandora's problem instance with deadlines
inst : PandoraDeadlineInstance, the policyAdaptivePolicy.stopsatisfies… - 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_capped_surplusThe reservation-capped threshold surplus of box i at threshold t: w_i(t) = E[(min(v_i, r_i) - t)^+].
- op182_deferred_to_deadline_beyond_half_against_stoppingRefutation of Open Problem OP-182 against the deferred-until-stopping benchmark: there does not exist any constant
c > 1/2such that for… - op182_deferred_to_deadline_beyond_half_self_benchmarkOpen Problem OP-182 against the deferred-to-deadline benchmark: there exists a constant
c > 1/2such that for every Pandora's problem… - dus_approx_of_pos_optIf a constant factor approximation ratio c is achieved by partially adaptive policies on all instances with optDUS > 0, then it is…
- two_box_counterexample_familyFor any integer
M > 1, there exists a 2-box Pandora deadline instance such that2 - 1 / M ≤ optDUS instand every valid policyπ… - pandora_threshold_policyThe 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…
- 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.
- pandora_exists_balancing_thresholdThere is a threshold t >= 0 at which the maximum total capped surplus over deadline-feasible sets equals t, attained by some feasible set.
- 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.
Read back from the Lean
For a given instance inst of the Pandora's box problem with deadlines (PandoraDeadlineInstance) and an adaptive policy π : AdaptivePolicy inst.n, IsValidPolicy inst π asserts that π is valid starting from an empty list of opened boxes [].
Validity with respect to a list opened : List (Fin inst.n) of previously opened boxes is defined recursively on the structure of π:
1. If π = .stop, the condition is trivially True.
2. If π = .openBox b cont (where b : Fin inst.n is the box chosen to be opened, and cont : ℝ → AdaptivePolicy inst.n is the continuation policy given the realized value):
- b ∉ opened (box b has not already been opened);
- opened.length + 1 ≤ inst.deadline b (the step at which box b is opened does not exceed its deadline); and
- for every value v in the finite support of the distribution of box b (v ∈ (inst.dist b).support), the continuation policy cont v is valid with b added to the list of opened boxes (b :: opened).
Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.
Lean source view module on GitHub
/-- A policy is valid for an instance if it respects deadlines and opens no box twice. -/ def IsValidPolicy (inst : PandoraDeadlineInstance) (π : AdaptivePolicy inst.n) : Prop := IsValidPolicyAux inst rfl [] π