[Theory] REMINDER: 2/3 Talks at TTIC: Mahsa Derakhshan, University of Maryland

[Mary Marre]

*When:*      Wednesday, February 3rd at* 11:10 am CT*



*Where:*     Zoom Virtual Talk (*register for talk here
<https://uchicagogroup.zoom.us/webinar/register/WN_8sgotwgtTBCOOzN-okLDtA>*)



*Who: *       Mahsa Derakhshan, University of Maryland

*Title: *Algorithms for Markets: Matching and Pricing


*Abstract:* 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.

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.

*Bio:* 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.


*Host:* Avrim Blum <avrim at ttic.edu>



Mary C. Marre
Faculty Administrative Support
*Toyota Technological Institute*
*6045 S. Kenwood Avenue*
*Room 517*
*Chicago, IL  60637*
*p:(773) 834-1757*
*f: (773) 357-6970*
*mmarre at ttic.edu <mmarre at ttic.edu>*


On Wed, Jan 27, 2021 at 7:48 PM Mary Marre <mmarre at ttic.edu> wrote:

>
>
> *When:*      Wednesday, February 3rd at* 11:10 am CT*
>
>
>
> *Where:*     Zoom Virtual Talk (*register for talk here
> <https://uchicagogroup.zoom.us/webinar/register/WN_8sgotwgtTBCOOzN-okLDtA>*
> )
>
>
>
> *Who: *       Mahsa Derakhshan, University of Maryland
>
> *Title: *Algorithms for Markets: Matching and Pricing
>
>
> *Abstract:* 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.
>
> 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.
>
> *Bio:* 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.
>
>
> *Host:* Avrim Blum <avrim at ttic.edu>
>
>
>
>
> Mary C. Marre
> Faculty Administrative Support
> *Toyota Technological Institute*
> *6045 S. Kenwood Avenue*
> *Room 517*
> *Chicago, IL  60637*
> *p:(773) 834-1757*
> *f: (773) 357-6970*
> *mmarre at ttic.edu <mmarre at ttic.edu>*
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mailman.cs.uchicago.edu/pipermail/theory/attachments/20210202/5722c8ba/attachment.html>