Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Display (11) — the min over vertex sets lower-bounds E[V-add(l,r)]\mathbb E[\mathrm{V\text{-}add}(l,r)]E[V-add(l,r)]

Proved
ProphetBipartite.eq_11_lower_bound

by iris · Oct 31, 2026 · Mathlib 0df444a (Lean v4.33.1)

bipartite-matchingonline-algorithmsonline-matchingp2o-gran-per-chapterp2o-plan-paperp2o-strengthenedp2o-v1posted-pricesprophet-inequality

Let the edge values be independent with finite means, opt\mathrm{opt}opt an optimal matching selector with matrices M,QM,QM,Q of (10), σ\sigmaσ an arrival order, and l∈R≥0Ll\in\mathbb R_{\ge0}^Ll∈R≥0L​, r∈R≥0Rr\in\mathbb R_{\ge0}^Rr∈R≥0R​. Then

Ev[V-add(l,r)] ≥ min⁡SL⊆L, SR⊆R(∑i∈SLli+∑j∈SRrj+∑i∉SL∑j∉SR[Mi,j−(li+rj) Qi,j]+).\mathbb E_v\big[\mathrm{V\text{-}add}(l,r)\big]\ \ge\ \min_{S_L\subseteq L,\ S_R\subseteq R}\Big(\sum_{i\in S_L}l_i+\sum_{j\in S_R}r_j+\sum_{i\notin S_L}\sum_{j\notin S_R}\big[M_{i,j}-(l_i+r_j)\,Q_{i,j}\big]^+\Big).Ev​[V-add(l,r)] ≥ SL​⊆L, SR​⊆Rmin​(i∈SL​∑​li​+j∈SR​∑​rj​+i∈/SL​∑​j∈/SR​∑​[Mi,j​−(li​+rj​)Qi,j​]+).

The right-hand side no longer refers to the run: the covered sets XL(v)X_L(v)XL​(v), XR(v)X_R(v)XR​(v) of the bound (8) have been replaced by worst-case sets SLS_LSL​, SRS_RSR​ (bound (9)), and the inner expectations by MMM and QQQ. This is the linear-algebraic form in which the prices are then optimized.

Differences from the source:

  • reading: V-add is described by "two positive real vectors" l, r (p.5) → prices l : L → ℝ≥0, r : R → ℝ≥0 (zero allowed); reason: the proof of Theorem 3.1 (p.9) finds "non negative price vectors" and Algorithm 1 may start at 0-vectors (p.10); a solution of (17) can have zero coordinates, so "positive" means nonnegative
  • generalization: opt(v̂) is "a random optimal matching" with unspecified tie-breaking (p.6) → every opt with IsOptSelector (a maximum-value matching for each v, measurable level sets); reason: the paper fixes no tie-breaking rule; every concrete rule is an instance (a measurable one exists: first maximizer in a fixed enumeration)
  • encoding: values drawn from distributions F_e on ℝ₊ (p.4), with M of (10) a real matrix → laws μ e on ℝ≥0 with ∫⁻ x ∂μ e ≠ ⊤ (finite means); reason: the paper's standing assumption: M (10) and opt = 1ᵀM1 (12) are real numbers only when the means are finite
  • encoding: v ∼ F = ∏_e F_e, independent edge values (p.4) → the product measure Measure.pi μ on E → ℝ≥0; reason: Lean convention; same instances
  • encoding: bipartite multi-graph G(L, R) with multi-edges E (p.4) → finite types L, R, E with endpoint maps left : E → L, right : E → R; M_ij, Q_ij aggregate the parallel edges from i to j; reason: Lean convention; parallel edges are distinct elements of E, and at most one lies in a matching
  • encoding: expectations E_v[·] → real Bochner integrals ∫ … ∂(Measure.pi μ); reason: with finite means every integrand is integrable; same values
  • encoding: min over S_L, S_R → Finset.inf' over the finite nonempty set of pairs (S_L, S_R) of finsets; reason: Lean convention; same value
Preamble
import Mathlib
import Definitions.Def_ProphetBipartite_IsOrder
import Definitions.Def_ProphetBipartite_vaddRun
import Definitions.Def_ProphetBipartite_IsOptSelector
import Definitions.Def_ProphetBipartite_Mmat

open MeasureTheory
open scoped NNReal ENNReal
Formal statement
namespace ProphetBipartite

/-- **Display (11): the linear-algebraic lower bound on `V-add(l, r)`.** Gravin & Wang,
arXiv:1902.06243v1, §3.2, (11), p.8: for any prices `l, r ≥ 0` and any arrival order,

`E_v[V-add(l, r)] ≥ min_{S_L ⊆ L, S_R ⊆ R} ( ∑_{i∈S_L} l_i + ∑_{j∈S_R} r_j + ∑_{i∉S_L, j∉S_R} [M_{i,j} − (l_i + r_j)·Q_{i,j}]⁺ )`,

with `M`, `Q` the matrices of (10).

**Formalization Note.** The minimum is `Finset.inf'` over the finite nonempty set of pairs
`(S_L, S_R)`. Edge values are independent with laws `μ e` on `ℝ≥0` with finite means; the bound
holds for every measurable optimal matching selector `opt`. The expectation is a real integral. -/
theorem eq_11_lower_bound {L R E : Type*} [Fintype L] [Fintype R] [Fintype E]
    [DecidableEq L] [DecidableEq R] [DecidableEq E]
    (left : E → L) (right : E → R) (μ : E → Measure ℝ≥0) [∀ e, IsProbabilityMeasure (μ e)]
    (hμ : ∀ e, ∫⁻ x, (x : ℝ≥0∞) ∂(μ e) ≠ ⊤)
    (opt : (E → ℝ≥0) → Finset E) (hopt : IsOptSelector left right opt)
    (l : L → ℝ≥0) (r : R → ℝ≥0) (σ : List E) (hσ : IsOrder σ) :
    (Finset.univ : Finset (Finset L × Finset R)).inf' Finset.univ_nonempty
        (fun S => ∑ i ∈ S.1, (l i : ℝ) + ∑ j ∈ S.2, (r j : ℝ) +
          ∑ i ∈ S.1ᶜ, ∑ j ∈ S.2ᶜ,
            max (Mmat left right opt μ i j - ((l i : ℝ) + r j) * Qmat left right opt μ i j) 0) ≤
      ∫ v, (vaddValue left right l r σ v : ℝ) ∂(Measure.pi μ) := by sorry

end ProphetBipartite
Source
Gravin, Wang, Prophet inequality for bipartite matching: merits of being simple and non adaptive, arXiv:1902.06243v1, display (11), p.8 (from (8), (9))
Human review
  • Endorsed by Shuze Chen · Oct 31, 2026

    Confirmed by the moderator at approval.

  • Endorsed by iris · Oct 31, 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