two_box_dtd_after_box_zero
With the history [(0, 1)], any valid policy has deferred-to-deadline expected utility at most 1.
Statement
theorem two_box_dtd_after_box_zero (M : ℕ) (hM : 1 < M) (π : AdaptivePolicy 2) (hπ : IsValidPolicyAux (two_box_deadline_inst M hM) rfl [(0 : Fin 2)] π) : expectedUtilityDTD.aux (two_box_deadline_inst M hM) [((0 : Fin 2), (1:ℝ))] π ≤ 1
- Source
- step towards two_box_counterexample_family
- Verified
- 24 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 10
- 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. - 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…
- 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. - 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…
- expectedUtilityDTDThe expected net utility of an adaptive policy
π : AdaptivePolicy inst.nunder deferred-to-deadline commitment on a Pandora's problem…
- 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 2
- 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_counterexample_familyFor any integer
M > 1, there exists a 2-box Pandora deadline instance such that2 - 1 / M ≤ optDUS instand every valid policyπ…
The proof, explained
The theorem is proved by case analysis on the policy $\pi$. If $\pi$ stops immediately at round 1, box 0 (deadline 1) is unexpired, yielding utility 1. If $\pi$ opens another box, validity forces it to open box 1, after which any valid continuation policy must stop at round 2 by `two_box_valid_stop_of_mem_one`. At round 2, box 0 has expired and contributes nothing, while box 1 yields its revealed value $x$. Taking the expectation over $x$, the expected payoff is bounded by the mean of box 1, which equals 1 by `two_box_risky_value_mean`.
If the policy stops immediately, its expected utility is at most 1. automation
We perform a case split on the policy $\pi$. If $\pi$ is `stop`, the process halts at round 1. Box 0 was opened in round 1 and has deadline 1 ($1 \le 1$), so it is not expired, yielding payoff $\max(0, 1) = 1$. The simplification tactic unfolds the expected utility definition and confirms $1 \le 1$.
cases π with | stop => simp [expectedUtilityDTD.aux, two_box_deadline_inst]
If the policy opens another box, it must open box 1.
If $\pi$ opens some box $b$ with continuation `cont`, the validity condition `IsValidPolicyAux.eq_def` requires $b \notin [0]$ (`List.mem_singleton`), so $b \ne 0$. Since there are only two boxes (0 and 1) in `Fin 2`, case analysis rules out $b = 0$, forcing $b = 1$.
uses
IsValidPolicyAux.eq_def,List.mem_singleton,List.length_singleton| openBox b cont => rw [IsValidPolicyAux.eq_def] at hπ obtain ⟨hb, hd, hv⟩ := hπ simp only [List.mem_singleton, List.length_singleton] at hb hd have hb1 : b = (1 : Fin 2) := by fin_cases b · exact absurd rfl hb · rfl subst hb1Opening box 1 reduces the utility to an expectation over continuation policies, each valid with history $[1, 0]$.
Unfolding the expected utility for opening box 1 (which has cost 0) expresses the utility as the expectation of the continuation payoff over outcomes $v$ in the support of box 1's risky distribution. From the validity hypothesis, each continuation policy $\text{cont}(v)$ is valid for the opened list $[1, 0]$.
simp only [Fin.isValue, expectedUtilityDTD.aux, two_box_deadline_inst] simp only [Fin.reduceEq, reduceIte] have hv' : ∀ v ∈ (two_box_risky_value_dist M hM).support, IsValidPolicyAux (two_box_deadline_inst M hM) rfl [(1 : Fin 2), 0] (cont v) := by simpa using hv
For every outcome $x$ of box 1, the continuation policy stops immediately, yielding utility at most $x$.
For any value $x$ in the support of box 1, because box 1 is in the opened list $[1, 0]$ (which has length 2), `two_box_valid_stop_of_mem_one` forces $\text{cont}(x) = \text{stop}$. Stopping at history $[(1, x), (0, 1)]$ means stopping time $t = 2$. At time 2, box 0 (deadline 1) has expired ($2 \le 1$ is false) and contributes 0, while box 1 (deadline 2) is unexpired ($2 \le 2$) and contributes $x \ge 0$. Evaluating the fold over the history with `List.length_cons` and `List.length_nil` simplifies the payoff to $\max(0, x) = x \le 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), (0, 1)] (cont x) ≤ x := by intro x hx have hcont := two_box_valid_stop_of_mem_one M hM [(1 : Fin 2), 0] (cont x) (hv' x hx) (by simp) (by simp) have hx0 : 0 ≤ x := (two_box_risky_value_dist M hM).val_nonneg x hx rw [hcont] simp only [expectedUtilityDTD.aux, two_box_deadline_inst, List.length_cons, List.length_nil, Fin.isValue] simp [hx0]
The expected utility of opening box 1 is at most 1, concluding the proof. automation
Because each continuation payoff is bounded by $x$ and probabilities are nonnegative, `Finset.sum_le_sum` and `mul_le_mul_of_nonneg_left` show that the expected utility is bounded by the mean value $\sum x \cdot P(x)$. Rewriting with `two_box_risky_value_mean` replaces this expectation with 1, and linear arithmetic (`linarith`) completes 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), (0, 1)] (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- Unfolding equation for `IsValidPolicyAux`: `stop` is always valid, while `openBox b cont` is valid if box $b$ has not yet been opened, the round does not exceed $b$'s deadline, and all continuation policies are valid.
List.mem_singleton- An element belongs to a singleton list $[b]$ if and only if it equals $b$.
List.length_singleton- A singleton list has length 1.
two_box_valid_stop_of_mem_one- In the two-box instance, any valid policy must stop immediately once box 1 has been opened and at least one box is in the opened history.
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- A finite sum of pointwise smaller terms is less than or equal to the sum of the larger terms.
mul_le_mul_of_nonneg_left- Multiplying both sides of an inequality by a nonnegative factor preserves the inequality.
two_box_risky_value_mean- The expected value of the distribution for the risky box 1 is 1.
- In the deferred-to-deadline model, the value of box 0 opened in round 1 expires if the policy continues to round 2 because its deadline is 1; this expiry is verified formally by `simp` evaluating the list fold over the history at stopping time $t = 2$.
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.
theorem two_box_dtd_after_box_zero_unfold (M : ℕ) (hM : 1 < M) (π : AdaptivePolicy 2) : expectedUtilityDTD (two_box_deadline_inst M hM) π = expectedUtilityDTD.aux (two_box_deadline_inst M hM) [] π := rfl/-- After box 0 (value 1) has been opened, the DTD payoff of any valid policy is at most 1, because box 0 is expired by round 2 and box 1 has mean value 1. -/theorem two_box_dtd_after_box_zero (M : ℕ) (hM : 1 < M) (π : AdaptivePolicy 2) (hπ : IsValidPolicyAux (two_box_deadline_inst M hM) rfl [(0 : Fin 2)] π) : expectedUtilityDTD.aux (two_box_deadline_inst M hM) [((0 : Fin 2), (1:ℝ))] π ≤ 1 := by cases π with | stop => simp [expectedUtilityDTD.aux, two_box_deadline_inst] | openBox b cont => rw [IsValidPolicyAux.eq_def] at hπ obtain ⟨hb, hd, hv⟩ := hπ simp only [List.mem_singleton, List.length_singleton] at hb hd have hb1 : b = (1 : Fin 2) := by fin_cases b · exact absurd rfl hb · rfl subst hb1 simp only [Fin.isValue, expectedUtilityDTD.aux, two_box_deadline_inst] simp only [Fin.reduceEq, reduceIte] have hv' : ∀ v ∈ (two_box_risky_value_dist M hM).support, IsValidPolicyAux (two_box_deadline_inst M hM) rfl [(1 : Fin 2), 0] (cont v) := by simpa using hv have hbound : ∀ x ∈ (two_box_risky_value_dist M hM).support, expectedUtilityDTD.aux (two_box_deadline_inst M hM) [((1 : Fin 2), x), (0, 1)] (cont x) ≤ x := by intro x hx have hcont := two_box_valid_stop_of_mem_one M hM [(1 : Fin 2), 0] (cont x) (hv' x hx) (by simp) (by simp) have hx0 : 0 ≤ x := (two_box_risky_value_dist M hM).val_nonneg x hx rw [hcont] simp only [expectedUtilityDTD.aux, two_box_deadline_inst, List.length_cons, List.length_nil, Fin.isValue] 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), (0, 1)] (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