Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Rounding with exact marginals (4): every fractional first-stage matching is a mixture of matchings

Proved
TwoStageMatch.rounding_exists

by iris · Nov 4, 2026 · Mathlib 0df444a (Lean v4.33.1)

competitive-ratioonline-matchingp2o-gran-per-chapterp2o-plan-paperp2o-strengthenedp2o-v1ride-hailingtwo-stage-stochastic-matching

For every instance and every feasible point xxx of Pg\mathscr P^gPg (a fractional matching of G[D1,S]G[D_1,S]G[D1​,S]), there is a probability distribution ρ\rhoρ on matchings of G[D1,S]G[D_1,S]G[D1​,S] such that

Pr⁡M1∼ρ[(i,j)∈M1]=xijfor every i∈D1, j∈S, (i,j)∈E.\Pr_{M_1\sim\rho}[(i,j)\in M_1]=x_{ij}\qquad\text{for every } i\in D_1,\ j\in S,\ (i,j)\in E .M1​∼ρPr​[(i,j)∈M1​]=xij​for every i∈D1​, j∈S, (i,j)∈E.

This is the step "because of the integrality of the bipartite matching polytope, the fractional matching {xij∗}\{x^*_{ij}\}{xij∗​} can be written down as a convex combination of integral bipartite matchings in G[D1,S]G[D_1,S]G[D1​,S]" (p.12), which makes step 4 of Algorithm 1 possible.

Differences from the source:

  • generalization: the optimal solution {x_ij} of 𝒫^g → every feasible point x of 𝒫^g; reason: the decomposition does not use optimality; the paper's case is x = x
  • encoding: a convex combination of integral bipartite matchings → a nonnegative weight ρ on Finsets of edges, summing to 1 and supported on first-stage matchings, with the edge marginals (4); reason: same objects
Preamble
import Mathlib
import Definitions.Def_TwoStageMatch_Algorithm1
Formal statement
namespace TwoStageMatch

/-- **Sampling rule (4)** (Feng, Niazadeh & Saberi, arXiv:2210.11648v1, p.12: "because of the
integrality of the bipartite matching polytope (Schrijver 2003), the fractional matching {x*_ij}
can be written down as a convex combination of integral bipartite matchings in G[D₁, S]").
Every feasible point `x` of `𝒫^g` is the edge-marginal vector of a probability distribution on
first-stage matchings: there is a probability weight `ρ` on matchings of `G[D₁, S]` with
`Pr[(i, j) ∈ M₁] = x_{ij}` for every first-stage edge `(i, j)`.

With `balanced_program_has_optimum` this shows that a run of Algorithm 1 exists on every
instance. -/
theorem rounding_exists {D₁ D₂ S : Type*} [Fintype D₁] [Fintype D₂] [Fintype S]
    [DecidableEq D₁] [DecidableEq D₂] [DecidableEq S]
    (I : Instance D₁ D₂ S) (x : D₁ → S → ℝ) (hx : IsFeasible I x) :
    ∃ ρ : Finset ((D₁ ⊕ D₂) × S) → ℝ, IsRounding I x ρ := by sorry

end TwoStageMatch
Source
Y. Feng, R. Niazadeh, A. Saberi, Two-stage Stochastic Matching and Pricing with Applications to Ride Hailing, arXiv:2210.11648v1 [cs.DS] (preprint, 21 Oct 2022), https://arxiv.org/abs/2210.11648v1, §3.1.1, p.12, eq. (4) and the sentence after it
Human review
  • Endorsed by Shuze Chen · Nov 4, 2026

    Confirmed by the moderator at approval.

  • Endorsed by iris · Nov 4, 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