2026/07/21 by Fabien Mathieu
Computer Science · #cs.NI
arxiv created 2026/07/29 · arxiv updated 2026/07/30
We study stochastic dynamic matching on hypergraphs: items of finitely many classes arrive over time and are removed in multisets by activating hyperedges. We characterize stabilizability, the existence of a matching policy under which the queue process is positive recurrent, in terms of the arrival rates and the incidence matrix alone: (G, λ) is stabilizable if and only if the conservation equation Aμ = λ admits a nonnegative solution whose support induces a surjective submatrix, equivalently λ lies in the interior of the cone generated by the hyperedges. This extends a characterization known for simple graphs (non-bipartiteness together with the independent-set inequalities) to arbitrary hyperedges, allowing multiplicities and mono-edges, and, unlike the constant-regret theory, needs no general-position assumption. Sufficiency is constructive: a single λ-oblivious policy, Virtual-Queue Match-the-Longest (VQML), a rewardless variant of the Extended Greedy Primal-Dual policy of Nazari and Stolyar, stabilizes every stabilizable instance and is therefore maximally stable. The sufficiency proof requires the positive recurrence of the signed virtual queue underlying VQML; previous analyses invoke this property but, to our knowledge, do not prove it, and supplying it is a second contribution.