Theorem 4 — for every ε > 0 and τ ∈ (0, 1) some τ-bounded instance gives no value-ordered policy more than (β^τ_k + ε) OPT_sim(I)
ProvedHiringLP.SimUpper.theorem_4In Simultaneous Offering (with overage cost and candidates labelled so that ), a value-ordered policy sends offers to the highest-valued candidates for some . For and let
Theorem. For every number of positions , every and every there is an instance with positions (all values at least ) such that for every
where is the expected reward of offering to and the best expected reward over all offer sets.
Together with Theorem 3 (value-ordered policies can guarantee of the LP bound) this brackets what value-ordered policies can guarantee on -bounded instances between and .
Formalization Note. The page leaves implicit in ; the theorem is stated for every and the instance is required to have exactly positions. The instance is existential, of any size ; validity includes , , and sorted labels, so value-ordered policies are the prefixes of the labelling. is the maximum over all offer sets, not over value-ordered ones.
import Mathlib import Definitions.Def_HiringLP_SimUpper_Model import Definitions.Def_HiringLP_SimUpper_Constants
namespace HiringLP.SimUpper
/-- Theorem 4 (p. 30): for every number of positions `k ≥ 1`, every `ε > 0` and `τ ∈ (0, 1)`
there is a valid, sorted, `τ`-bounded instance with `k` positions on which every value-ordered
policy earns at most `(β^τ_k + ε) · OPT_sim(I)`. -/
theorem theorem_4 (k : ℕ) (hk : 1 ≤ k) (ε τ : ℝ) (hε : 0 < ε) (hτ0 : 0 < τ) (hτ1 : τ < 1) :
∃ (n : ℕ) (I : SimInstance n), I.Valid ∧ I.k = k ∧ I.TauBounded τ ∧
∀ m : ℕ, 1 ≤ m → m ≤ n → reward I (valueOrdered m) ≤ (beta k τ + ε) * OPTsim I := by sorry
end HiringLP.SimUpper
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.