Online Stochastic Matchings: Stability on Hypergraphs

Abstract

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, $\hat{I}»$) is stabilizable if and only if the conservation equation A$\hat{I}¼$ = $\hat{I}»$ admits a nonnegative solution whose support induces a surjective submatrix, equivalently $\hat{I}»$ 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 $\hat{I}»$-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.