Stability in stochastic hypergraph matching III: general reneging
Abstract
In many real-life matching problems, waiting agents might abandon before being matched, such as patients deceasing before receiving organs, passengers/drivers cancelling ride requests, or raw materials/intermediary products degrading in production lines. This poses the need for incorporating reneging in stochastic matching models. In this work, we consider matching models on hypergraphs with batch arrivals and general-weight matchings. Since our model allows fractional weights, we may not be able to talk about individual items, and thus reneging is not required to be independent between items of the same class. For the simplicity sake's, we assume items arrive at discrete time. We show that stability depends on the exact nature of reneging, in stark contrast with the non-reneging case where it depends on the arrivals only through the arrival rates. To our best knowledge, this is the first such sensitivity result in stochastic matching. We uncover a new stabilising mechanism which exists neither in the non-reneging case nor in the graph case, which explains why incorporating reneging in stochastic matching is not straightforward. Together with balancing mechanism as hinted in the online assignment framework for the non-reneging case, it gives a criterion necessary and sufficient for stability. Finally, whilst verifying stability is a hard problem, we give a family of MaxWeight-type policies parameterised by ε > 0, which are maximally stabilising for all ε sufficiently small. Unfortunately there is no effective bound for ε, but we show how to adjust its value during implementation.
Related
- Stability in stochastic hypergraph matching I: necessary and sufficient criteria
- Stability in stochastic hypergraph matching II: weights, batch arrivals, and continuous time
- Fluid and Diffusion Approximation of a Multiclass Proportional Processor Sharing Queue with Reneging and General Distributions
- The terminal leave in random greedy hypergraph matching
- Hypergraph Turán Problem of the Generalized Triangle with Bounded Matching Number
BibTeX
@misc{nguyen2026stability,
title = {{Stability in stochastic hypergraph matching III: general reneging}},
author = {Doan Dai Nguyen and Ana Bušić},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.15532},
eprint = {2609.15532},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.15532},
}
RIS
TY - UNPB
TI - Stability in stochastic hypergraph matching III: general reneging
AU - Doan Dai Nguyen
AU - Ana Bušić
PY - 2026
DA - 2026/09/14
PB - arXiv
DO - 10.48550/arxiv.2609.15532
UR - https://arxiv.org/abs/2609.15532
AB - In many real-life matching problems, waiting agents might abandon before being matched, such as patients deceasing before receiving organs, passengers/drivers cancelling ride requests, or raw materials/intermediary products degrading in production lines. This poses the need for incorporating reneging in stochastic matching models. In this work, we consider matching models on hypergraphs with batch arrivals and general-weight matchings. Since our model allows fractional weights, we may not be able to talk about individual items, and thus reneging is not required to be independent between items of the same class. For the simplicity sake's, we assume items arrive at discrete time. We show that stability depends on the exact nature of reneging, in stark contrast with the non-reneging case where it depends on the arrivals only through the arrival rates. To our best knowledge, this is the first such sensitivity result in stochastic matching. We uncover a new stabilising mechanism which exists neither in the non-reneging case nor in the graph case, which explains why incorporating reneging in stochastic matching is not straightforward. Together with balancing mechanism as hinted in the online assignment framework for the non-reneging case, it gives a criterion necessary and sufficient for stability. Finally, whilst verifying stability is a hard problem, we give a family of MaxWeight-type policies parameterised by ε > 0, which are maximally stabilising for all ε sufficiently small. Unfortunately there is no effective bound for ε, but we show how to adjust its value during implementation.
ER -