Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Theorem 3, p. 7 — Randomized-Batching with Depth-k Greedy is 1/d-competitive for Online-(k, d)-Max-Matching

Proved
HyperMatchDelay.Batching.theorem_3

by mikedeng1 · Oct 22, 2026 · Mathlib 0df444a (Lean v4.33.1)

batchingcompetitive-ratiohypergraph-matchingonline-algorithmsp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1ridesharing

Let H=(V,E,w)H = (V, E, w)H=(V,E,w) be a shareability hypergraph with parameters (n,d,k)(n, d, k)(n,d,k), d≥1d \ge 1d≥1, k≥1k \ge 1k≥1: vertices 1,…,n1, \dots, n1,…,n arrive one per time step, each hyperedge has diameter less than ddd, at most kkk vertices and non-negative weight. Run Randomized-Batching (Algorithm 1) with Depth-k Greedy (Algorithm 2) as the offline subroutine, where Greedy breaks weight ties in an arbitrary but fixed way. Draw the shift ZZZ uniformly from {0,…,d−1}\{0, \dots, d-1\}{0,…,d−1} and let MZM_ZMZ​ be the output. Then:

  1. for every shift zzz, MzM_zMz​ is a matching of EEE and every edge of MzM_zMz​ lies inside a single batch window {z+id,…,z+(i+1)d−1}\{z + id, \dots, z + (i+1)d - 1\}{z+id,…,z+(i+1)d−1}, so it can be committed online after all its vertices arrive and before any of them leaves;
  2. for every matching M~\widetilde MM of EEE,
EZ[w(MZ)]=1d∑z=0d−1w(Mz)  ≥  w(M~)d.\mathbb E_Z\big[w(M_Z)\big] = \frac1d \sum_{z=0}^{d-1} w(M_z) \;\ge\; \frac{w(\widetilde M)}{d}.EZ​[w(MZ​)]=d1​z=0∑d−1​w(Mz​)≥dw(M)​.

Taking M~\widetilde MM to be a maximum weight matching shows that the algorithm is 1/d1/d1/d-competitive for Online-(k, d)-Max-Matching, the best possible ratio for k≥3k \ge 3k≥3 by Theorem 1 of the paper, and it is achieved by a polynomial-time algorithm for fixed kkk.

Formalization Note Only the competitive-ratio clause of Theorem 3 is formalized; the running-time clause O(∣E∣k+1)O(|E|^{k+1})O(∣E∣k+1) is not. The comparison against every matching is equivalent to comparison against a maximum weight matching M∗M^*M∗. Ties in Greedy are an ordering oracle and the statement holds for every weight-sorted oracle. Hyperedges are assumed non-empty.

Preamble
import Mathlib
import Definitions.Def_HyperMatchDelay_Batching_Model
Formal statement
namespace HyperMatchDelay.Batching

/-- Theorem 3, p. 7 (competitive clause; proof Appendix B.3, pp. 17–20): Randomized-Batching
using Depth-k Greedy as a subroutine is `1/d`-competitive for Online-(k, d)-Max-Matching.
For every shift `z < d` the output `M_z` is a matching of `E` whose every edge lies inside one
window (online feasibility), and its expected weight over a uniform shift
`Z ∈ {0, …, d - 1}` is at least `w(M̃)/d` for every matching `M̃` of `E`. -/
theorem theorem_3 (n d k : ℕ) (hd : 1 ≤ d) (hk : 1 ≤ k) (E : Finset (Finset ℕ))
    (w : Finset ℕ → ℝ) (hE : IsShareability n d k E w)
    (σ : Finset (Finset ℕ) → List (Finset ℕ)) (hσ : IsSortedOrder w σ) :
    (∀ z < d, IsMatching E (randomizedBatching σ w n d k E z) ∧
      ∀ e ∈ randomizedBatching σ w n d k E z, ∃ i ∈ batchIndices n d, e ⊆ window n d z i) ∧
    ∀ Mt : Finset (Finset ℕ), IsMatching E Mt →
      weight w Mt / d ≤
        (1 / (d : ℝ)) * ∑ z ∈ Finset.range d,
          weight w (randomizedBatching σ w n d k E z) := by sorry

end HyperMatchDelay.Batching
Source
Pavone, Saberi, Schiffer & Tsao, Online Hypergraph Matching with Delays, arXiv:2009.12022v1, p. 7, Theorem 3 (proof Appendix B.3, pp. 17–20)
Human review
  • Endorsed by Shuze Chen · Oct 22, 2026

    Confirmed by the moderator at approval.

  • Endorsed by mikedeng1 · Oct 22, 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