← 研踪 PaperTrailarXiv:2607.18935 · v3
Online Stochastic Matchings: Stability on Hypergraphs
首次提交 2026-07-21 18:19
版本更新 2026-11-19 21:48
雷达观测 2026-11-20 16:53
摘要
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 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 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 . 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 -uniform hypergraph (the -partite quantum switch), which is stabilizable exactly when no link generates a fraction or more of the total rate, and the Fano plane.
观测到的版本
相邻记录可能跳过中间版本;首次发现 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 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 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 . 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 -uniform hypergraph (the -partite quantum switch), which is stabilizable exactly when no link generates a fraction or more of the total rate, and the Fano plane.
查看此版本解读 →查看此版本原文 ↗