Theorem C.8 — Deterministic -competitive k-way matching (sum costs)
OpenMatchingDelays.Linear.Supplement.kway_competitive_ratiok-way-matchingmatchingonline-algorithmsp2o-batch-stoc27sp2o-gran-per-chapterp2o-plan-paperp2o-v1
Fix an integer , known to the algorithm. Consider k-way matching with delays and all-pairs sum costs: requests with at points of an arbitrary metric space arrive at times , and forming a group of requests at time costs , where . Let be the offline optimum over partitions into -groups with feasible formation times. Then:
- for every such , every metric space and every input, every execution of the Delayed Best-Effort Matching algorithm of §C.3 (, any tie-breaking) terminates and outputs a partition into -groups with feasible formation times, with
- the deterministic policy
kPolicy k(the §C.3 rule with lexicographic tie-breaking) has an execution on every such input; - that policy needs no advance knowledge of or the metric space: two of its executions on inputs that agree on everything revealed up to time have equal observations at time , even across different sizes and ambient metric spaces.
Logarithms are natural, and inputs with are included. This is the formal version of Theorem 1.3 (printed p. 2 / PDF p. 3).
Differences from the source:
- encoding: requests labeled [n] in continuous real time → arrival-ranked Fin n input, batched simultaneous arrivals, and natural-number microsteps with exact continuous interpolation; time-indexed objects are read from the completed event state at t; reason: relabeling preserves all inputs and ties; microsteps do not discretize time, and they order arrivals, merges and matches at one instant exactly as the source does
- encoding: "deterministic and O(k log n)-competitive … More precisely, alg ≤ 96(k−1)/ln 2 (1+3 ln n) opt" → every execution (any tie-breaking) terminates with a feasible timed k-partition satisfying the explicit bound; the deterministic observation-only policy has executions and is causal across sizes and metric spaces; reason: makes explicit what "deterministic" and "no advance knowledge" mean, as in the published goal
Preamble
import Mathlib import Definitions.Def_MatchingDelays_Linear_Supplement_KWay set_option autoImplicit false open scoped BigOperators open Classical noncomputable section
Formal statement
namespace MatchingDelays.Linear.Supplement
/-- Theorem C.8 (printed 32 / PDF 33), formal version of Theorem 1.3 (printed 2 / PDF 3):
every execution terminates with a timed partition into k-groups of sum cost at most
`96(k−1)/ln 2 · (1 + 3 ln n)` times the offline optimum; the deterministic observation-only
policy `kPolicy k` has executions on every input and is causal across inputs of different
sizes and metric spaces. -/
theorem kway_competitive_ratio (k : ℕ) :
(∀ (n : ℕ) (X : Type*) [MetricSpace X] (I : Instance n X), ValidKSize k n →
∀ R : KRun, IsKExecution k I R →
KTerminated R ∧ KPartitionOutput k I R ∧
kAlgCost I R ≤
(96 * ((k : ℝ) - 1) / Real.log 2) * (1 + 3 * Real.log (n : ℝ)) * kOfflineOpt k I) ∧
(∀ (n : ℕ) (X : Type*) [MetricSpace X] (I : Instance n X), ValidKSize k n →
∃ R : KRun, IsKExecution k I R ∧ KFollows k I (kPolicy k) R) ∧
(∀ (n m : ℕ) (X Y : Type*) [MetricSpace X] [MetricSpace Y]
(I : Instance n X) (J : Instance m Y), ValidKSize k n → ValidKSize k m →
∀ (R S : KRun), IsKExecution k I R → IsKExecution k J S →
KFollows k I (kPolicy k) R → KFollows k J (kPolicy k) S →
∀ t : ℝ, 0 ≤ t → SameInputThrough I J t →
kObservation I (kStateAt k R t) = kObservation J (kStateAt k S t)) := by sorry
end MatchingDelays.Linear.Supplement
Source
Ahmadian, Chawla, Kumar, Purohit, and Zhang, A General Framework for Matching with Delays, STOC 2027 submission #482 (October 2026), Theorem C.8, printed p.32 / PDF p.33. SHA-256 20a2fed026bd39130a6aff1891feff42709817c1c43d85d5a879a4935a1646be. https://github.com/sigact-stoc/stoc2027/releases/download/papers-1/482.pdf