Theorem 17, p. 17 — explicit closed form of the greedy dual solution for secretaries with k samples
ProvedSecretaryAdvice.SamplesDual.theorem_17Consider the secretary problem with secretaries and samples: the signal of a secretary is , the number of sample elements smaller than it. Let be the greedy (backward-induction) solution (8) of the dual LP of §5, with coefficients and for (and for ). Then for every signal ,
and for every round and every signal ,
with the convention if .
Since the greedy solution is optimal for the dual (Theorem 16), this gives a non-recursive description of the optimal dual solution, from which the optimal thresholds in signal space can be read off.
Formalization Note Rounds are as natural numbers, signals are Fin (k + 1), and all arithmetic is in . The statement keeps the : it is about the greedy recursion (8) as defined, which clips at every round. The paper's proof treats the recursion with the maximum removed (the companion milestone unclipped_closed_form); the passage from the un-clipped to the clipped recursion is not argued in the paper and is part of this goal.
import Mathlib import Definitions.Def_SecretaryAdvice_SamplesDual_ClosedForm open Finset
namespace SecretaryAdvice.SamplesDual
/-- Theorem 17, p. 17: the greedy dual solution (8) with the samples coefficients of §5 is
`u(n,s) = 1/(k+1)·∏_{t=1}^{n−1} (s+t)/(k+t+1)` and, for `i < n`,
`u(i,s) = max {0, innerFormula n k i s}`, for every round `1 ≤ i ≤ n` and signal `s ∈ {0,…,k}`. -/
theorem theorem_17 (n k i : ℕ) (hi : 1 ≤ i) (hin : i ≤ n) (s : Fin (k + 1)) :
samplesGreedy n k i s = explicitFormula n k i s := by sorry
end SecretaryAdvice.SamplesDual
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.