Stability in stochastic hypergraph matching II: weights, batch arrivals, and continuous time

Abstract

Many real-life systems can be found as examples of stochastic matching on hypergraphs, such as production lines or assemble-to-order systems. Two common features are the number of items required may vary between matchings, and there may intermediary items which exist as a combination of other items and not of external arrivals. Both of these phenomena can be modelled by considering the weighted variant of stochastic matching. In this work, we formalise the notion of stochastic weighted matching on hypergraphs. We also allow batch arrivals, meaning multiple items of multiple classes may arrive at the same time, and in particular, the arrivals can be correlated between classes. Unlike the classical setting where items arrive at discrete time $t\in \mathbb{N}$, we allow arrival processes to take place in continuous time $t\in {\mathbb{R}}_{\ge 0}$. We then extend the results from Nguyen and Bušić (2026) to overcome the intricacies brought up by this new setting. This allows us to derive necessary and sufficient criteria as direct generalisations of those in the unweighted setting, which depend only on the per-class arrival rates. As such, the correlation between classes bear no differences. The constructive proofs also give a maximally stable, periodic-review, size-based, arrival-rate agnostic policy.

42 pages. A gap in the proof of Lemma 4.2 was discovered in the previous version, which led to a change of NCOND-like conditions; the proof is also corrected to adapt to the batch arrivals. Continuous-time matching models are defined and analysed

Topics & keywords