Special Seminar in CMS and HSS

The presence of uncertainty is a common challenge when it comes to designing algorithms for matching markets such as organ exchange markets, labor markets, and dating platforms. This uncertainty is often due to the stochastic nature of the data or restrictions that result in limited access to information. In this talk, I will discuss my works on the stochastic matching problem. In this problem, the goal is to find a large matching of a graph whose edges are uncertain. Particularly, we only know the existence probability of each edge but to verify their existence, we need to perform costly queries.  For instance, in labor markets, the existence of an edge between a freelancer and an employer represents their compatibility to work with one another, and a query translates to an interview between them which is often time-consuming. I will present an algorithm we recently developed, showing that despite the uncertainty in the graph, one can find a nearly maximum size matching (weighted and unweighted) by conducting only a constant number of queries per vertex. This significantly improves upon prior algorithms which could only achieve 2/3-approximation for unweighted graphs and only slightly better than 0.5-approximation for weighted graphs.