Stochastic Matching with Few Queries: New Algorithms and Tools

Soheil Behnezhad, Alireza Farhadi, MohammadTaghi Hajiaghayi, Nima Reyhani

TL;DR

This paper tackles the stochastic matching problem, where potential connections in a network (like donor-patient pairs) only exist with a certain probability, and testing them is expensive. The authors introduce a surprisingly simple non-adaptive algorithm that breaks the long-standing 0.5 approximation barrier for both weighted and unweighted graphs, representing a major theoretical leap for optimizing matching markets.

What Problem Does This Paper Address?

Imagine trying to match organ donors with patients (kidney exchange), or freelancers with employers (online labor markets). You have a list of potential matches (a graph), but you don't know if a match will actually work out until you conduct a time-consuming medical test or interview.

This is formalized as the stochastic matching problem. You are given a graph where each edge exists (is "realized") independently with a probability $p$. Because testing is slow and expensive, you are restricted to querying only a small number of edges per vertex. Furthermore, the algorithm must be non-adaptive—meaning you must choose all the edges you want to test simultaneously, rather than testing one, seeing the result, and then deciding what to test next.

Historically, it has been notoriously difficult to design non-adaptive algorithms that guarantee an expected matching size better than 50% (a 0.5 approximation) of the theoretical maximum, especially when the edges have different weights (values). Breaking this "half-approximation barrier" has been a major open question in theoretical computer science.

Methods

The authors propose an algorithm (Algorithm B) that is remarkably simple and natural, especially compared to prior state-of-the-art methods that relied on complex graph sparsification.

  1. The Algorithm: The algorithm simulates $R$ independent "parallel universes" (realizations) of the input graph based on the probability $p$. It calculates the maximum weighted matching in each of these simulated universes. It then takes the union of all the edges from these $R$ matchings, queries them all simultaneously in the real world, and outputs the best matching among the edges that actually exist.
  2. The Analytical Tools: While the algorithm is simple, proving that it works is highly complex. The authors introduce novel analytical procedures based on fractional matchings. They divide the edges into two buckets: "crucial" edges (highly likely to be in the optimal matching) and "non-crucial" edges. They then design mathematical procedures to construct large fractional matchings over the realized edges. By relying on classical graph theory (Edmonds' matching polytope), they prove that if a large, valid fractional matching exists, a correspondingly large actual (integral) matching must also exist.

Datasets

Not discussed in the paper. This is a purely theoretical algorithmic paper, so no empirical datasets or benchmarks were used. The results are proven mathematically.

Key Insights and Ideas

  • Simplicity Wins: Prior attempts to break the 0.5 barrier for unweighted graphs required extracting complex $b$-matchings. This paper proves that simply sampling independent realizations and taking their union is actually highly effective, provided you have the right mathematical tools to analyze it.
  • The Power of Fractional Matchings: The authors realized that directly proving the existence of a large integral matching in the queried set is too difficult. Instead, their "aha" moment was designing procedures that assign fractional values to realized edges without violating per-vertex budgets.
  • Dynamic Budgets for Weighted Graphs: To break the 0.5 barrier on weighted graphs, the authors found that static budget allocations fail. They introduced a "dynamic budget" procedure where a realized, high-weight crucial edge is allowed to "steal" fractional budget from adjacent non-crucial edges. This intricate balancing act is what finally pushed the weighted approximation factor past 0.5.

Key Results

The paper provides two massive theoretical improvements for non-adaptive stochastic matching, both requiring only $O(\log(1/p)/p)$ queries per vertex:

  • Unweighted Graphs: The algorithm achieves an expected approximation factor of roughly 0.6568 ($4\sqrt{2} - 5$). This shatters the previous state-of-the-art, which barely scraped by at 0.5001.
  • Weighted Graphs: The algorithm achieves an expected approximation factor of 0.501. While seemingly a small margin, this is the first algorithm ever to break the 0.5 approximation barrier for weighted graphs in a non-adaptive setting.

Limitations and Future Work

  • Tightness of the Analysis: The authors prove that their specific fractional matching analysis tool cannot yield an approximation better than $\approx 0.6568$ for unweighted graphs. To prove the algorithm performs even better, entirely new analytical techniques will be required.
  • Weighted Bound is Small: While breaking the 0.5 barrier for weighted graphs is a major theoretical milestone, the actual improvement (0.501) is marginal. Future work will likely focus on pushing this ratio higher.
  • Purely Theoretical: The paper focuses strictly on worst-case theoretical bounds. It does not explore how this algorithm performs empirically on real-world datasets (like actual kidney exchange compatibility graphs), where it would likely perform much better than the theoretical lower bounds suggest.

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},
}

Loading related content...

Figure