Stochastic matching achieves near optimal size with low degree selection
Stochastic Matching with Polynomial Degree
Data Structures and Algorithms
Summary
This paper studies a problem where you have a network of connections, but each connection might work or not with some chance. The goal is to choose a smaller set of connections ahead of time so that even after some fail, you still keep most of the best possible matches, while ensuring no node has too many connections. The authors prove that it is always possible to do this with a surprisingly low maximum number of connections per node, solving a recent open question. Their proof uses a new way of rearranging matchings to make the problem easier to control.
What this means in practice
- •For kidney exchange planners: Design low-degree compatibility graphs that maximize expected successful kidney matches despite uncertain availability.
- •For online dating platform engineers: Create efficient user interaction networks that preserve high matching rates while limiting overload on individual users.
A theory result. No direct application yet.
Authors
Soheil Behnezhad
Abstract
We study the stochastic matching problem, where a graph $G$ is known in advance, but each edge survives independently with probability $p$. The goal is to select a subgraph $H$ of small maximum degree before seeing the surviving edges, while preserving a $(1-ε)$ fraction of the expected maximum matching size. This problem has received significant attention due to its numerous applications in kidney exchange, labor markets, and online dating. In this paper, we show there is always a subgraph $H \subseteq G$ achieving a $(1-ε)$-approximation while having a maximum degree of at most $O\left(\frac{\log(1/ε)}{ε^4} \cdot \frac{1}{p}\right).$ This resolves a major conjecture of the literature, first stated by [BDH, STOC'20], that $poly(\frac{1}{εp})$ degrees suffice. The best previous bound was $(1/p)^{\exp((1/ε)\log(1/ε))}$ by [ABGR, STOC'25]. The key to this result is a lemma of independent interest that any distribution over the matchings of a stochastic graph can be transformed to another distribution which matches each vertex with exactly the same probability, but exhibits extremely low total pairwise correlation.