Abstract
Motivated by its applications in kidney exchange, online labor markets (such as Upwork, Freelancer, etc.), and other matching markets, we consider the following stochastic matching problem. A graph G = (V,E) along with a parameter p ∈ (0,1) is given where 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 of the maximum realized matching in H approximates the size of the maximum realized matching in G. This model of stochastic matching has attracted significant attention over the past few years. In this talk, we overview some recent progress made on this problem and discuss the main open problems of the area.