<div dir="ltr"><div dir="ltr"><div class="gmail_default" style="font-size:small"><div class="gmail_default"><p style="font-variant-numeric:normal;font-variant-east-asian:normal;font-stretch:normal;line-height:normal;margin:0px"><font face="arial, sans-serif"><font style="vertical-align:inherit"><font style="vertical-align:inherit"><b>When:</b> </font></font><font style="vertical-align:inherit"><font style="vertical-align:inherit"> Wednesday, February 3rd at<b> 11:10 am CT</b></font></font><br></font></p><p class="MsoNormal" style="margin:0in 0in 0.0001pt;line-height:normal;background-image:initial;background-position:initial;background-size:initial;background-repeat:initial;background-origin:initial;background-clip:initial"><font face="arial, sans-serif"> </font></p><p class="MsoNormal" style="margin:0in 0in 0.0001pt;line-height:normal;background-image:initial;background-position:initial;background-size:initial;background-repeat:initial;background-origin:initial;background-clip:initial"><font face="arial, sans-serif"><font style="vertical-align:inherit"><font style="vertical-align:inherit"><b>Where:</b> </font></font></font><font color="#000000" style="font-family:arial,sans-serif">Zoom Virtual Talk (</font><b><span style="line-height:13.91px;color:blue"><font face="arial, sans-serif" style="color:rgb(5,99,193)"><a href="https://uchicagogroup.zoom.us/webinar/register/WN_8sgotwgtTBCOOzN-okLDtA" style="color:rgb(5,99,193)" target="_blank"><i>register for talk here</i></a></font></span></b><span style="font-family:arial,sans-serif;color:rgb(0,0,0)">)</span></p><p class="MsoNormal" style="margin:0in 0in 0.0001pt;line-height:normal;background-image:initial;background-position:initial;background-size:initial;background-repeat:initial;background-origin:initial;background-clip:initial"><font face="arial, sans-serif"> </font></p><p class="MsoNormal" style="margin:0in 0in 0.0001pt;line-height:normal;background-image:initial;background-position:initial;background-size:initial;background-repeat:initial;background-origin:initial;background-clip:initial"><font face="arial, sans-serif"><font style="vertical-align:inherit"><font style="vertical-align:inherit"><b>Who: </b> </font></font></font><span style="color:rgb(60,64,67);letter-spacing:0.2px"><font face="arial, sans-serif">Mahsa Derakhshan, University of Maryland</font></span></p><br></div><div class="gmail_default"><p dir="ltr" style="color:rgb(0,0,0);line-height:1.9872;margin-top:0pt;margin-bottom:0pt"><span style="font-variant-east-asian:normal;vertical-align:baseline;white-space:pre-wrap"><font face="arial, sans-serif"><b>Title: </b>Algorithms for Markets: Matching and Pricing </font></span></p><p dir="ltr" style="color:rgb(0,0,0);line-height:1.9872;margin-top:0pt;margin-bottom:0pt"><b style="color:rgb(34,34,34)"><br></b></p><b>Abstract:</b> Modern market algorithms have transformed in crucial ways due to the presence of uncertainty, strategic behavior, and the huge volume of data to process. This is the case both in markets where money plays a role (monetary markets,) such as auctions, and those without money (non-monetary markets,) such as matching markets. In this talk, I will discuss my works on some of the prominent examples of these markets such as stochastic matchings and pricing mechanisms for auctions.</div><div class="gmail_default"><br></div><div class="gmail_default">The main focus of the talk will be on the stochastic matching problem, which has applications in kidney exchange, online labor markets, and dating apps among others. 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 its 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 and expensive. I 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.<br><br><b>Bio:</b> Mahsa is a fifth-year Ph.D. candidate in Computer Science at the University of Maryland, advised by MohammdTaghi 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 main area of research is algorithmic mechanism design with a special focus on designing models and algorithms for online platforms such as online advertising markets, online matching markets, and online retail markets. She is also interested in the design and analysis of big-data algorithms, particularly 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.</div><div class="gmail_default"><br></div><div class="gmail_default"><br></div><div class="gmail_default"><font face="arial, sans-serif"><b style="white-space:pre-wrap">Host:</b><span style="white-space:pre-wrap"> </span><a href="mailto:avrim@ttic.edu" style="white-space:pre-wrap" target="_blank">Avrim Blum</a><br></font></div><div class="gmail_default"><br></div><div class="gmail_default"><br></div><div class="gmail_default"><br></div></div><div><div dir="ltr" data-smartmail="gmail_signature"><div dir="ltr"><div><div dir="ltr"><div><div dir="ltr"><div><div dir="ltr"><div><div dir="ltr"><div><div dir="ltr"><div><div dir="ltr"><font face="arial, helvetica, sans-serif">Mary C. Marre</font><div><font face="arial, helvetica, sans-serif">Faculty Administrative Support</font></div><div><i><font face="arial, helvetica, sans-serif" color="#3d85c6"><b>Toyota Technological Institute</b></font></i></div><div><i><font face="arial, helvetica, sans-serif" color="#3d85c6">6045 S. Kenwood Avenue</font></i></div><div><i><font face="arial, helvetica, sans-serif" color="#3d85c6">Room 517</font></i></div><div><i><font face="arial, helvetica, sans-serif" color="#3d85c6">Chicago, IL 60637</font></i></div><div><i><font face="arial, helvetica, sans-serif">p:(773) 834-1757</font></i></div><div><i><font face="arial, helvetica, sans-serif">f: (773) 357-6970</font></i></div><div><b><i><a href="mailto:mmarre@ttic.edu" target="_blank"><font face="arial, helvetica, sans-serif">mmarre@ttic.edu</font></a></i></b></div></div></div></div></div></div></div></div></div></div></div></div></div></div></div></div><br></div><br><div class="gmail_quote"><div dir="ltr" class="gmail_attr">On Wed, Jan 27, 2021 at 7:48 PM Mary Marre <<a href="mailto:mmarre@ttic.edu" target="_blank">mmarre@ttic.edu</a>> wrote:<br></div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex"><div dir="ltr"><div style="font-size:small"><b> </b></div><div><p style="font-size:small;font-variant-numeric:normal;font-variant-east-asian:normal;font-stretch:normal;line-height:normal;margin:0px"><font face="arial, sans-serif"><font style="vertical-align:inherit"><font style="vertical-align:inherit"><b>When:</b> </font></font><font style="vertical-align:inherit"><font style="vertical-align:inherit"> Wednesday, February 3rd at<b> 11:10 am CT</b></font></font><br></font></p><p class="MsoNormal" style="font-size:small;margin:0in 0in 0.0001pt;line-height:normal;background-image:initial;background-position:initial;background-size:initial;background-repeat:initial;background-origin:initial;background-clip:initial"><font face="arial, sans-serif"> </font></p><p class="MsoNormal" style="font-size:small;margin:0in 0in 0.0001pt;line-height:normal;background-image:initial;background-position:initial;background-size:initial;background-repeat:initial;background-origin:initial;background-clip:initial"><font face="arial, sans-serif"><font style="vertical-align:inherit"><font style="vertical-align:inherit"><b>Where:</b> </font></font></font><font color="#000000" style="font-family:arial,sans-serif">Zoom Virtual Talk (</font><b><span style="line-height:107%;color:blue"><font face="arial, sans-serif" style="color:rgb(5,99,193)"><a href="https://uchicagogroup.zoom.us/webinar/register/WN_8sgotwgtTBCOOzN-okLDtA" style="color:rgb(5,99,193)" target="_blank"><i>register
for talk here</i></a></font></span></b><span style="font-family:arial,sans-serif;color:rgb(0,0,0)">)</span></p><p class="MsoNormal" style="font-size:small;margin:0in 0in 0.0001pt;line-height:normal;background-image:initial;background-position:initial;background-size:initial;background-repeat:initial;background-origin:initial;background-clip:initial"><font face="arial, sans-serif"> </font></p><p class="MsoNormal" style="margin:0in 0in 0.0001pt;line-height:normal;background-image:initial;background-position:initial;background-size:initial;background-repeat:initial;background-origin:initial;background-clip:initial"><font face="arial, sans-serif" style="font-size:small"><font style="vertical-align:inherit"><font style="vertical-align:inherit"><b>Who: </b> </font></font></font><span style="color:rgb(60,64,67);letter-spacing:0.2px"><font face="arial, sans-serif">Mahsa Derakhshan, University of Maryland</font></span></p><br></div><div><p dir="ltr" style="color:rgb(0,0,0);line-height:1.9872;margin-top:0pt;margin-bottom:0pt"><span style="font-variant-east-asian:normal;vertical-align:baseline;white-space:pre-wrap"><font face="arial, sans-serif"><b>Title: </b>Algorithms for Markets: Matching and Pricing </font></span></p><p dir="ltr" style="color:rgb(0,0,0);line-height:1.9872;margin-top:0pt;margin-bottom:0pt"><b style="color:rgb(34,34,34)"><br></b></p><b>Abstract:</b> Modern market algorithms have transformed in crucial ways due to the presence of uncertainty, strategic behavior, and the huge volume of data to process. This is the case both in markets where money plays a role (monetary markets,) such as auctions, and those without money (non-monetary markets,) such as matching markets. In this talk, I will discuss my works on some of the prominent examples of these markets such as stochastic matchings and pricing mechanisms for auctions.</div><div><br></div><div>The main focus of the talk will be on the stochastic matching problem, which has applications in kidney exchange, online labor markets, and dating apps among others. 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 its 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 and expensive. I 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.<br><br><b>Bio:</b> Mahsa is a fifth-year Ph.D. candidate in Computer Science at the University of Maryland, advised by MohammdTaghi 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 main area of research is algorithmic mechanism design with a special focus on designing models and algorithms for online platforms such as online advertising markets, online matching markets, and online retail markets. She is also interested in the design and analysis of big-data algorithms, particularly 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.</div><div><br></div><div><br></div><div><font face="arial, sans-serif"><b style="white-space:pre-wrap">Host:</b><span style="white-space:pre-wrap"> </span><a href="mailto:avrim@ttic.edu" style="white-space:pre-wrap" target="_blank">Avrim Blum</a><br></font></div><div><br></div><div><br></div><div><br></div><div><br></div><div><div dir="ltr"><div dir="ltr"><div><div dir="ltr"><div><div dir="ltr"><div><div dir="ltr"><div><div dir="ltr"><div><div dir="ltr"><div><div dir="ltr"><font face="arial, helvetica, sans-serif">Mary C. Marre</font><div><font face="arial, helvetica, sans-serif">Faculty Administrative Support</font></div><div><i><font face="arial, helvetica, sans-serif" color="#3d85c6"><b>Toyota Technological Institute</b></font></i></div><div><i><font face="arial, helvetica, sans-serif" color="#3d85c6">6045 S. Kenwood Avenue</font></i></div><div><i><font face="arial, helvetica, sans-serif" color="#3d85c6">Room 517</font></i></div><div><i><font face="arial, helvetica, sans-serif" color="#3d85c6">Chicago, IL 60637</font></i></div><div><i><font face="arial, helvetica, sans-serif">p:(773) 834-1757</font></i></div><div><i><font face="arial, helvetica, sans-serif">f: (773) 357-6970</font></i></div><div><b><i><a href="mailto:mmarre@ttic.edu" target="_blank"><font face="arial, helvetica, sans-serif">mmarre@ttic.edu</font></a></i></b></div></div></div></div></div></div></div></div></div></div></div></div></div></div></div></div></div>
</blockquote></div></div>