跳到正文
研踪PaperTrail
← 研踪 PaperTrail

arXiv:2607.18935 · v3

Online Stochastic Matchings: Stability on Hypergraphs

首次提交 2026-07-21 18:19
版本更新 2026-11-19 21:48
雷达观测 2026-11-20 16:53
arXiv ↗PDF ↗

摘要

In stochastic dynamic matching, items of several classes arrive at rates λλ and leave in compatible groups. When groups may exceed two items, as in quantum switches or organ exchange, compatibility is described by the incidence matrix AA of a hypergraph, whose entries count how many items of each class a group consumes (single-class hyperedges can model discards). We call a system stabilizable if some matching policy keeps large queues rare in the long run, and show that this holds if and only if the conservation equation Aμ=λAμ= λ admits a nonnegative solution whose support induces a surjective submatrix. Equivalently, λλ lies in the interior of the cone generated by the hyperedges. The condition is necessary for all policies, including idling and clairvoyant ones. It is sufficient through one explicit policy: the rewardless counterpart of the Extended Greedy Primal--Dual policy of Nazari and Stolyar (2019) stabilizes every stabilizable system without knowledge of the rates, and its mean queue length is explicitly bounded. Approaching a solution whose support is not surjective has a cost, under every policy: matching rates within εε of it force mean queues of order at least 1/ε1/ε. On simple graphs, some greedy policies stabilize every stabilizable system. On a small hypergraph with a single hyperedge of size three, every greedy policy is unstable on an open set of stabilizable rates. This shows that no greedy policy, nor any family of greedy policies, can approach maximal stability on hypergraphs: idling is necessary. We also settle two cases explicitly: the complete kk-uniform hypergraph (the kk-partite quantum switch), which is stabilizable exactly when no link generates a fraction 1/k1/k or more of the total rate, and the Fano plane.

AI 论文解读

基于摘要 · 非全文审阅

此版本尚未生成 AI 解读。解读由后台任务生成并按论文版本保存,登录后共享已有结果。

版本差异

本站首次收录为 v3,暂无更早版本可对照。

观测到的版本

相邻记录可能跳过中间版本;首次发现 v2 及以上也会标为版本更新。

v3 · 2026-11-19 21:48 · 最新观测版本

Online Stochastic Matchings: Stability on Hypergraphs

In stochastic dynamic matching, items of several classes arrive at rates λλ and leave in compatible groups. When groups may exceed two items, as in quantum switches or organ exchange, compatibility is described by the incidence matrix AA of a hypergraph, whose entries count how many items of each class a group consumes (single-class hyperedges can model discards). We call a system stabilizable if some matching policy keeps large queues rare in the long run, and show that this holds if and only if the conservation equation Aμ=λAμ= λ admits a nonnegative solution whose support induces a surjective submatrix. Equivalently, λλ lies in the interior of the cone generated by the hyperedges. The condition is necessary for all policies, including idling and clairvoyant ones. It is sufficient through one explicit policy: the rewardless counterpart of the Extended Greedy Primal--Dual policy of Nazari and Stolyar (2019) stabilizes every stabilizable system without knowledge of the rates, and its mean queue length is explicitly bounded. Approaching a solution whose support is not surjective has a cost, under every policy: matching rates within εε of it force mean queues of order at least 1/ε1/ε. On simple graphs, some greedy policies stabilize every stabilizable system. On a small hypergraph with a single hyperedge of size three, every greedy policy is unstable on an open set of stabilizable rates. This shows that no greedy policy, nor any family of greedy policies, can approach maximal stability on hypergraphs: idling is necessary. We also settle two cases explicitly: the complete kk-uniform hypergraph (the kk-partite quantum switch), which is stabilizable exactly when no link generates a fraction 1/k1/k or more of the total rate, and the Fano plane.

查看此版本解读 →查看此版本原文 ↗