Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Theorem 1.10, p. 5 (restated p. 16) — a (b, c)-selectable greedy OCRS gives E[f(S)] ≥ c·F(x), and E[f(S(1/2))] ≥ (c/4)·F(x) for non-monotone f

Proved
OnlineCRS.Submod.selectability_to_approximation

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

almighty-adversarymultilinear-extensiononline-contention-resolutionp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1submodular-functions

Let NNN be a finite ground set, F⊆2N\mathcal F\subseteq 2^NF⊆2N a down-closed family of feasible sets and P⊆[0,1]NP\subseteq[0,1]^NP⊆[0,1]N a relaxation of it. Let b,c∈[0,1]b,c\in[0,1]b,c∈[0,1], let π\piπ be a (b,c)(b,c)(b,c)-selectable greedy OCRS for PPP (deterministic or randomized), and let x∈bPx\in bPx∈bP. Let f:2N→R≥0f:2^N\to\mathbb R_{\ge0}f:2N→R≥0​ be non-negative and submodular, with multilinear extension F(x)=E[f(R(x))]F(x)=\mathbb E[f(R(x))]F(x)=E[f(R(x))]. The elements arrive in an order chosen by the almighty adversary, who knows the realized active set R(x)R(x)R(x) and the realized family Fx\mathcal F_xFx​ before choosing it.

  1. If fff is moreover monotone, the set SSS selected by π\piπ satisfies
E[f(S)]≥c⋅F(x).\mathbb E[f(S)]\ge c\cdot F(x).E[f(S)]≥c⋅F(x).
  1. Even if fff is not monotone, let S(1/2)S(1/2)S(1/2) contain every element of SSS independently with probability 1/21/21/2, the coins being part of the algorithm and known to the adversary. Then
E[f(S(1/2))]≥c4⋅F(x).\mathbb E[f(S(1/2))]\ge \frac c4\cdot F(x).E[f(S(1/2))]≥4c​⋅F(x).

The theorem turns any selectability guarantee into an approximation guarantee for online submodular maximization, losing only the factor ccc for monotone objectives and c/4c/4c/4 in general. It is how the paper derives its applications to prophet inequalities and Bayesian mechanism design from the OCRSs for matroids, matchings and knapsacks.

Formalization Note A deterministic greedy OCRS is the special case of a point-mass family distribution. The adversary is a function from all realized randomness (family, active set, and in part 2 the coins CCC, with S(1/2)=S∩CS(1/2)=S\cap CS(1/2)=S∩C) to arrival orders. The standing assumptions of Definition 1.3 (a down-closed F\mathcal FF, P⊆[0,1]NP\subseteq[0,1]^NP⊆[0,1]N a relaxation of PFP_{\mathcal F}PF​, b,c∈[0,1]b,c\in[0,1]b,c∈[0,1]) are explicit hypotheses. Monotonicity is A⊆B⇒f(A)≤f(B)A\subseteq B\Rightarrow f(A)\le f(B)A⊆B⇒f(A)≤f(B) (footnote 6) and submodularity is f(A∪B)+f(A∩B)≤f(A)+f(B)f(A\cup B)+f(A\cap B)\le f(A)+f(B)f(A∪B)+f(A∩B)≤f(A)+f(B) (footnote 5).

Preamble
import Mathlib
import Definitions.Def_NonmonotoneSubmod_Shared_F
import Definitions.Def_NonmonotoneSubmod_Shared_Submodular
import Definitions.Def_OnlineCRS_Matroid_Basics
import Definitions.Def_OnlineCRS_Submod_Model

open scoped Pointwise
Formal statement
namespace OnlineCRS.Submod

/-- Theorem 1.10 (arXiv:1508.00142v2, p. 5, restated p. 16): let `P ⊆ [0,1]^N` be a relaxation of the
down-closed feasible sets `𝓕`, `w` a `(b, c)`-selectable (randomized) greedy OCRS for `P`, `x ∈ bP`, and
`f ≥ 0` submodular with multilinear extension `F`. Against every almighty adversary:
(i) if `f` is monotone, the selected set `S` satisfies `E[f(S)] ≥ c · F(x)`;
(ii) without monotonicity, `E[f(S(1/2))] ≥ (c/4) · F(x)`, where the coins defining `S(1/2)` are known to
the adversary. -/
theorem selectability_to_approximation {α : Type} [Fintype α] [DecidableEq α]
    (𝓕 : Finset α → Prop) (P : Set (α → ℝ))
    (hPoly : IsPolytope P) (hRel : IsRelaxation 𝓕 P)
    (b c : ℝ) (hb0 : 0 ≤ b) (hb1 : b ≤ 1) (hc0 : 0 ≤ c) (hc1 : c ≤ 1)
    (w : (α → ℝ) → Finset (Finset α) → ℝ) (hw : OnlineCRS.Matroid.IsSelectableRand 𝓕 P b c w)
    (x : α → ℝ) (hx : x ∈ b • P)
    (f : Finset α → ℝ) (hf0 : ∀ S, 0 ≤ f S) (hf : NonmonotoneSubmod.Shared.Submodular f) :
    ((∀ A B : Finset α, A ⊆ B → f A ≤ f B) →
        ∀ ord : Finset (Finset α) → Finset α → List α, (∀ Fam A, IsOrder (ord Fam A)) →
          c * NonmonotoneSubmod.Shared.F f x ≤ expOutput w x ord f) ∧
      (∀ ord : Finset (Finset α) → Finset α → Finset α → List α,
        (∀ Fam A C, IsOrder (ord Fam A C)) →
          c / 4 * NonmonotoneSubmod.Shared.F f x ≤ expOutputHalf w x ord f) := by sorry

end OnlineCRS.Submod
Source
arXiv:1508.00142v2, Theorem 1.10, p. 5; restatement, p. 16
Human review
  • Endorsed by Shuze Chen · Oct 9, 2026

    Confirmed by the moderator at approval.

  • Endorsed by mikedeng1 · Oct 9, 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