two_box_deadline_inst
abbrev
Two boxes with zero cost: box 0 has deadline 1 and deterministic value 1; box 1 has deadline 2, value M with probability 1/M and 0 otherwise.
Statement
noncomputable abbrev two_box_deadline_inst (M : ℕ) (hM : 1 < M) : PandoraDeadlineInstance
- Source
- step towards two_box_counterexample_family
- Verified
- 20 Oct 2026
- Axioms
- none listed
- Built on 4
- two_box_fair_value_distThe degenerate discrete distribution taking the value
1with probability1. - two_box_risky_value_distThe distribution taking the value
Mwith probability1/Mand the value0with probability1 - 1/M. - 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…
- two_box_fair_value_distThe degenerate discrete distribution taking the value
- Used by 6
- two_box_pi01_validThe policy "open box 0, then box 1, then stop" is valid for the two-box instance.
- 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. - two_box_pi01_dusThe DUS utility of the policy opening box 0 then box 1 is
2 - 1/M. - two_box_dtd_after_box_zeroWith the history
[(0, 1)], any valid policy has deferred-to-deadline expected utility at most 1. - 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π…
Lean source view module on GitHub
/-- Two boxes, both free to open: box 0 has deadline 1 and deterministic value 1, box 1 has deadline 2 and value `M` with probability `1/M` (0 otherwise). -/ noncomputable abbrev two_box_deadline_inst (M : ℕ) (hM : 1 < M) : PandoraDeadlineInstance where n := 2 cost := fun _ => 0 deadline := fun i => if i = 0 then 1 else 2 dist := fun i => if i = 0 then two_box_fair_value_dist else two_box_risky_value_dist M hM cost_nonneg := by intro i; norm_num deadline_pos := by intro i; fin_cases i <;> simp