Theorem 2.1, PDF p. 2 — the recursive k-choice secretary algorithm selects expected value ≥ (1 − 5/√k)·v
ProvedMultiChoiceSecretary.Alg.theorem_2_1Let be any set of non-negative real numbers, revealed one at a time in a uniformly random order, let be the number of allowed selections, and let be the sum of the largest elements of (all of if ). Kleinberg's recursive algorithm uses the classical secretary rule for ; for it draws , recursively selects up to elements among the first arrivals, and afterwards selects every arrival exceeding , the -th largest of the first values, until elements have been selected in total. Then the expected sum of the selected elements, over the random order and all internal coin tosses, satisfies
This shows that the competitive ratio of the -choice secretary problem tends to as , at rate ; it is the main result of the paper and the basis of its strategyproof online auction.
Formalization Note. When the first phase has seen fewer than arrivals, the page leaves undefined; the formalization reads it as , so every later arrival is selected until the cap. The cap of counts the selections of both phases. For the right-hand side is and the claim is immediate; it is stated uniformly in , as on the page.
import Mathlib import Definitions.Def_MultiChoiceSecretary_Alg_Setting
namespace MultiChoiceSecretary.Alg
theorem theorem_2_1 (S : Finset ℝ) (hS : ∀ x ∈ S, 0 ≤ x) (k : ℕ) (hk : 1 ≤ k) :
(1 - 5 / Real.sqrt k) * topSum S k ≤ expectedValue S k := by sorry
end MultiChoiceSecretary.Alg
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.