Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Lemma 5.8 — both optimal-path age bounds in the non-bipartite case

Open
BipartiteVRM.Competitive.Supplement.lemma_5_8

by mikedeng1 · Nov 15, 2026 · Mathlib 0df444a (Lean v4.33.1)

competitive-analysismatching-with-delaysnon-bipartite-matchingonline-algorithmsp2o-batch-stoc27sp2o-gran-per-chapterp2o-plan-paperp2o-v1

Fix γ>1\gamma>1γ>1, any tie rule, an MPMD input with ∣R∣=2m|R|=2m∣R∣=2m and any minimum-cost perfect matching M∗M^*M∗ on RRR under DDD. Let ttt be a stable time and uuu a free request at ttt such that the terminal request of P∗=Pu∗(t)P^*=P^*_u(t)P∗=Pu∗​(t) has arrived by ttt, and let D∗=D(P∗∩M∗)D^*=D(P^*\cap M^*)D∗=D(P∗∩M∗). Then

D∗≥age⁡(u,t)andD∗≥age⁡(z,t)γ+1 for every vertex z of P∗,D^*\ge\operatorname{age}(u,t)\qquad\text{and}\qquad D^*\ge\frac{\operatorname{age}(z,t)}{\gamma+1}\ \text{for every vertex } z \text{ of } P^*,D∗≥age(u,t)andD∗≥γ+1age(z,t)​ for every vertex z of P∗,

where age⁡(v,t)=t−av\operatorname{age}(v,t)=t-a_vage(v,t)=t−av​.

These bounds make the Case 2 charge rates well defined and bound how long an edge of M∗M^*M∗ can be charged.

Differences from the source:

  • encoding: a finite request set R with |R| = 2m in any metric space, locations and arrival times a_v ≥ 0 that may coincide → the published MatchingDelays.Linear.Instance n X (labels 0..n−1 in nondecreasing arrival order, any MetricSpace X) with Even n, m = n/2; reason: every finite input can be relabeled in arrival order (simultaneous arrivals in any order); labels give the algorithm no future data, and repeated locations and arrival times are allowed
  • encoding: an arbitrary but fixed rule for ties among simultaneous events and among the choices of N_uv and v in Steps 1 and 2 → every TieRule, a View-and-history selector over the nonempty finite option sets; reason: the rule sees only received data and its own history; every statement quantifies over all such rules
  • encoding: a stable time t (no request arrives and no augmentation is performed at t) → 0 ≤ t, no arrival at t and no output pair with time t; reason: for t < 0 there is no free request, so the condition 0 ≤ t excludes only vacuous cases
  • encoding: the optimal path P_u(t), its terminal request and D = D(P* ∩ M*) → the vertex list optimalWalk from u, its last element, and the sum of TA distances over its edges in M*; reason: the walk traverses the component of M_t △ M* containing u
Preamble
import Definitions.Def_BipartiteVRM_Competitive_Supplement_Specifications

set_option autoImplicit false
Formal statement
namespace BipartiteVRM.Competitive.Supplement

open MatchingDelays.Linear (Instance Edge)

/-- Lemma 5.8, p. 18: both bounds, the second at every vertex of P*. -/
theorem lemma_5_8 {n : ℕ} {X : Type*} [MetricSpace X] (I : Instance n X) (hn : Even n)
    (γ : ℝ) (hγ : 1 < γ) (tie : TieRule) (Mstar : Matching) (hMstar : IsOptimal I Mstar)
    (t : ℝ) (ht : stable I γ tie t) (u : ℕ) (hu : u ∈ freeAt I γ tie t)
    (hterm : ∃ v, (optimalPath I γ tie Mstar t u).getLast? = some v ∧
      MatchingDelays.Linear.arrival I v ≤ t) :
    age I u t ≤ optimalLength I γ tie Mstar t u ∧
      ∀ z ∈ optimalPath I γ tie Mstar t u,
        age I z t / (γ + 1) ≤ optimalLength I γ tie Mstar t u := by sorry

end BipartiteVRM.Competitive.Supplement
Source
Tung-Wei Kuo, STOC 2027 submission #528 (October 2026), p. 18, Lemma 5.8

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