expectedUtilityDTD
The expected net utility of an adaptive policy π : AdaptivePolicy inst.n under deferred-to-deadline commitment on a Pandora's problem instance with deadlines inst : PandoraDeadlineInstance. Evaluated recursively starting with an empty history: upon opening a box b, the box cost inst.cost b is subtracted and the expectation over the realized values v in the support of (inst.dist b) of continuing with (b, v) :: history is taken; upon stopping at round t = history.length, the policy receives the maximum realized value among all opened boxes whose deadline satisfies t ≤ inst.deadline b (or 0 if none).
Statement
noncomputable def expectedUtilityDTD (inst : PandoraDeadlineInstance) (π : AdaptivePolicy inst.n) : ℝ
- Defined in
- arXiv:2610.13775 Sec. 2.1
- Verified
- 18 Oct 2026
- Axioms
- none listed
- Built on 3
- 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…
- DiscreteDistA discrete probability distribution with finite support on non-negative real values, defined by a finite support set, non-negative…
- Used by 8
- two_box_dtd_le_oneUnder deferred-to-deadline commitment, every valid policy on the two-box instance gets expected utility at most 1.
- expected_utility_dtd_le_dusFor every Pandora's problem instance with deadlines
inst : PandoraDeadlineInstanceand every adaptive policy… - 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… - two_box_dtd_after_box_zeroWith the history
[(0, 1)], any valid policy has deferred-to-deadline expected utility at most 1. - 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… - 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π…
Read back from the Lean
expectedUtilityDTD inst π defines the expected utility (as a real number) of an adaptive policy π : AdaptivePolicy inst.n on an instance inst : PandoraDeadlineInstance of Pandora's box problem with deadlines.
It is computed by an auxiliary function aux (history : List (Fin inst.n × ℝ)) (π : AdaptivePolicy inst.n) : ℝ initialized with an empty history []:
1. When π = AdaptivePolicy.stop:
Let t = history.length be the total number of boxes opened. The return value is the result of folding over history from an initial value of 0: for each opened box-value pair (b, v), if t ≤ inst.deadline b, it updates the accumulator to max acc v, and otherwise leaves it unchanged. That is, it returns the maximum value among all opened boxes whose deadline is at least t, or 0 if no such box exists.
2. When π = AdaptivePolicy.openBox b cont:
It opens box b : Fin inst.n, paying the cost inst.cost b. Its value v is drawn from the finite support (inst.dist b).support with probability (inst.dist b).prob v. It takes the expectation over v ∈ (inst.dist b).support of aux ((b, v) :: history) (cont v) and subtracts inst.cost b.
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
/-- Expected net utility of an adaptive policy under deferred-to-deadline commitment in Pandora's problem with deadlines. -/ noncomputable def expectedUtilityDTD (inst : PandoraDeadlineInstance) (π : AdaptivePolicy inst.n) : ℝ := aux [] π where aux (history : List (Fin inst.n × ℝ)) : AdaptivePolicy inst.n → ℝ | .stop => let t := history.length history.foldl (fun acc bv => if t ≤ inst.deadline bv.1 then max acc bv.2 else acc) 0 | .openBox b cont => (∑ v ∈ (inst.dist b).support, (inst.dist b).prob v * aux ((b, v) :: history) (cont v)) - inst.cost b