Proof of Proposition 5.1, p. 42, display — a perturbed scoring with OPT(I) = M and E[w(Alg(I))] ≤ (1+ε)OPT(I)/ω
ProvedPosetSecretary.LowerBound.exists_perturbation_expectedScore_leLet , , and let be a selection rule with capacity on . Let be a chain whose selection probabilities satisfy , and let and . Then there is a scoring consistent with the order such that and
This is the display of the proof of Proposition 5.1: the score is concentrated on the least-selected chain, and the remaining chains carry an arbitrarily small total score that only serves to make all scores distinct.
Formalization Note The statement is existential in the scoring. The page's middle inequality drops the term , which the page's constraints (, ) do not make nonpositive; the bound holds for perturbations chosen small enough, not for every admissible one, and the existential form records exactly that. The scoring is chosen after , as on the page, where is fixed before the scores.
import Mathlib import Definitions.Def_AppliedComb_Posets_width import Definitions.Def_PosetSecretary_LowerBound_Setting
namespace PosetSecretary.LowerBound
theorem exists_perturbation_expectedScore_le (ω k : ℕ) (hk : 1 ≤ k) (hω : 1 ≤ ω)
(μ : Finset (ChainsPoset ω k) → ℝ) (hμ : IsSelectionRule k μ) (i₀ : Fin ω)
(hi₀ : ∑ j : Fin k, selProb μ ⟨i₀, j⟩ ≤ (k : ℝ) / ω) (M : ℝ) (hM : 0 < M)
(ε : ℝ) (hε : 0 < ε) :
∃ w : ChainsPoset ω k → ℝ, PosetSecretary.ProxyLabel.IsConsistentScoring w ∧ PosetSecretary.ProxyLabel.opt w k = M ∧
expectedScore μ w ≤ (1 + ε) * PosetSecretary.ProxyLabel.opt w k / ω := by sorry
end PosetSecretary.LowerBound
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.