Main theorem — against any online weight-adaptive adversary, the threshold algorithm (9) earns
ProvedMatroidProphetKW.Single.main_theoremLet be a matroid on a finite ground set, and for each let be a probability distribution supported on with finite mean. The weights are independent with , and is the expected weight of the maximum-weight independent set.
An online weight-adaptive adversary reveals the elements one at a time, choosing each next element knowing only the weights already revealed. The algorithm of §3.3, having selected , selects the arriving element if and only if and
where is an independent copy of the weights and is the remainder of the -maximum-weight basis (§3.2). Then for every online weight-adaptive adversary, the set the algorithm selects satisfies
This is the matroid prophet inequality: on every matroid, an online algorithm facing the elements in an adversarial, adaptively chosen order earns at least half of what a prophet who sees all weights in advance earns. The factor is the best possible already for rank-one matroids (the classical prophet inequality).
Formalization Note The statement is for the paper's own algorithm, which is stronger than the existence statement of §3. The thresholds are fixed by (9), not assumed to satisfy (2)–(3). The adversary is deterministic and measurable in the revealed weights; randomized adversaries are mixtures of these. and are Bochner integrals under the finite-mean assumption.
import Mathlib import Definitions.Def_MatroidProphetKW_Single_Setting import Definitions.Def_MatroidProphetKW_Single_Online import Definitions.Def_MatroidProphetKW_Single_Algorithm
namespace MatroidProphetKW.Single
open MeasureTheory
/-- Main theorem (Kleinberg–Weinberg, arXiv:1201.4764v1, §3, p. 4; Proposition 1, p. 6, with
`α = 2`; algorithm (9), p. 7): against every online weight-adaptive adversary, the algorithm of
§3.3 — select `x_i` iff `A_{i−1} ∪ {x_i} ∈ ℐ` and `w(x_i) ≥ ½ E[w′(R(A_{i−1})) − w′(R(A_{i−1} ∪ {x_i}))]`
— earns `E[w(A)] ≥ ½ · OPT`. -/
theorem main_theorem {α : Type*} [Fintype α] [DecidableEq α]
(M : Matroid α) (hE : M.E = Set.univ)
(F : α → Measure ℝ) [∀ x, IsProbabilityMeasure (F x)]
(hF0 : ∀ x, F x (Set.Iio 0) = 0) (hFi : ∀ x, Integrable id (F x))
(adv : List α → (α → ℝ) → α) (hadv : IsAdversary adv) :
(1 / 2) * OPT M F ≤ ∫ w, wt w (run M (kwThr M F) (advOrder adv w) w) ∂(Measure.pi F) := by sorry
end MatroidProphetKW.Single
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.