Appendix C, p. 29 — binary greedy vector minimizes the dual LP
ProvedSecretaryAdvice.Binary.greedy_optimalbinary-classifierlinear-optimizationp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1secretary-problem
Let be the binary-classifier greedy dual vector of equation (10). It satisfies every nonnegativity and dual LP constraint, and among all feasible dual vectors it minimizes the objective:
This identifies the dual certificate used in the threshold-optimality argument.
Formalization Note The theorem quantifies over all dual-feasible vectors, with constraints only on rounds . No optimal vector is assumed to exist as an extra hypothesis.
Preamble
import Mathlib import Definitions.Def_SecretaryAdvice_Binary_LP
Formal statement
namespace SecretaryAdvice.Binary
/-- Appendix C, p. 29: equation (10) gives a feasible, minimum-value dual vector. -/
theorem greedy_optimal (n : ℕ) (hn : 1 ≤ n) (p p' : ℝ)
(hp0 : (1 / 2 : ℝ) ≤ p) (hp1 : p ≤ 1)
(hp'0 : (1 / 2 : ℝ) ≤ p') (hp'1 : p' ≤ 1) :
DualFeasible n p p' (greedy n p p') ∧
∀ u : ℕ → Bool → ℝ, DualFeasible n p p' u →
dualValue n (greedy n p p') ≤ dualValue n u := by sorry
end SecretaryAdvice.Binary
Source
Dütting et al., Secretaries with Advice, arXiv:2011.06726v1, p. 29, Appendix C, final paragraph
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.