Special Seminar in CMS and HSS
Mahsa is a fifth-year Ph.D. candidate in Computer Science at the University of Maryland, advised by Mohammad Taghi Hajiaghayi. During her Ph.D., Mahsa has spent a year as an intern at Google and Microsoft Research, and two semesters as a visiting student and Simons Institute for the theory of computing at UC Berkeley. Her primary research interest is in algorithmic mechanism design and algorithmic game theory. Particularly, the focus of her research is on designing market algorithms in the presence of uncertainty and strategic behavior. She is also interested in the design and analysis of big-data algorithms, especially in distributed and dynamic settings. Mahsa’s research is supported by the Ann G. Wylie Dissertation Fellowship and the 2020 Google Ph.D. Fellowship for Algorithms, Optimizations, and Markets.
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.