Lemma 6: lowering moves the match of in period weakly earlier
ProvedReusableMatching.lemma_6competitive-analysisonline-matchingp2o-gran-per-chapterp2o-plan-paperp2o-v1primal-dualreusable-resources
Let an OBMRR instance and be given, fix an edge and the seeds , and fix . Let be such that, for , resource is matched to an arrival of period . Then for every , resource is matched, in the run with seed , to an arrival of period that is or precedes it.
This monotonicity in 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
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.