AFTD Auto-Formalizing Theoretical Domains

AdaptivePolicy

inductive

A fully adaptive search policy for Pandora's problem with n boxes, represented as a decision tree that at each step either stops or opens a box and branches on its revealed value.

Statement

inductive AdaptivePolicy (n : ℕ) where
  | stop : AdaptivePolicy n
  | openBox (b : Fin n) (cont : ℝ → AdaptivePolicy n) : AdaptivePolicy n
Defined in
arXiv:2610.13775, Sec. 2.1
Verified
18 Oct 2026
Axioms
none listed
Used by 37
  • 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 inst under deferred-until-stopping commitment for a Pandora's problem instance with deadlines…
  • 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.
  • opt_dus_nonnegFor any Pandora deadline instance inst, 0 ≤ optDUS inst.
  • expected_utility_dus_le_opt_dusFor any Pandora's problem instance with deadlines inst and 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…
  • 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.
  • 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.
  • two_box_valid_stop_of_mem_oneIf a valid policy execution has box 1 in its already-opened list and at least one round has elapsed, then the remaining policy is stop.
  • expected_utility_dus_stopFor any Pandora deadline instance inst, the expected net utility expectedUtilityDUS inst AdaptivePolicy.stop is zero.
  • 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…
  • two_box_pi01_dusThe DUS utility of the policy opening box 0 then box 1 is 2 - 1/M.
  • expected_utility_dtd_le_dusFor every Pandora's problem instance with deadlines inst : PandoraDeadlineInstance and every adaptive policy…
  • expectedUtilityDTDThe expected net utility of an adaptive policy π : AdaptivePolicy inst.n under deferred-to-deadline commitment on a Pandora's problem…
  • 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 inst under deferred-to-deadline commitment for a Pandora's problem instance with deadlines…
  • is_partially_adaptive_stopFor any natural number n, the policy AdaptivePolicy.stop : AdaptivePolicy n is partially adaptive (…
  • two_box_dtd_after_box_zeroWith the history [(0, 1)], any valid policy has deferred-to-deadline expected utility at most 1.
  • is_valid_policy_stopFor every Pandora's problem instance with deadlines inst : PandoraDeadlineInstance, the policy AdaptivePolicy.stop satisfies…
  • 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…
  • 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…
  • 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/2 such that for…
  • expectedUtilityDUSThe expected net utility of an adaptive policy π : AdaptivePolicy inst.n under deferred-until-stopping commitment on a Pandora's problem…
  • op182_deferred_to_deadline_beyond_half_self_benchmarkOpen Problem OP-182 against the deferred-to-deadline benchmark: there exists a constant c > 1/2 such 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 that 2 - 1 / M ≤ optDUS inst and 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.
  • IsPartiallyAdaptiveA search policy π : AdaptivePolicy n for Pandora's problem is partially adaptive if there exists a predetermined ordered list of boxes…
  • 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

An inductive type family AdaptivePolicy parameterized by a natural number n : ℕ, defined with two constructors: 1. stop: produces a term of AdaptivePolicy n. 2. openBox: given an index b : Fin n and a continuation function cont : ℝ → AdaptivePolicy n (mapping each real number to a subsequent policy), produces a term of AdaptivePolicy n.

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 fully adaptive search policy for Pandora's problem as a decision tree. -/
inductive AdaptivePolicy (n : ℕ) where
  | stop : AdaptivePolicy n
  | openBox (b : Fin n) (cont : ℝ → AdaptivePolicy n) : AdaptivePolicy n
See it in the graphDiscuss this resultChallenge it