Colloquium Details
Algorithms for Markets: Matching Under Uncertainty
Speaker: Mahsa Derakhshan, University of Maryland
Location: Online
Date: March 11, 2021, 10 a.m.
Host: Richard Cole
Synopsis:
Market algorithms influence many aspects of our lives, from organ exchange programs to the ads we see and the products we purchase. Modern market algorithms come with various challenges. This includes the inherent uncertainty in the data, the large volume of data to process, and the agents' strategic behavior. In this talk, I will present an overview of my research in this emerging area and focus mainly on matching markets in the presence of uncertainty.
The stochastic matching problem is a well-studied model of studying matchings under uncertainty and has applications in prominent matching markets such as the kidney exchange program, online labor markets, and online dating. In this problem, the goal is to find a large matching of a graph whose edges are uncertain. Particularly, we are only given the existence probability of each edge, but we need to perform costly queries to verify their existence. 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 (often time-consuming) interview between them. Prior work had identified 2/3-approximation as a barrier for this problem. In this talk, I will present my recent line of work on this problem where we break this barrier and prove that it is in fact possible to obtain a (1-ε)-approximation with only a constant number of queries per vertex.
Speaker Bio:
Mahsa is a fifth-year Ph.D. candidate in Computer Science at the University of Maryland, advised by MohammadTaghi 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 at Simons Institute for the theory of computing at UC Berkeley. Mahsa primarily uses her background in algorithmic game theory and the foundations of big data algorithms to design algorithms for modern markets, such as matching markets and online advertising markets. She has also worked on resource allocation problems in competitive environments with applications in the US presidential election and wildlife protection. Her research is supported by the Ann G. Wylie Dissertation Fellowship and the 2020 Google Ph.D. Fellowship for Algorithms, Optimizations, and Markets.