AI & ML
Online Stochastic Matchings: Stability on Hypergraphs
arXiv cs.NI0 views
arXiv:2607.18935v3 Announce Type: replace Abstract: In stochastic dynamic matching, items of several classes arrive at rates $\lambda$ 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 $A$ 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\mu = \lambda$ admits a nonnegative solution whose support induces a surjective submatrix. Equivalently, $\lambda$ 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 $\epsilon$ of it force mean queues of order at least $1/\epsilon$. 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 $k$-uniform hypergraph (the $k$-partite quantum switch), which is stabilizable exactly when no link generates a fraction $1/k$ or more of the total rate, and the Fano plane.
Source:https://arxiv.org/abs/2607.18935PreviousxAppGen: LLM-driven Natural Language Programming for Agile xApp DevelopmentNextCommJEPA: When Predictive Representation Learning Meets Wireless Intelligence
Related posts
Trying to get our Arms around AI efficiency
0Stack Overflow Blog
Why an Embedded Game Fails on Some Phones, and How to Debug It
0dev.to
Microsoft 365 vs Office 2024: The Break-Even Math
0dev.to
Master AI Evals: Build Reliable, Scalable Model Evaluation Pipelines
0dev.to
What to give someone who misses a place
0dev.to
Google is pushing OEMs against GrapheneOS and bootloader unlocking
0Hacker News