Proof of Theorem 1, case M = ∅ and (1), pp. 6–7 — if no candidate deviates, Algorithm 1 hires ı̂ and v(ı̂) ≥ (1−ϵ)/(1+ϵ)·v(i)
ProvedSecretaryPred.LearnedDynkin.case_M_emptycompetitive-ratiolearning-augmented-algorithmsoptimal-stoppingp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-strengthenedp2o-v1secretary-problem
Let candidates have values and predictions , let be any maximizer of , and run Algorithm 1 (learned Dynkin) with any threshold and time . Suppose no candidate deviates, i.e. . Then:
- on every arrival vector the algorithm stays in Prediction mode and hires , so its value is ;
- hence ;
- inequality (1): for every with for all , and every candidate ,
This is the first half of the proof of Theorem 1: when the predictions are accurate up to , the algorithm follows them and is -competitive.
Formalization Note Candidates are Fin n (0-based). The prediction-error condition is written .
Differences from the source:
- generalization: θ = 0.646, τ = 0.313 → any θ and τ; reason: the case M = ∅ never uses θ or τ beyond the definition of M; it specializes to the source's values
- generalization: (1) for the optimal candidate i∗ → (1) for every candidate j; reason: i∗ is one of the j; the chain of (1) uses nothing about i∗
- generalization: ϵ = max_i |1 − v̂(i)/v(i)| → every ε ≥ 0 with |v(i) − v̂(i)| ≤ ε·v(i) for all i; reason: when all v(i) > 0 the source's ϵ is one such ε; the Lean clause also covers v(i) = 0, where the source's ϵ is undefined
- encoding: the algorithm hires ı̂ → algValue = v(ı̂) on every arrival vector t, and expectedValue = v(ı̂); reason: the value of the run and its expectation when ı̂ is the hire
- encoding: |1 − v̂(i)/v(i)| > θ (line 4 and the set M, p. 6) → θ·v(i) < |v(i) − v̂(i)| (Deviates); reason: identical when v(i) > 0; avoids Lean's x/0 = 0, and for v(i) = 0 a candidate deviates iff v̂(i) ≠ 0
- encoding: candidates N = [n] interviewed in random order, arrival times iid Uniform[0, 1] (§2.1), exactly one hire → candidates Fin n (0-based), t uniform on the cube [0, 1]^n (arrivalLaw n), the mode at i is Secretary iff some deviating j has t_j ≤ t_i, and algValue sums the values of all candidates that are first to stop; reason: the run differs from the source's single-hire run only on the null set of arrival vectors with two equal times
Preamble
import Mathlib import Definitions.Def_SecretaryPred_LearnedDynkin_Setting
Formal statement
namespace SecretaryPred.LearnedDynkin
theorem case_M_empty (n : ℕ) (theta tau : ℝ) (v vhat : Fin n → ℝ) (ihat : Fin n)
(hv : ∀ i, 0 ≤ v i) (hvhat : ∀ i, 0 ≤ vhat i) (hihat : ∀ j, vhat j ≤ vhat ihat)
(hM : Mset theta v vhat = ∅) :
(∀ t : Fin n → ℝ, algValue theta tau v vhat ihat t = v ihat) ∧
expectedValue theta tau v vhat ihat = v ihat ∧
∀ eps : ℝ, 0 ≤ eps → (∀ i, |v i - vhat i| ≤ eps * v i) →
∀ j, (1 - eps) / (1 + eps) * v j ≤ v ihat := by sorry
end SecretaryPred.LearnedDynkin
Source
Fujii, Yoshida, The Secretary Problem with Predictions, arXiv:2306.08340v1, pp. 6–7, proof of Theorem 1, case M = ∅, inequality (1)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.