Proposition 5.1, p. 14 (proof p. 42) — on a poset of width ω, every algorithm has sup over scorings of OPT/E[w(Alg)] ≥ ω
ProvedPosetSecretary.LowerBound.proposition_5_1Let be the number of selections and . There is a finite poset of width such that for every selection rule with capacity on and every there is a scoring consistent with with and
Equivalently, for every algorithm , , the supremum ranging over the scorings of . Here a scoring consistent with is nonnegative, injective and strictly increasing along the order, is the largest total score of at most elements, and a selection rule with capacity is the law of the selected set: a probability distribution on subsets of at most elements.
Together with the upper bound for ProxyLabel when the width is known (Corollary 5.1, p. 15), this shows that the width of the poset governs the best achievable competitive ratio.
Formalization Note The printed statement reads "there is an instance … such that for any algorithm" (); this order is false for , since on a fixed instance the rule selecting the best elements has ratio . The formalization follows the last sentence of the proof (Appendix F, p. 42): the poset is fixed first, then the algorithm and , then the scoring. Algorithms are encoded as score-independent distributions of the selected set; this class contains every online algorithm (which sees only the poset and the arrival order), so the bound holds for them. "-competitive" is read as , avoiding a division by , which may be . The hypotheses and are standing: with the poset is empty and with every ratio is . Width is the largest antichain.
import Mathlib import Definitions.Def_AppliedComb_Posets_width import Definitions.Def_PosetSecretary_LowerBound_Setting
namespace PosetSecretary.LowerBound
theorem proposition_5_1 (k ω : ℕ) (hk : 1 ≤ k) (hω : 1 ≤ ω) :
∃ (β : Type) (_ : PartialOrder β) (_ : Fintype β) (_ : DecidableEq β),
AppliedComb.Posets.width β = ω ∧
∀ μ : Finset β → ℝ, IsSelectionRule k μ →
∀ ε : ℝ, 0 < ε →
∃ w : β → ℝ, PosetSecretary.ProxyLabel.IsConsistentScoring w ∧ 0 < PosetSecretary.ProxyLabel.opt w k ∧
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.