Original title: Stability in stochastic hypergraph matching III: general reneging
Doan Dai Nguyen, Ana Bušić · September 2026
Many matching systems deal with waiting items that can vanish before pairing up. Patients pass away waiting for organs, riders cancel trips, and factory parts degrade. Researchers call this leaving process reneging. The authors studied this by modeling groups of items arriving in discrete time batches and pairing up across multiple groups at once, allowing fractional amounts. In simpler models without reneging, system stability depends only on average arrival rates. Here, the researchers found that stability changes based on the exact way items leave. They uncovered a new stabilizing mechanism unique to this setup, which does not exist in standard graph models or systems without reneging. Combined with an existing balancing mechanism, this gave them a necessary and sufficient rule to tell if a system stays stable. Finally, they designed MaxWeight-style scheduling rules that achieve maximum stability when a specific setting, epsilon, is small enough.
You are a cashier at a busy coffee shop. Normally customers wait in line and are eventually served if you keep up with orders. But some customers walk away if the line is too long, and the chance they walk away varies with their drink order and how many people are waiting. In this paper, the matching system faces items (like customers) that may abandon (renege) before being matched, and stability depends on exactly how and when they abandon—unlike systems where no one leaves.
In organ transplants, ride-hailing, and manufacturing, agents may leave before being matched. Ignoring this reneging can make stability predictions dangerously wrong. This paper gives the first stability criterion for such systems and a matching policy that works despite abandonment, enabling more reliable market design.
The abstract notes there is no effective bound for ε in the MaxWeight policy, and verifying stability in general is a hard problem. The model assumes discrete time, which may not reflect all real-world settings, and fractional weights can make individual item tracking impossible.
Ask anything about this paper. Answers come from its abstract, and say so when the abstract doesn't cover your question.
Stability in stochastic hypergraph matching III: general reneging — Doan Dai Nguyen, Ana Bušić
Abstract licence: CC0
Explanation generated by Synthesis from the abstract — it is not the original paper. This is a preprint, so it hasn't necessarily been peer reviewed.