Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Lemma 1 — structural decomposition (corrected: supply-free components)

Proved
TwoStageMatch.lemma_1

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

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

Let g:R→Rg:\mathbb R\to\mathbb Rg:R→R be differentiable, monotone (non-decreasing) and strictly convex. Suppose all weights are positive, let x∗x^*x∗ be an optimal solution of Pg\mathscr P^gPg, and write yj∗=∑i∈N(j)xij∗y^*_j=\sum_{i\in N(j)}x^*_{ij}yj∗​=∑i∈N(j)​xij∗​. Let G′=(D1,S,E′)G'=(D_1,S,E')G′=(D1​,S,E′) with E′={(i,j):xij∗>0}E'=\{(i,j):x^*_{ij}>0\}E′={(i,j):xij∗​>0}, let S(0)={j:yj∗=1}S^{(0)}=\{j: y^*_j=1\}S(0)={j:yj∗​=1}, D(0)={i∈D1:∃j∈S(0),xij∗>0}D^{(0)}=\{i\in D_1:\exists j\in S^{(0)},x^*_{ij}>0\}D(0)={i∈D1​:∃j∈S(0),xij∗​>0}, and let the remaining levels be the connected components of G′[D1∖D(0),S∖S(0)]G'[D_1\setminus D^{(0)},S\setminus S^{(0)}]G′[D1​∖D(0),S∖S(0)], with slacks c(l)c^{(l)}c(l) (c(0)=0c^{(0)}=0c(0)=0; a component without supply vertices has slack 000). Then:

  1. (Uniformity) for every level lll and every supply j∈S(l)j\in S^{(l)}j∈S(l), wj(1−yj∗)=c(l)w_j(1-y^*_j)=c^{(l)}wj​(1−yj∗​)=c(l); in particular all supplies of a level have the same value wj(1−yj∗)w_j(1-y^*_j)wj​(1−yj∗​), and it is 000 on level 000.
  2. (Monotonicity) for every edge (i,j)∈E(i,j)\in E(i,j)∈E with i∈D(l)i\in D^{(l)}i∈D(l) and j∈S(l′)j\in S^{(l')}j∈S(l′), c(l′)≤c(l)c^{(l')}\le c^{(l)}c(l′)≤c(l); equivalently, there is no edge of EEE between D(l)D^{(l)}D(l) and S(l′)S^{(l')}S(l′) if c(l)<c(l′)c^{(l)}<c^{(l')}c(l)<c(l′).
  3. (Saturation) every i∈D(l)i\in D^{(l)}i∈D(l), for a component lll containing a supply vertex, is fully matched: ∑j∈N(i)xij∗=1\sum_{j\in N(i)}x^*_{ij}=1∑j∈N(i)​xij∗​=1.
  4. (Supply-free components) a component that contains no supply vertex consists of a single demand vertex iii, and every supply jjj with (i,j)∈E(i,j)\in E(i,j)∈E lies in S(0)S^{(0)}S(0).

The printed lemma states saturation for every component l≥1l\ge 1l≥1. That fails for a component without supply vertices: take D1={a,b}D_1=\{a,b\}D1​={a,b}, S={s}S=\{s\}S={s}, ws=1w_s=1ws​=1, E={(a,s),(b,s)}E=\{(a,s),(b,s)\}E={(a,s),(b,s)}; then x∗=(xas∗,xbs∗)=(1,0)x^*=(x^*_{as},x^*_{bs})=(1,0)x∗=(xas∗​,xbs∗​)=(1,0) is optimal for every admissible ggg (for instance g=exp⁡g=\expg=exp), S(0)={s}S^{(0)}=\{s\}S(0)={s}, D(0)={a}D^{(0)}=\{a\}D(0)={a}, and ({b},∅)(\{b\},\emptyset)({b},∅) is a component with ∑jxbj∗=0\sum_j x^*_{bj}=0∑j​xbj∗​=0. Clauses 3 and 4 are the corrected statement; the proof of Theorem 1 goes through with αb=c=0\alpha_b=c=0αb​=c=0 on such a vertex.

This decomposition is the structural input to the dual-fitting proof of Theorem 1: it fixes the demand duals αi=c(l)\alpha_i=c^{(l)}αi​=c(l) and gives Type I feasibility (6).

Differences from the source:

  • correction: (iii) saturation for every component l ∈ [1 : L], with c(l) defined through a supply vertex of the component → saturation for components that contain a supply vertex, plus clause 4 (a supply-free component is one demand vertex whose E-neighbours all lie in S⁽⁰⁾), with c := 0 on such a component; reason: counterexample satisfying every assumption: D₁ = {a, b}, S = {s}, w_s = 1, E = {(a, s), (b, s)}, g = exp; x* = (1, 0) is optimal and ({b}, ∅) is a component with Σ_j x*_bj = 0 ≠ 1
  • correction: the L ≥ 1 connected components of G′[D₁ \ D⁽⁰⁾, S \ S⁽⁰⁾] → any number L ≥ 0 of components (no claim that L ≥ 1); reason: counterexample: D₁ = {a}, S = {s}, one edge, w_s = 1; x* = 1 is optimal and the induced subgraph is empty, so L = 0
  • encoding: 𝒫^g and its optimal solution, with 1/w_j in the objective → hypothesis w_j > 0 for every supply j; reason: the paper's 𝒫^g divides by w_j and is undefined when some w_j = 0; the hypothesis excludes only that undefined case
  • reading: the optimal solution x* of 𝒫^g → every optimal solution x*; reason: 𝒫^g need not have a unique minimizer in x (only the loads y* are pinned down); the claim is made for each
  • encoding: uniformity ∀ l, j, j′ ∈ S⁽ˡ⁾: w_j(1 − y_j) = w_j′(1 − y_j′) ≜ c⁽ˡ⁾; monotonicity: no edge of E between D⁽ˡ⁾ and S⁽ˡ′⁾ if c⁽ˡ⁾ < c⁽ˡ′⁾ → every supply's value w_j(1 − y*_j) equals the slack of its level (c⁽ˡ⁾ defined through a chosen supply vertex); for every edge (i, j) ∈ E, c(level j) ≤ c(level i); levels as Option of the connected components; reason: equivalent formulations (contrapositive of monotonicity, stated for every pair of levels including l = l′); same instances
Preamble
import Mathlib
import Definitions.Def_TwoStageMatch_Algorithm1
import Definitions.Def_TwoStageMatch_Decomposition
Formal statement
namespace TwoStageMatch

/-- **Lemma 1 (Structural decomposition), corrected** (Feng, Niazadeh & Saberi,
arXiv:2210.11648v1, pp.13–14, restated p.ec4; proof pp.ec5–ec6). Let `g` be differentiable,
monotone and strictly convex, let all weights be positive and let `x*` be an optimal solution of
`𝒫^g`. With `y*_j = Σ_i x*_{ij}`, `S⁽⁰⁾`, `D⁽⁰⁾`, the components of `G′[D₁ \ D⁽⁰⁾, S \ S⁽⁰⁾]` and the
level slacks `c⁽ˡ⁾` of `Def_TwoStageMatch_Decomposition`:
1. (uniformity) every supply `j` satisfies `w_j (1 − y*_j) = c⁽ˡ⁾` for its level `l`, and `c⁽⁰⁾ = 0`;
2. (monotonicity) for every edge `(i, j) ∈ E` with `i ∈ D₁` of level `l` and `j` of level `l′`,
   `c⁽ˡ′⁾ ≤ c⁽ˡ⁾` (no edge of `E` from `D⁽ˡ⁾` to `S⁽ˡ′⁾` when `c⁽ˡ⁾ < c⁽ˡ′⁾`);
3. (saturation) every `i ∈ D₁` lying in a component that contains a supply vertex is fully
   matched, `Σ_j x*_{ij} = 1`;
4. (supply-free components) a component that contains no supply vertex consists of a single
   demand vertex `i`, and every supply `j` with `(i, j) ∈ E` lies in `S⁽⁰⁾`.

The printed lemma claims saturation for every component `l ≥ 1`; that fails for a component
without supply vertices (see the item's natural-language statement), hence clauses 3 and 4. -/
theorem lemma_1 {D₁ D₂ S : Type*} [Fintype D₁] [Fintype S] [DecidableEq D₁] [DecidableEq S]
    (I : Instance D₁ D₂ S) (g : ℝ → ℝ) (hgd : Differentiable ℝ g) (hgm : Monotone g)
    (hgc : StrictConvexOn ℝ Set.univ g) (hw : ∀ j, 0 < I.w j)
    (x : D₁ → S → ℝ) (hx : IsOptimal I g x) :
    ((∀ j, I.w j * (1 - load x j) = levelSlack I.w x (levelS x j)) ∧
      levelSlack I.w x none = 0) ∧
    (∀ i j, I.E (Sum.inl i) j →
      levelSlack I.w x (levelS x j) ≤ levelSlack I.w x (levelD x i)) ∧
    (∀ i, levelD x i ≠ none → (∃ j, levelS x j = levelD x i) → ∑ j, x i j = 1) ∧
    (∀ i, levelD x i ≠ none → (¬ ∃ j, levelS x j = levelD x i) →
      (∀ i', levelD x i' = levelD x i → i' = i) ∧
      ∀ j, I.E (Sum.inl i) j → levelS x j = none) := 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, Lemma 1, pp.13–14 (restated p.ec4, proof pp.ec5–ec6)
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