Stability in stochastic hypergraph matching I: necessary and sufficient criteria
Abstract
Stochastic matching on hypergraphs is an important topic for its versatility in capturing real-life systems, from living donor transplant to ride-hailing. Nevertheless, finding necessary and sufficient criteria for stability is a long-standing problem. One of the key difficulties is the fact that greedy policies, whilst maximally stable for stochastic matching on graphs, no longer achieve maximal stability region on hypergraphs. So far, no alternative families of policies with similar properties have been known. In this work, we introduce online assignment policies, in which each item is assigned to a matching hyperedge type upon arrival. We show that this is a good generalisation to greedy policies, by proving that they are maximally stable. Their natural amenability to analysis allow us to derive several necessary and sufficient criteria for stability, which generalise the known criteria for graphs. Furthermore, the constructive proof gives a maximally stable arrival-rate agnostic policy.
Related
- Stability in stochastic hypergraph matching II: weights, batch arrivals, and continuous time
- Stability in stochastic hypergraph matching III: general reneging
- Necessary and sufficient conditions for optimal control of coupled forward-backward stochastic control systems driven by G-Brownian motion
- Necessary and Sufficient Conditions for Adaptive Stabilizability of Continuous-Time Markov Jump Linear Stochastic Systems
- Necessary and sufficient conditions for the martingale property of stochastic exponentials driven by multi-dimensional diffusions
BibTeX
@misc{nguyen2026stability,
title = {{Stability in stochastic hypergraph matching I: necessary and sufficient criteria}},
author = {Doan Dai Nguyen and Ana Bušić},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2607.23778},
eprint = {2607.23778},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2607.23778},
}
RIS
TY - UNPB
TI - Stability in stochastic hypergraph matching I: necessary and sufficient criteria
AU - Doan Dai Nguyen
AU - Ana Bušić
PY - 2026
DA - 2026/09/30
PB - arXiv
DO - 10.48550/arxiv.2607.23778
UR - https://arxiv.org/abs/2607.23778
AB - Stochastic matching on hypergraphs is an important topic for its versatility in capturing real-life systems, from living donor transplant to ride-hailing. Nevertheless, finding necessary and sufficient criteria for stability is a long-standing problem. One of the key difficulties is the fact that greedy policies, whilst maximally stable for stochastic matching on graphs, no longer achieve maximal stability region on hypergraphs. So far, no alternative families of policies with similar properties have been known. In this work, we introduce online assignment policies, in which each item is assigned to a matching hyperedge type upon arrival. We show that this is a good generalisation to greedy policies, by proving that they are maximally stable. Their natural amenability to analysis allow us to derive several necessary and sufficient criteria for stability, which generalise the known criteria for graphs. Furthermore, the constructive proof gives a maximally stable arrival-rate agnostic policy.
ER -