Proof of Proposition 5.1, p. 42 — for the perturbed scoring w = w′ + ε of Figure 8, OPT(I) = M
ProvedPosetSecretary.LowerBound.opt_perturbation_eqoffline-optimump2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1posetsecretary-problem
Let , , , and let be one of the chains of . Let be a scoring consistent with the order (nonnegative, distinct, increasing along each chain) which is a perturbation of
in the following sense:
- on every chain : ;
- on the chain : for all ;
- .
Then the offline optimum with selections is
The perturbation makes the scores distinct without moving the optimum away from the heavy chain .
Formalization Note The page's further constraint is not needed for this claim and is omitted. Distinctness is part of consistency. The hypothesis is necessary: for the poset is empty and the optimum is .
Preamble
import Mathlib import Definitions.Def_AppliedComb_Posets_width import Definitions.Def_PosetSecretary_LowerBound_Setting
Formal statement
namespace PosetSecretary.LowerBound
theorem opt_perturbation_eq (ω k : ℕ) (hk : 1 ≤ k) (i₀ : Fin ω) (M : ℝ) (hM : 0 < M)
(w : ChainsPoset ω k → ℝ) (hw : PosetSecretary.ProxyLabel.IsConsistentScoring w)
(hlight : ∀ (i : Fin ω) (j : Fin k), i ≠ i₀ → 0 ≤ w ⟨i, j⟩ ∧ w ⟨i, j⟩ < M / (2 * k))
(hheavy : ∀ j : Fin k, |w ⟨i₀, j⟩ - M / k| < M / (2 * k))
(hsum : ∑ j : Fin k, (w ⟨i₀, j⟩ - M / k) = 0) :
PosetSecretary.ProxyLabel.opt w k = M := by sorry
end PosetSecretary.LowerBound
Source
Salem & Gupta, Secretary Problems with Biased Evaluations Using Partial Ordinal Information, SSRN 3444283 (version of 2022-04-17), proof of Proposition 5.1, Appendix F, p. 42, third paragraph
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.