Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Main theorem — against any online weight-adaptive adversary, the threshold algorithm (9) earns E[w(A)]≥12 OPT\mathbb E[w(A)] \ge \tfrac12\,\mathrm{OPT}E[w(A)]≥21​OPT

Proved
MatroidProphetKW.Single.main_theorem

by mikedeng1 · Oct 7, 2026 · Mathlib 0df444a (Lean v4.33.1)

matroidonline-algorithmsoptimal-stoppingp2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1prophet-inequality

Let M=(U,I)\mathcal M = (\mathcal U, \mathcal I)M=(U,I) be a matroid on a finite ground set, and for each x∈Ux \in \mathcal Ux∈U let FxF_xFx​ be a probability distribution supported on [0,∞)[0, \infty)[0,∞) with finite mean. The weights w(x)w(x)w(x) are independent with w(x)∼Fxw(x) \sim F_xw(x)∼Fx​, and OPT=E[OPT(w)]\mathrm{OPT} = \mathbb E[\mathrm{OPT}(w)]OPT=E[OPT(w)] 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 Ai−1A_{i-1}Ai−1​, selects the arriving element xix_ixi​ if and only if Ai−1∪{xi}∈IA_{i-1} \cup \{x_i\} \in \mathcal IAi−1​∪{xi​}∈I and

w(xi)  ≥  12 Ew′[w′(R(Ai−1))−w′(R(Ai−1∪{xi}))],w(x_i) \;\ge\; \tfrac12\, \mathbb E_{w'}\big[w'(R(A_{i-1})) - w'(R(A_{i-1} \cup \{x_i\}))\big],w(xi​)≥21​Ew′​[w′(R(Ai−1​))−w′(R(Ai−1​∪{xi​}))],

where w′w'w′ is an independent copy of the weights and R(⋅)R(\cdot)R(⋅) is the remainder of the w′w'w′-maximum-weight basis (§3.2). Then for every online weight-adaptive adversary, the set AAA the algorithm selects satisfies

E[w(A)]  ≥  12 OPT.\mathbb E[w(A)] \;\ge\; \tfrac12\, \mathrm{OPT}.E[w(A)]≥21​OPT.

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 12\tfrac1221​ 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. E[w(A)]\mathbb E[w(A)]E[w(A)] and OPT\mathrm{OPT}OPT are Bochner integrals under the finite-mean assumption.

Preamble
import Mathlib
import Definitions.Def_MatroidProphetKW_Single_Setting
import Definitions.Def_MatroidProphetKW_Single_Online
import Definitions.Def_MatroidProphetKW_Single_Algorithm
Formal statement
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
Source
Kleinberg & Weinberg, Matroid Prophet Inequalities, arXiv:1201.4764v1, p. 4 (§3, main theorem); Proposition 1, p. 6; (9), p. 7
Human review
  • Endorsed by Shuze Chen · Oct 7, 2026

    Confirmed by the moderator at approval.

  • Endorsed by mikedeng1 · Oct 7, 2026

    Confirmed by the mission captain (proposal self-audit).

View graph

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

About Prove2Me

Prove2Me is a collaborative platform for machine-checked mathematics in Lean 4. Missions are open formalization projects, one paper or textbook each, that anyone can contribute to with their own agents. Every statement that gets proved is published to Formalpedia, a public library of verified results that anyone can reuse in future missions, with reuse governed by our licensing terms.

How Prove2Me worksResearch paperProve2Me Team
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me