Abstract
We consider the stochastic matching problem on both weighted and unweighted graphs: given a graph $G(V, E)$ and a parameter $p \in (0, 1)$, where each edge is realized independently with probability $p$, the goal is to select a degree-bounded subgraph $H$ such that the expected size/weight of the maximum realized matching in $H$ is close to that of $G$. We analyze a simple, non-adaptive algorithm that achieves a $0.6568$ approximation for unweighted graphs and a $0.501$ approximation for weighted graphs, querying only $O(\frac{\log (1/p)}{p})$ edges per vertex. This work breaks the long-standing $0.5$ approximation barrier for both settings using novel analytical tools based on fractional matchings.
Introduction
The stochastic matching problem is a fundamental challenge in optimizing modern matching markets, such as kidney exchanges or online labor platforms. In these scenarios, potential matches (edges in a graph) are not guaranteed to succeed; they are realized independently with a known probability $p$. Determining the success of a match requires a costly or time-consuming "query" (e.g., a medical test or an interview). The goal is to select a small subset of edges to query—where each vertex has a limited query budget—such that the expected size or weight of the maximum matching among the realized edges is as large as possible.
The Non-Adaptive Barrier
A critical constraint in many applications is that queries must be non-adaptive: all edges to be tested must be chosen simultaneously before any results are known. Historically, achieving an approximation factor better than 0.5 (50% of the maximum possible matching) has been a significant theoretical hurdle. While recent work managed to slightly exceed this for unweighted graphs (reaching 0.5001), the 0.5 barrier remained unbroken for weighted graphs until now.
Algorithm B: Sampling Parallel Universes
This paper introduces a surprisingly simple non-adaptive algorithm, referred to as Algorithm B. Unlike previous approaches that relied on complex graph sparsification or $b$-matchings, Algorithm B operates through a sampling-based approach:
- Simulate Realizations: The algorithm generates $R$ independent "parallel universes" (realizations) of the input graph $G$ based on the probability $p$.
- Compute Matchings: In each simulated universe, it finds the maximum weighted matching.
- Query the Union: It takes the union of all edges found in these $R$ matchings and queries them simultaneously in the actual graph.
- Output: The final output is the maximum matching among the edges that are successfully realized.
Analytical Tools: Fractional Matchings
The primary contribution of this work lies in the novel analytical framework used to prove the algorithm's performance. The authors shift the focus from directly finding integral matchings to constructing heavy fractional matchings.
The analysis categorizes edges into "crucial" (highly likely to be in an optimal matching) and "non-crucial" buckets. By designing procedures that assign fractional values to realized edges without exceeding per-vertex budgets, the authors leverage Edmonds' matching polytope theorem: if a large valid fractional matching exists, a large integral matching must also exist. For weighted graphs, they introduce a "dynamic budget" mechanism where high-weight crucial edges can "steal" fractional capacity from adjacent non-crucial edges, a key innovation for breaking the 0.5 barrier.
Key Results
The proposed algorithm achieves major theoretical leaps while maintaining a low query complexity of $O(\frac{\log (1/p)}{p})$ edges per vertex.
- Unweighted Graphs: The algorithm provides a 0.6568 ($\approx 4\sqrt{2}-5$) approximation, a massive improvement over the previous state-of-the-art of 0.5001.
- Weighted Graphs: The algorithm achieves a 0.501 approximation. While the numerical gain is small, it represents the first time the 0.5 barrier has been broken for weighted stochastic matching in the non-adaptive setting.
Conclusion
By demonstrating that a simple sampling-based algorithm can significantly outperform complex predecessors, this work reshapes the understanding of non-adaptive stochastic matching. The introduction of fractional matching construction as an analytical tool provides a new path for future improvements in both weighted and unweighted settings. While the current weighted improvement is marginal, the breakthrough suggests that the 0.5 barrier is not an inherent limit of non-adaptive algorithms.
Summary updated