AFTD Auto-Formalizing Theoretical Domains

IsPartiallyAdaptive

def

A search policy π : AdaptivePolicy n for Pandora's problem is partially adaptive if there exists a predetermined ordered list of boxes order such that along every execution branch, the sequence of boxes opened is a prefix of order.

Statement

def IsPartiallyAdaptive {n : ℕ} (π : AdaptivePolicy n) : Prop
Defined in
arXiv:2610.13775, Sec. 2.1
Verified
25 Oct 2026
Axioms
none listed
Built on 1
  • 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 14
  • 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.
  • not_single_box_valid_is_partially_adaptiveThe statement single_box_valid_is_partially_adaptive is false: The statement is false. IsValidPolicy only 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…
  • is_partially_adaptive_stopFor any natural number n, the policy AdaptivePolicy.stop : AdaptivePolicy n is partially adaptive (…
  • 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)^+].
  • 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…
  • 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

Given a natural number n and an adaptive policy π : AdaptivePolicy n, IsPartiallyAdaptive π asserts that there exists a list order : List (Fin n) of box indices such that aux order π holds, where aux is defined recursively as follows: - For any list of box indices, aux _ AdaptivePolicy.stop is True. - For the empty list [], aux [] (AdaptivePolicy.openBox _ _) is False. - For a non-empty list b :: rest and an open-box node AdaptivePolicy.openBox b' cont, aux (b :: rest) (AdaptivePolicy.openBox b' cont) holds if and only if b' = b and for every real number v : ℝ, aux rest (cont v) holds. In other words, the policy opens boxes according to a fixed predetermined sequence given by order (or a prefix thereof), where at step k along any execution path, if the policy opens a box, it must open the k-th box in order, although the decision to stop may depend adaptively on the observed values v.

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 partially adaptive if its opened boxes along every branch form a prefix of a fixed box order. -/
def IsPartiallyAdaptive {n : ℕ} (π : AdaptivePolicy n) : Prop := ∃ order : List (Fin n), aux order π
where
  aux : List (Fin n) → AdaptivePolicy n → Prop
    | _, .stop => True
    | [], .openBox _ _ => False
    | b :: rest, .openBox b' cont => b' = b ∧ ∀ v, aux rest (cont v)
See it in the graphDiscuss this resultChallenge it