Online Stochastic Matchings: Stability on Hypergraphs
TL;DR
Stochastic dynamic matching on hypergraphs is studied: items of finitely many classes arrive over time and are removed in multisets by activating hyperedges, and a single $\lambda$-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.
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, $\lambda$) is stabilizable if and only if the conservation equation A$\mu$ = $\lambda$ admits a nonnegative solution whose support induces a surjective submatrix, equivalently $\lambda$ 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 $\lambda$-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.