Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Lemma 6: lowering y1y^1y1 moves the match of iii in period k(j)−1k(j)-1k(j)−1 weakly earlier

Proved
ReusableMatching.lemma_6

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

competitive-analysisonline-matchingp2o-gran-per-chapterp2o-plan-paperp2o-v1primal-dualreusable-resources

Let an OBMRR instance and β>0\beta>0β>0 be given, fix an edge (i,j)∈E(i,j)\in E(i,j)∈E and the seeds Y−i,jY_{-i,j}Y−i,j​, and fix y2∈[0,1]y^2\in[0,1]y2∈[0,1]. Let z∈[0,1]z\in[0,1]z∈[0,1] be such that, for y1=zy^1=zy1=z, resource iii is matched to an arrival t(z)t(z)t(z) of period k(j)−1k(j)-1k(j)−1. Then for every y1≤zy^1\le zy1≤z, resource iii is matched, in the run with seed y1y^1y1, to an arrival of period k(j)−1k(j)-1k(j)−1 that is t(z)t(z)t(z) or precedes it.

This monotonicity in y1y^1y1 is what makes the three regimes of Lemma 7 intervals.

Differences from the source:

  • reading: the lemma does not name y² → the statement holds for every y², the same in the run at y¹ = z and in the run at y¹ ≤ z; reason: the run up to the end of period k(j) − 1 does not read y² (proof, p.10)
  • encoding: fixed seeds Y_{−i,j} and the run PR(y¹, y²) (p.9) → a full seed vector Y whose coordinates (i, k(j) − 1) and (i, k(j)) are overwritten by y¹, y² (twoSeed); the statement is for every Y; reason: Lean convention; every Y_{−i,j} is obtained this way, and the paper fixes an arbitrary Y_{−i,j}
  • reading: arg max over the available neighbours, no tie rule (Algorithm 1, p.8) → the least maximizer for a linear order on V (a fixed priority order; V and its order are arbitrary); reason: the paper fixes no tie rule; its proofs of Lemmas 4, 6 and 8 compare runs at fixed seeds and need a choice among tied resources that does not depend on the seeds
  • encoding: arrivals 1, …, |U|; periods of length d with a dummy period before the first arrival (p.8) → arrivals Fin n numbered from 0; arrival t lies in period t / d + 1; period 0 is the dummy period; seeds indexed by V × Fin (n + 1); reason: Lean convention; same instances and same runs
  • encoding: d ∈ ℕ (p.2) → 1 ≤ d, as a field of the instance; reason: the model ("unavailable for the next d − 1 periods") has no meaning at d = 0
Preamble
import Mathlib
import Definitions.Def_ReusableMatching_PeriodicReranking
import Definitions.Def_ReusableMatching_twoSeed
Formal statement
namespace ReusableMatching

/-- **Lemma 6** of Delong, Farhadi, Niazadeh, Sivan & Udwani, arXiv:2110.07084v2, p.10, for a fixed
edge `(i, j) ∈ E` and fixed seeds `Y_{−i,j}`:

"Consider a value `z ∈ [0, 1]` such that for `y¹ = z`, `i` is matched to some arrival, say `t(z)`,
in period `k(j) − 1`. Then, for every `y¹ ≤ z`, `i` is matched in period `k(j) − 1` to arrival
`t(z)` or an arrival that precedes it."

**Formalization Note.**
* The lemma does not name `y²`; the run of period `k(j) − 1` does not read it ("The value of `y²`
  does not affect the output of PR in periods prior to `k(j)`", proof, p.10). The statement is for
  every `y²`, the same in the run at `y¹ = z` and in the run at `y¹ ≤ z`.
* "Arrival `t` in period `k(j) − 1`" is `period I t = prevPeriod I j`.
* `β > 0` (p.8; the proof uses the monotonicity of `g`). -/
theorem lemma_6 {V : Type*} [Fintype V] [LinearOrder V] {n : ℕ} (I : OBMRRInstance V n)
    (β : ℝ) (hβ : 0 < β) (i : V) (j : Fin n) (hij : (i, j) ∈ I.E) (Y : Seeds V n)
    (z y2 : unitInterval) (tz : Fin n) (htz : period I tz = prevPeriod I j)
    (hmatch : PeriodicReranking I β (twoSeed I Y i j z y2) tz = some i) :
    ∀ y1 : unitInterval, y1 ≤ z →
      ∃ t : Fin n, period I t = prevPeriod I j ∧ t ≤ tz ∧
        PeriodicReranking I β (twoSeed I Y i j y1 y2) t = some i := by sorry

end ReusableMatching
Source
Delong, Farhadi, Niazadeh, Sivan & Udwani, Online Bipartite Matching with Reusable Resources, arXiv:2110.07084v2, Lemma 6, p.10
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