Stochastic Matching with Few Queries: New Algorithms and Tools

Soheil Behnezhad, Alireza Farhadi, MohammadTaghi Hajiaghayi, Nima Reyhani

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:

  1. Simulate Realizations: The algorithm generates $R$ independent "parallel universes" (realizations) of the input graph $G$ based on the probability $p$.
  2. Compute Matchings: In each simulated universe, it finds the maximum weighted matching.
  3. Query the Union: It takes the union of all edges found in these $R$ matchings and queries them simultaneously in the actual graph.
  4. Output: The final output is the maximum matching among the edges that are successfully realized.
Illustrations of graph structures (a, b, c) used to analyze the performance of the non-adaptive matching algorithm.

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.
Comparison of approximation factors and query complexity between this work and prior state-of-the-art algorithms.

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

Abstract

We consider the following stochastic matching problem on both weighted and unweighted graphs: A graph $G(V, E)$ along with a parameter $p \in (0, 1)$ is given in the input. Each edge of $G$ is realized independently with probability $p$. The goal is to select a degree bounded (dependent only on $p$) subgraph $H$ of $G$ such that the expected size/weight of maximum realized matching of $H$ is close to that of $G$. This model of stochastic matching has attracted significant attention over the recent years due to its various applications. The most fundamental open question is the best approximation factor achievable for such algorithms that, in the literature, are referred to as non-adaptive algorithms. Prior work has identified breaking (near) half-approximation as a barrier for both weighted and unweighted graphs. Our main results are as follows: -- We analyze a simple and clean algorithm and show that for unweighted graphs, it finds an (almost) $4\sqrt{2}-5$ ($\approx 0.6568$) approximation by querying $O(\frac{\log (1/p)}{p})$ edges per vertex. This improves over the state-of-the-art $0.5001$ approximate algorithm of Assadi et al. [EC'17]. -- We show that the same algorithm achieves a $0.501$ approximation for weighted graphs by querying $O(\frac{\log (1/p)}{p})$ edges per vertex. This is the first algorithm to break $0.5$ approximation barrier for weighted graphs. It also improves the per-vertex queries of the state-of-the-art by Yamaguchi and Maehara [SODA'18] and Behnezhad and Reyhani [EC'18]. Our algorithms are fundamentally different from prior works, yet are very simple and natural. For the analysis, we introduce a number of procedures that construct heavy fractional matchings. We consider the new algorithms and our analytical tools to be the main contributions of this paper.
BibTeX
@inproceedings{behnezhad2019stochastic,
  author = {Soheil Behnezhad and Alireza Farhadi and MohammadTaghi Hajiaghayi and Nima Reyhani},
  title = {{Stochastic Matching with Few Queries: New Algorithms and Tools}},
  booktitle = {SODA},
  year = {2019},
  url = {https://openreview.net/forum?id=7EpAaMSBV_B},
}
Figure