Stochastic Matching with Few Queries: New Algorithms and Tools

Authors:
  • SBSoheil Behnezhad
    Soheil Behnezhad
  • AFAlireza Farhadi
    Alireza Farhadi
  • MHMohammadTaghi Hajiaghayi
    MohammadTaghi Hajiaghayi
  • NRNima Reyhani
    Nima Reyhani

Abstract
We consider the following stochastic matching problem on both weighted and unweighted graphs: A graph G(V, E) along with a parameter p ∊ (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 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 in kidney exchange, online labor markets, and other matching markets. 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: Interestingly, prior results were all based on similar algorithms and differed only in the analysis. Our algorithms are fundamentally different, yet 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.