Stability in stochastic hypergraph matching I: necessary and sufficient criteria

Abstract

Stochastic matching on hypergraphs is an important topic for its versatility in capturing real-life systems, from living donor transplant to ride-hailing. Nevertheless, finding necessary and sufficient criteria for stability is a long-standing problem. One of the key difficulties is the fact that greedy policies, whilst maximally stable for stochastic matching on graphs, no longer achieve maximal stability region on hypergraphs. So far, no alternative families of policies with similar properties have been known. In this work, we introduce online assignment policies, in which each item is assigned to a matching hyperedge type upon arrival. We show that this is a good generalisation to greedy policies, by proving that they are maximally stable. Their natural amenability to analysis allow us to derive several necessary and sufficient criteria for stability, which generalise the known criteria for graphs. Furthermore, the constructive proof gives a maximally stable arrival-rate agnostic policy.