AFTD Auto-Formalizing Theoretical Domains

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 1 with probability 1.
  • two_box_risky_value_distThe distribution taking the value M with probability 1/M and the value 0 with probability 1 - 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…
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 that 2 - 1 / M ≤ optDUS inst and 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
See it in the graphDiscuss this resultChallenge it