two_box_dtd_le_one
Under deferred-to-deadline commitment, every valid policy on the two-box instance gets expected utility at most 1.
Statement
theorem two_box_dtd_le_one (M : ℕ) (hM : 1 < M) (π : AdaptivePolicy 2)
(hπ : IsValidPolicy (two_box_deadline_inst M hM) π) :
expectedUtilityDTD (two_box_deadline_inst M hM) π ≤ 1- Source
- step towards two_box_counterexample_family
- Verified
- 24 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 12
- two_box_deadline_instTwo boxes with zero cost: box 0 has deadline 1 and deterministic value 1; box 1 has deadline 2, value
Mwith probability1/Mand 0… - two_box_risky_value_meanThe mean of the risky distribution is 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_dtd_after_box_zeroWith the history
[(0, 1)], any valid policy has deferred-to-deadline expected utility at most 1. - 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…
- two_box_risky_value_distThe distribution taking the value
Mwith probability1/Mand the value0with probability1 - 1/M. - two_box_fair_value_distThe degenerate discrete distribution taking the value
1with probability1. - DiscreteDistA discrete probability distribution with finite support on non-negative real values, defined by a finite support set, non-negative…
- expectedUtilityDTDThe expected net utility of an adaptive policy
π : AdaptivePolicy inst.nunder deferred-to-deadline commitment on a Pandora's problem… - 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…
- 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.
- two_box_deadline_instTwo boxes with zero cost: box 0 has deadline 1 and deterministic value 1; box 1 has deadline 2, value
- Used by 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π…
- two_box_counterexample_familyFor any integer
The proof, explained
The proof proceeds by case analysis on the first action of the policy. If the policy stops immediately, it receives 0 utility. If it first opens box 0, the deterministic value 1 and deadline constraint ensure expected utility at most 1 by an auxiliary lemma. If it first opens box 1, box 0's deadline of 1 expires immediately, forcing any valid continuation policy to stop, which limits the utility to the realized value of box 1; taking the expectation over this risky distribution yields at most 1 since its mean is 1.
If the policy stops immediately without opening any box, its expected utility is 0, which is at most 1. automation
A policy that stops immediately opens no boxes. In the auxiliary expected utility function, an empty history of opened boxes yields 0 payoff, so the expected utility is 0 ≤ 1, closed by simp.
cases π with | stop => simp [expectedUtilityDTD, expectedUtilityDTD.aux]
For a policy that opens box b with continuation cont, the policy is valid and its expected utility is the expected continuation utility over the distribution of box b.
We reformulate the goal using the auxiliary expected utility function on an empty history. By unfolding policy validity (`IsValidPolicyAux.eq_def`), we obtain the hypotheses that box b is not in the opened list, the deadline condition holds, and for every outcome v in the support of box b, the continuation policy `cont v` is valid. Expanding the auxiliary expected utility for opening box b gives the expectation of continuation utilities minus the opening cost (which is 0).
uses
IsValidPolicyAux.eq_def| openBox b cont => show expectedUtilityDTD.aux (two_box_deadline_inst M hM) [] (AdaptivePolicy.openBox b cont) ≤ 1 unfold IsValidPolicy at hπ rw [IsValidPolicyAux.eq_def] at hπ obtain ⟨hb, hd, hv⟩ := hπ simp only [expectedUtilityDTD.aux]If the first box opened is box 0, the expected utility is at most 1.
We perform a case distinction on whether b = 0. In this case, box 0 has the deterministic distribution `two_box_fair_value_dist`, which yields value 1 with probability 1, reducing the expected utility to the utility of `cont 1`. By policy validity, `cont 1` is valid after opening box 0. Applying `two_box_dtd_after_box_zero`, any valid continuation policy after opening box 0 earns at most 1.
uses
if_pos,Finset.sum_singleton,two_box_dtd_after_box_zeroby_cases hb0 : b = 0 · rw [if_pos hb0] simp only [two_box_fair_value_dist, Finset.sum_singleton] have hzero : IsValidPolicyAux (two_box_deadline_inst M hM) rfl [(0 : Fin 2)] (cont 1) := by subst hb0 have h := hv 1 (by simp [two_box_fair_value_dist]) simpa using h have hle := two_box_dtd_after_box_zero M hM (cont 1) hzero subst hb0 simpa using hle
If the first box opened is not box 0, it must be box 1.
When b ≠ 0, the distribution in the expectation is the risky distribution `two_box_risky_value_dist M hM`. Since the instance has only two boxes (b ∈ Fin 2), ruling out 0 leaves b = 1 as the only possibility.
uses
if_neg· rw [if_neg hb0] have hb1 : b = 1 := by fin_cases b · exact absurd rfl hb0 · rfl subst hb1
After opening box 1 with realized outcome x, any valid continuation must stop immediately, achieving utility at most x.
For any value x in the support of the risky distribution, the continuation `cont x` is valid with opened list [1]. By `two_box_valid_stop_of_mem_one`, because box 1 has been opened and the opened list has length at least 1, any valid continuation policy must immediately be `AdaptivePolicy.stop`, since box 0's deadline of 1 has passed. Stopping with history [(1, x)] at time 1 meets box 1's deadline of 2; since x ≥ 0, the resulting utility is exactly max(0, x) = x.
uses
two_box_valid_stop_of_mem_one,List.length_cons,List.length_nilhave hbound : ∀ x ∈ (two_box_risky_value_dist M hM).support, expectedUtilityDTD.aux (two_box_deadline_inst M hM) [((1 : Fin 2), x)] (cont x) ≤ x := by intro x hx have hvalid : IsValidPolicyAux (two_box_deadline_inst M hM) rfl [(1 : Fin 2)] (cont x) := by have h := hv x (by simpa using hx) simpa using h have hstop := two_box_valid_stop_of_mem_one M hM [(1 : Fin 2)] (cont x) hvalid (by simp) (by simp) have hx0 : 0 ≤ x := (two_box_risky_value_dist M hM).val_nonneg x hx rw [hstop] simp only [expectedUtilityDTD.aux, List.length_cons, List.length_nil] simp [hx0]
The total expected utility when opening box 1 first is at most 1. automation
Weighting the pointwise bound on continuation utility by the non-negative probabilities and summing over the support of the risky distribution via `Finset.sum_le_sum` and `mul_le_mul_of_nonneg_left`, the total expected utility is bounded by the mean of the risky distribution. By `two_box_risky_value_mean`, this mean is exactly 1, and linear arithmetic finishes the proof.
uses
Finset.sum_le_sum,mul_le_mul_of_nonneg_left,two_box_risky_value_meanhave hsum : ∑ x ∈ (two_box_risky_value_dist M hM).support, (two_box_risky_value_dist M hM).prob x * expectedUtilityDTD.aux (two_box_deadline_inst M hM) [((1 : Fin 2), x)] (cont x) ≤ ∑ x ∈ (two_box_risky_value_dist M hM).support, (two_box_risky_value_dist M hM).prob x * x := by apply Finset.sum_le_sum intro x hx exact mul_le_mul_of_nonneg_left (hbound x hx) ((two_box_risky_value_dist M hM).prob_nonneg x hx) rw [two_box_risky_value_mean M hM] at hsum linarith
IsValidPolicyAux.eq_def- Unfolds the definition of a valid policy: stopping is always valid, while opening a box requires that it was not previously opened, that opening it does not exceed its deadline, and that every possible realized value leads to a valid continuation policy.
if_pos- If the condition c holds, the conditional expression (if c then t else e) simplifies to t.
Finset.sum_singleton- The sum of a function over a singleton set {a} equals the function evaluated at a.
two_box_dtd_after_box_zero- Under deferred-to-deadline commitment, any valid continuation policy after opening box 0 (which has value 1 and deadline 1) achieves expected utility at most 1.
if_neg- If the condition c does not hold, the conditional expression (if c then t else e) simplifies to e.
two_box_valid_stop_of_mem_one- Any valid continuation policy after opening box 1 must stop immediately, because opening box 0 would violate box 0's deadline of 1.
List.length_cons- The length of a list with an element prepended is one more than the length of the tail.
List.length_nil- The empty list has length 0.
Finset.sum_le_sum- If f(i) ≤ g(i) for all elements i in a finite set, then the sum of f over the set is at most the sum of g over the set.
mul_le_mul_of_nonneg_left- Multiplying both sides of an inequality b ≤ c by a non-negative scalar a preserves the inequality: a * b ≤ a * c.
two_box_risky_value_mean- The expected value of the risky distribution for box 1 is 1.
- Under deferred-to-deadline (DTD) commitment, the value of an opened box is only eligible for the final payoff if the stopping time does not exceed that box's deadline. In this instance, box 0 has deadline 1 and deterministic value 1, while box 1 has deadline 2 and mean value 1.
Written by a model (gemini-3.8-flash) from the Lean proof and the goal states Lean reported at each step. Lean verified the proof; this explanation is a reading aid and is not itself machine-checked.
Lean source view module on GitHub
Choose a tactic — a marked line — to see the goals Lean had before and after it, as in Lean’s infoview. Step with ← → or j k.
/-- Every valid policy achieves DTD expected utility at most 1 on the two-box instance. -/theorem two_box_dtd_le_one (M : ℕ) (hM : 1 < M) (π : AdaptivePolicy 2) (hπ : IsValidPolicy (two_box_deadline_inst M hM) π) : expectedUtilityDTD (two_box_deadline_inst M hM) π ≤ 1 := by cases π with | stop => simp [expectedUtilityDTD, expectedUtilityDTD.aux] | openBox b cont => show expectedUtilityDTD.aux (two_box_deadline_inst M hM) [] (AdaptivePolicy.openBox b cont) ≤ 1 unfold IsValidPolicy at hπ rw [IsValidPolicyAux.eq_def] at hπ obtain ⟨hb, hd, hv⟩ := hπ simp only [expectedUtilityDTD.aux] by_cases hb0 : b = 0 · rw [if_pos hb0] simp only [two_box_fair_value_dist, Finset.sum_singleton] have hzero : IsValidPolicyAux (two_box_deadline_inst M hM) rfl [(0 : Fin 2)] (cont 1) := by subst hb0 have h := hv 1 (by simp [two_box_fair_value_dist]) simpa using h have hle := two_box_dtd_after_box_zero M hM (cont 1) hzero subst hb0 simpa using hle · rw [if_neg hb0] have hb1 : b = 1 := by fin_cases b · exact absurd rfl hb0 · rfl subst hb1 have hbound : ∀ x ∈ (two_box_risky_value_dist M hM).support, expectedUtilityDTD.aux (two_box_deadline_inst M hM) [((1 : Fin 2), x)] (cont x) ≤ x := by intro x hx have hvalid : IsValidPolicyAux (two_box_deadline_inst M hM) rfl [(1 : Fin 2)] (cont x) := by have h := hv x (by simpa using hx) simpa using h have hstop := two_box_valid_stop_of_mem_one M hM [(1 : Fin 2)] (cont x) hvalid (by simp) (by simp) have hx0 : 0 ≤ x := (two_box_risky_value_dist M hM).val_nonneg x hx rw [hstop] simp only [expectedUtilityDTD.aux, List.length_cons, List.length_nil] simp [hx0] have hsum : ∑ x ∈ (two_box_risky_value_dist M hM).support, (two_box_risky_value_dist M hM).prob x * expectedUtilityDTD.aux (two_box_deadline_inst M hM) [((1 : Fin 2), x)] (cont x) ≤ ∑ x ∈ (two_box_risky_value_dist M hM).support, (two_box_risky_value_dist M hM).prob x * x := by apply Finset.sum_le_sum intro x hx exact mul_le_mul_of_nonneg_left (hbound x hx) ((two_box_risky_value_dist M hM).prob_nonneg x hx) rw [two_box_risky_value_mean M hM] at hsum linarith