Appendix C, p. 29 — binary greedy dual variables are non-decreasing
ProvedSecretaryAdvice.Binary.greedy_monotonebinary-classifierlinear-optimizationp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1secretary-problem
Let be the binary-classifier dual vector constructed by the backward recurrence in equation (10). For each signal and each adjacent pair of rounds ,
This monotonicity is one of the two dual properties required by Proposition 12 to obtain a threshold policy.
Formalization Note The theorem uses the exact finite greedy vector, including the maximum with zero, and the model's ranges .
Preamble
import Mathlib import Definitions.Def_SecretaryAdvice_Binary_LP
Formal statement
namespace SecretaryAdvice.Binary
/-- Appendix C, p. 29: the greedy dual variables increase with round number. -/
theorem greedy_monotone (n : ℕ) (hn : 1 ≤ n) (p p' : ℝ)
(hp0 : (1 / 2 : ℝ) ≤ p) (hp1 : p ≤ 1)
(hp'0 : (1 / 2 : ℝ) ≤ p') (hp'1 : p' ≤ 1) :
∀ i : ℕ, 1 ≤ i → i < n → ∀ s : Bool,
greedy n p p' i s ≤ greedy n p p' (i + 1) s := by sorry
end SecretaryAdvice.Binary
Source
Dütting et al., Secretaries with Advice, arXiv:2011.06726v1, p. 29, Appendix C, first paragraph
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.