<div dir="ltr"><div dir="ltr"><div class="gmail_default" style="font-size:small"><div class="gmail_default"><div dir="ltr" style="color:rgb(80,0,80)"><div class="gmail_default"><div class="gmail_default"><font face="arial, sans-serif"><font style="color:rgb(0,0,0);vertical-align:inherit"><font style="vertical-align:inherit"><b>When:</b>    </font></font><font style="color:rgb(0,0,0);vertical-align:inherit"><font style="vertical-align:inherit">    Thursday<span class="gmail_default">, October 13th</span> at<b> <span style="background-color:rgb(255,255,0)">1:00 pm CT</span></b></font></font></font></div><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" color="#000000"><font style="vertical-align:inherit"><font style="vertical-align:inherit"><b><span style="background-color:rgb(255,255,0)"><br></span></b></font></font></font></p><div class="gmail_default"><font face="arial, sans-serif"><b><font color="#500050">Where:      </font><font color="#000000"> </font></b><font color="#000000">Talk will be given </font><font color="#0000ff" style="font-weight:bold"><u>live, in-person</u></font><font style="font-weight:bold"> </font>at</font></div><p class="MsoNormal" style="margin:0in;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 color="#500050">               </font><font color="#000000">    TTIC, 6045 S. Kenwood Avenue</font></font></p><p class="MsoNormal" style="margin:0in;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" color="#000000">                   5th Floor, Room 530<b> </b></font></p><font face="arial, sans-serif"><br></font></div><div class="gmail_default"><font face="arial, sans-serif"><b style="color:rgb(60,64,67);letter-spacing:0.2px;white-space:pre-wrap">Virtually:</b><span style="color:rgb(60,64,67);letter-spacing:0.2px;white-space:pre-wrap">    <i>via</i> Panopto (</span><a href="https://uchicago.hosted.panopto.com/Panopto/Pages/Viewer.aspx?id=ae483ef4-1fa6-44ce-8419-af2a00c0323b" target="_blank"><b><font color="#0000ff">livestream</font></b></a>)<br clear="all"></font></div><div class="gmail_default"><font face="arial, sans-serif"><br></font></div><div class="gmail_default"><div dir="ltr"><div class="gmail_default"><div class="gmail_default"><div class="gmail_default"><div class="gmail_default"><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 color="#500050">    </font><font color="#000000"><font color="#500050">   </font> </font></font></font>Divyarthi Mohan, Tel Aviv University</font></p><div class="MsoNormal" align="center" style="margin:0in 0in 8pt;font-size:11pt;text-align:center;line-height:15.6933px;font-family:Calibri,sans-serif"><hr size="2" width="100%" align="center"></div><div><font face="arial, sans-serif"><b style="color:rgb(60,64,67)">Title:          </b><span style="color:rgb(60,64,67)">Simplicity and Optimality in Multi-Dimensional Mechanism Design</span><br style="color:rgb(60,64,67)"><br style="color:rgb(60,64,67)"><b style="color:rgb(60,64,67)">Abstract: </b><span style="color:rgb(60,64,67)">Designing mechanisms to maximize revenue is a fundamental problem in mathematical economics and has various applications like online ad auctions and spectrum auctions. Unfortunately, optimal auctions for selling multiple items can be unreasonably complex and computationally intractable. In this talk, we consider a revenue-maximizing seller with n items facing a single unit-demand buyer. Our work shows that simple mechanisms can achieve almost optimal revenue. We approached the tradeoffs of simplicity formally through the lens of computation and menu size. Our main result provides a mechanism that gets a (1 − ε)-approximation to the optimal revenue in time quasi-polynomial in n and has quasi polynomial (symmetric) menu complexity.</span></font></div><div><font face="arial, sans-serif"><br style="color:rgb(60,64,67)"><span style="color:rgb(60,64,67)">I will also briefly discuss our work on welfare maximization in rich advertising auctions. Online ad auctions have evolved from allocating a few lines of text to richer formats that include images, sitelinks, etc. In our model, advertisers can be strategic both about their bid per click and the set of ad formats they are interested in (i.e, they are of multi-dimensional types). The advertisers are unit-demand and the seller's goal is to maximize welfare subject to a knapsack constraint. We provide a simple greedy-like allocation that is monotone (in both value and the set of formats) and guarantees a 1/3-approximation to the optimal welfare.</span></font></div><div><font face="arial, sans-serif"><br style="color:rgb(60,64,67)"><span style="color:rgb(60,64,67)">This talk is based on the following two works:</span><br style="color:rgb(60,64,67)"><span style="color:rgb(60,64,67)">- Approximation Schemes for a Unit-Demand Buyer with Independent Items via Symmetries. Pravesh Kothari, Divyarthi Mohan, Ariel Schvartzman, Sahil Singla, Matt Weinberg (FOCS 2019).</span><br style="color:rgb(60,64,67)"><span style="color:rgb(60,64,67)">- Simple Mechanisms for Welfare Maximization in Rich Advertising Auctions. Gagan Aggarwal, Kshipra Bhawalkar, Aranyak Mehta, Divyarthi Mohan, Alex Psomas (Neurips 2022).</span><br style="color:rgb(60,64,67)"><br style="color:rgb(60,64,67)"><b style="color:rgb(60,64,67)">Bio: </b><span style="color:rgb(60,64,67)">Divyarthi Mohan is a Postdoctoral Fellow at Tel Aviv University's EconCS lab hosted by Michal Feldman. She received her PhD in Computer Science from Princeton University in 2021 advised by Matt Weinberg. Divya's research interest broadly lies at the intersection of computer science and economics. She is primarily interested in algorithmic mechanism design, social learning and strategic communication. She was awarded the Simons-Berkeley Research Fellowship for Fall 2022, and the class of 2021 Siebel Scholarship. </span></font></div><div><span style="color:rgb(60,64,67);font-family:Roboto,Helvetica,Arial,sans-serif;font-size:14px;background-color:rgb(241,243,244)"><br></span></div></div></div></div></div></div></div></div></div><div class="gmail_quote" style="color:rgb(80,0,80)"><div dir="ltr" class="gmail_attr"><b style="white-space:pre-wrap;font-family:arial,sans-serif"><font color="#000000">Host:</font></b><b style="white-space:pre-wrap;font-family:arial,sans-serif"> </b><a href="mailto:avrim@ttic.edu" target="_blank" style="white-space:pre-wrap;font-family:arial,sans-serif"><b><font color="#0000ff">Avrim Blum</font></b></a></div></div></div><div class="gmail_default"><br></div></div><div><div dir="ltr" class="gmail_signature"><div dir="ltr"><div><span style="font-family:arial,helvetica,sans-serif;font-size:x-small">Mary C. Marre</span><br></div><div><div><font face="arial, helvetica, sans-serif" size="1">Faculty Administrative Support</font></div><div><i><font face="arial, helvetica, sans-serif" color="#3d85c6" size="1"><b>Toyota Technological Institute</b></font></i></div><div><i><font face="arial, helvetica, sans-serif" color="#3d85c6" size="1">6045 S. Kenwood Avenue</font></i></div><div><font size="1"><i><font face="arial, helvetica, sans-serif" color="#3d85c6">Chicago, IL  60637</font></i><br></font></div><div><b><i><a href="mailto:mmarre@ttic.edu" target="_blank"><font face="arial, helvetica, sans-serif" size="1">mmarre@ttic.edu</font></a></i></b></div></div></div></div></div><br></div><br><div class="gmail_quote"><div dir="ltr" class="gmail_attr">On Thu, Oct 13, 2022 at 12:28 PM Mary Marre <<a href="mailto:mmarre@ttic.edu">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 dir="ltr"><div style="font-size:small"><div><div dir="ltr" style="color:rgb(80,0,80)"><div><div><font face="arial, sans-serif"><font style="color:rgb(0,0,0);vertical-align:inherit"><font style="vertical-align:inherit"><b>When:</b>    </font></font><font style="color:rgb(0,0,0);vertical-align:inherit"><font style="vertical-align:inherit">    Thursday<span class="gmail_default">, October 13th</span> at<b> <span style="background-color:rgb(255,255,0)">1:00 pm CT</span></b></font></font></font></div><div><p style="font-variant-numeric:normal;font-variant-east-asian:normal;font-stretch:normal;line-height:normal;margin:0px"><font face="arial, sans-serif" color="#000000"><font style="vertical-align:inherit"><font style="vertical-align:inherit"><b><span style="background-color:rgb(255,255,0)"><br></span></b></font></font></font></p><div><font face="arial, sans-serif"><b><font color="#500050">Where:      </font><font color="#000000"> </font></b><font color="#000000">Talk will be given </font><font color="#0000ff" style="font-weight:bold"><u>live, in-person</u></font><font style="font-weight:bold"> </font>at</font></div><p class="MsoNormal" style="margin:0in;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 color="#500050">               </font><font color="#000000">    TTIC, 6045 S. Kenwood Avenue</font></font></p><p class="MsoNormal" style="margin:0in;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" color="#000000">                   5th Floor, Room 530<b> </b></font></p><font face="arial, sans-serif"><br></font></div><div><font face="arial, sans-serif"><b style="color:rgb(60,64,67);letter-spacing:0.2px;white-space:pre-wrap">Virtually:</b><span style="color:rgb(60,64,67);letter-spacing:0.2px;white-space:pre-wrap">    <i>via</i> Panopto (</span><a href="https://uchicago.hosted.panopto.com/Panopto/Pages/Viewer.aspx?id=ae483ef4-1fa6-44ce-8419-af2a00c0323b" target="_blank"><b><font color="#0000ff">livestream</font></b></a>)<br clear="all"></font></div><div><font face="arial, sans-serif"><br></font></div><div><div dir="ltr"><div><div><div><div><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 color="#500050">    </font><font color="#000000"><font color="#500050">   </font> </font></font></font>Divyarthi Mohan, Tel Aviv University</font></p><div class="MsoNormal" align="center" style="margin:0in 0in 8pt;font-size:11pt;text-align:center;line-height:15.6933px;font-family:Calibri,sans-serif"><hr size="2" width="100%" align="center"></div><div><font face="arial, sans-serif"><b style="color:rgb(60,64,67)">Title:          </b><span style="color:rgb(60,64,67)">Simplicity and Optimality in Multi-Dimensional Mechanism Design</span><br style="color:rgb(60,64,67)"><br style="color:rgb(60,64,67)"><b style="color:rgb(60,64,67)">Abstract: </b><span style="color:rgb(60,64,67)">Designing mechanisms to maximize revenue is a fundamental problem in mathematical economics and has various applications like online ad auctions and spectrum auctions. Unfortunately, optimal auctions for selling multiple items can be unreasonably complex and computationally intractable. In this talk, we consider a revenue-maximizing seller with n items facing a single unit-demand buyer. Our work shows that simple mechanisms can achieve almost optimal revenue. We approached the tradeoffs of simplicity formally through the lens of computation and menu size. Our main result provides a mechanism that gets a (1 − ε)-approximation to the optimal revenue in time quasi-polynomial in n and has quasi polynomial (symmetric) menu complexity.</span></font></div><div><font face="arial, sans-serif"><br style="color:rgb(60,64,67)"><span style="color:rgb(60,64,67)">I will also briefly discuss our work on welfare maximization in rich advertising auctions. Online ad auctions have evolved from allocating a few lines of text to richer formats that include images, sitelinks, etc. In our model, advertisers can be strategic both about their bid per click and the set of ad formats they are interested in (i.e, they are of multi-dimensional types). The advertisers are unit-demand and the seller's goal is to maximize welfare subject to a knapsack constraint. We provide a simple greedy-like allocation that is monotone (in both value and the set of formats) and guarantees a 1/3-approximation to the optimal welfare.</span></font></div><div><font face="arial, sans-serif"><br style="color:rgb(60,64,67)"><span style="color:rgb(60,64,67)">This talk is based on the following two works:</span><br style="color:rgb(60,64,67)"><span style="color:rgb(60,64,67)">- Approximation Schemes for a Unit-Demand Buyer with Independent Items via Symmetries. Pravesh Kothari, Divyarthi Mohan, Ariel Schvartzman, Sahil Singla, Matt Weinberg (FOCS 2019).</span><br style="color:rgb(60,64,67)"><span style="color:rgb(60,64,67)">- Simple Mechanisms for Welfare Maximization in Rich Advertising Auctions. Gagan Aggarwal, Kshipra Bhawalkar, Aranyak Mehta, Divyarthi Mohan, Alex Psomas (Neurips 2022).</span><br style="color:rgb(60,64,67)"><br style="color:rgb(60,64,67)"><b style="color:rgb(60,64,67)">Bio: </b><span style="color:rgb(60,64,67)">Divyarthi Mohan is a Postdoctoral Fellow at Tel Aviv University's EconCS lab hosted by Michal Feldman. She received her PhD in Computer Science from Princeton University in 2021 advised by Matt Weinberg. Divya's research interest broadly lies at the intersection of computer science and economics. She is primarily interested in algorithmic mechanism design, social learning and strategic communication. She was awarded the Simons-Berkeley Research Fellowship for Fall 2022, and the class of 2021 Siebel Scholarship. </span></font></div><div><span style="color:rgb(60,64,67);font-family:Roboto,Helvetica,Arial,sans-serif;font-size:14px;background-color:rgb(241,243,244)"><br></span></div></div></div></div></div></div></div></div></div><div class="gmail_quote" style="color:rgb(80,0,80)"><div dir="ltr" class="gmail_attr"><b style="white-space:pre-wrap;font-family:arial,sans-serif"><font color="#000000">Host:</font></b><b style="white-space:pre-wrap;font-family:arial,sans-serif"> </b><a href="mailto:avrim@ttic.edu" style="white-space:pre-wrap;font-family:arial,sans-serif" target="_blank"><b><font color="#0000ff">Avrim Blum</font></b></a></div></div></div><div><br></div><div><br></div></div><div><div dir="ltr"><div dir="ltr"><div><span style="font-family:arial,helvetica,sans-serif;font-size:x-small">Mary C. Marre</span><br></div><div><div><font face="arial, helvetica, sans-serif" size="1">Faculty Administrative Support</font></div><div><i><font face="arial, helvetica, sans-serif" color="#3d85c6" size="1"><b>Toyota Technological Institute</b></font></i></div><div><i><font face="arial, helvetica, sans-serif" color="#3d85c6" size="1">6045 S. Kenwood Avenue</font></i></div><div><font size="1"><i><font face="arial, helvetica, sans-serif" color="#3d85c6">Chicago, IL  60637</font></i><br></font></div><div><b><i><a href="mailto:mmarre@ttic.edu" target="_blank"><font face="arial, helvetica, sans-serif" size="1">mmarre@ttic.edu</font></a></i></b></div></div></div></div></div><br></div><br><div class="gmail_quote"><div dir="ltr" class="gmail_attr">On Wed, Oct 12, 2022 at 4:19 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 dir="ltr"><div style="font-size:small"><div><div dir="ltr" style="color:rgb(80,0,80)"><div><div><font face="arial, sans-serif"><font style="color:rgb(0,0,0);vertical-align:inherit"><font style="vertical-align:inherit"><b>When:</b>    </font></font><font style="color:rgb(0,0,0);vertical-align:inherit"><font style="vertical-align:inherit">    Thursday<span class="gmail_default">, October 13th</span> at<b> <span style="background-color:rgb(255,255,0)">1:00 pm CT</span></b></font></font></font></div><div><p style="font-variant-numeric:normal;font-variant-east-asian:normal;font-stretch:normal;line-height:normal;margin:0px"><font face="arial, sans-serif" color="#000000"><font style="vertical-align:inherit"><font style="vertical-align:inherit"><b><span style="background-color:rgb(255,255,0)"><br></span></b></font></font></font></p><div><font face="arial, sans-serif"><b><font color="#500050">Where:      </font><font color="#000000"> </font></b><font color="#000000">Talk will be given </font><font color="#0000ff" style="font-weight:bold"><u>live, in-person</u></font><font style="font-weight:bold"> </font>at</font></div><p class="MsoNormal" style="margin:0in;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 color="#500050">               </font><font color="#000000">    TTIC, 6045 S. Kenwood Avenue</font></font></p><p class="MsoNormal" style="margin:0in;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" color="#000000">                   5th Floor, Room 530<b> </b></font></p><font face="arial, sans-serif"><br></font></div><div><font face="arial, sans-serif"><b style="color:rgb(60,64,67);letter-spacing:0.2px;white-space:pre-wrap">Virtually:</b><span style="color:rgb(60,64,67);letter-spacing:0.2px;white-space:pre-wrap">    <i>via</i> Panopto (</span><a href="https://uchicago.hosted.panopto.com/Panopto/Pages/Viewer.aspx?id=ae483ef4-1fa6-44ce-8419-af2a00c0323b" target="_blank"><b><font color="#0000ff">livestream</font></b></a>)<br clear="all"></font></div><div><font face="arial, sans-serif"><br></font></div><div><div dir="ltr"><div><div><div><div><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 color="#500050">    </font><font color="#000000"><font color="#500050">   </font> </font></font></font>Divyarthi Mohan, Tel Aviv University</font></p><div class="MsoNormal" align="center" style="margin:0in 0in 8pt;font-size:11pt;text-align:center;line-height:15.6933px;font-family:Calibri,sans-serif"><hr size="2" width="100%" align="center"></div><div><font face="arial, sans-serif"><b style="color:rgb(60,64,67)">Title:          </b><span style="color:rgb(60,64,67)">Simplicity and Optimality in Multi-Dimensional Mechanism Design</span><br style="color:rgb(60,64,67)"><br style="color:rgb(60,64,67)"><b style="color:rgb(60,64,67)">Abstract: </b><span style="color:rgb(60,64,67)">Designing mechanisms to maximize revenue is a fundamental problem in mathematical economics and has various applications like online ad auctions and spectrum auctions. Unfortunately, optimal auctions for selling multiple items can be unreasonably complex and computationally intractable. In this talk, we consider a revenue-maximizing seller with n items facing a single unit-demand buyer. Our work shows that simple mechanisms can achieve almost optimal revenue. We approached the tradeoffs of simplicity formally through the lens of computation and menu size. Our main result provides a mechanism that gets a (1 − ε)-approximation to the optimal revenue in time quasi-polynomial in n and has quasi polynomial (symmetric) menu complexity.</span></font></div><div><font face="arial, sans-serif"><br style="color:rgb(60,64,67)"><span style="color:rgb(60,64,67)">I will also briefly discuss our work on welfare maximization in rich advertising auctions. Online ad auctions have evolved from allocating a few lines of text to richer formats that include images, sitelinks, etc. In our model, advertisers can be strategic both about their bid per click and the set of ad formats they are interested in (i.e, they are of multi-dimensional types). The advertisers are unit-demand and the seller's goal is to maximize welfare subject to a knapsack constraint. We provide a simple greedy-like allocation that is monotone (in both value and the set of formats) and guarantees a 1/3-approximation to the optimal welfare.</span></font></div><div><font face="arial, sans-serif"><br style="color:rgb(60,64,67)"><span style="color:rgb(60,64,67)">This talk is based on the following two works:</span><br style="color:rgb(60,64,67)"><span style="color:rgb(60,64,67)">- Approximation Schemes for a Unit-Demand Buyer with Independent Items via Symmetries. Pravesh Kothari, Divyarthi Mohan, Ariel Schvartzman, Sahil Singla, Matt Weinberg (FOCS 2019).</span><br style="color:rgb(60,64,67)"><span style="color:rgb(60,64,67)">- Simple Mechanisms for Welfare Maximization in Rich Advertising Auctions. Gagan Aggarwal, Kshipra Bhawalkar, Aranyak Mehta, Divyarthi Mohan, Alex Psomas (Neurips 2022).</span><br style="color:rgb(60,64,67)"><br style="color:rgb(60,64,67)"><b style="color:rgb(60,64,67)">Bio: </b><span style="color:rgb(60,64,67)">Divyarthi Mohan is a Postdoctoral Fellow at Tel Aviv University's EconCS lab hosted by Michal Feldman. She received her PhD in Computer Science from Princeton University in 2021 advised by Matt Weinberg. Divya's research interest broadly lies at the intersection of computer science and economics. She is primarily interested in algorithmic mechanism design, social learning and strategic communication. She was awarded the Simons-Berkeley Research Fellowship for Fall 2022, and the class of 2021 Siebel Scholarship. </span></font></div><div><span style="color:rgb(60,64,67);font-family:Roboto,Helvetica,Arial,sans-serif;font-size:14px;background-color:rgb(241,243,244)"><br></span></div></div></div></div></div></div></div></div></div><div class="gmail_quote" style="color:rgb(80,0,80)"><div dir="ltr" class="gmail_attr"><b style="white-space:pre-wrap;font-family:arial,sans-serif"><font color="#000000">Host:</font></b><b style="white-space:pre-wrap;font-family:arial,sans-serif"> </b><a href="mailto:avrim@ttic.edu" style="white-space:pre-wrap;font-family:arial,sans-serif" target="_blank"><b><font color="#0000ff">Avrim Blum</font></b></a></div></div></div><div><br></div><div><br></div><div><br></div></div><div><div dir="ltr"><div dir="ltr"><div><span style="font-family:arial,helvetica,sans-serif;font-size:x-small">Mary C. Marre</span><br></div><div><div><font face="arial, helvetica, sans-serif" size="1">Faculty Administrative Support</font></div><div><i><font face="arial, helvetica, sans-serif" color="#3d85c6" size="1"><b>Toyota Technological Institute</b></font></i></div><div><i><font face="arial, helvetica, sans-serif" color="#3d85c6" size="1">6045 S. Kenwood Avenue</font></i></div><div><font size="1"><i><font face="arial, helvetica, sans-serif" color="#3d85c6">Chicago, IL  60637</font></i><br></font></div><div><b><i><a href="mailto:mmarre@ttic.edu" target="_blank"><font face="arial, helvetica, sans-serif" size="1">mmarre@ttic.edu</font></a></i></b></div></div></div></div></div><br></div><br><div class="gmail_quote"><div dir="ltr" class="gmail_attr">On Mon, Oct 10, 2022 at 7:21 AM 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><div><div dir="ltr" style="color:rgb(80,0,80)"><div><div><font face="arial, sans-serif"><font style="color:rgb(0,0,0);vertical-align:inherit"><font style="vertical-align:inherit"><b>When:</b>    </font></font><font style="color:rgb(0,0,0);vertical-align:inherit"><font style="vertical-align:inherit">    Thursday<span class="gmail_default">, October 13th</span> at<b> <span style="background-color:rgb(255,255,0)">1:00 pm CT</span></b></font></font></font></div><div><p style="font-variant-numeric:normal;font-variant-east-asian:normal;font-stretch:normal;line-height:normal;margin:0px"><font face="arial, sans-serif" color="#000000"><font style="vertical-align:inherit"><font style="vertical-align:inherit"><b><span style="background-color:rgb(255,255,0)"><br></span></b></font></font></font></p><div><font face="arial, sans-serif"><b><font color="#500050">Where:      </font><font color="#000000"> </font></b><font color="#000000">Talk will be given </font><font color="#0000ff" style="font-weight:bold"><u>live, in-person</u></font><font style="font-weight:bold"> </font>at</font></div><p class="MsoNormal" style="margin:0in;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 color="#500050">               </font><font color="#000000">    TTIC, 6045 S. Kenwood Avenue</font></font></p><p class="MsoNormal" style="margin:0in;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" color="#000000">                   5th Floor, Room 530<b> </b></font></p><font face="arial, sans-serif"><br></font></div><div><font face="arial, sans-serif"><b style="color:rgb(60,64,67);letter-spacing:0.2px;white-space:pre-wrap">Virtually:</b><span style="color:rgb(60,64,67);letter-spacing:0.2px;white-space:pre-wrap">    <i>via</i> Panopto (</span><a href="https://uchicago.hosted.panopto.com/Panopto/Pages/Viewer.aspx?id=ae483ef4-1fa6-44ce-8419-af2a00c0323b" target="_blank"><b><font color="#0000ff">livestream</font></b></a>)<br clear="all"></font></div><div><font face="arial, sans-serif"><br></font></div><div><div dir="ltr"><div><div><div><div><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 color="#500050">    </font><font color="#000000"><font color="#500050">   </font> </font></font></font>Divyarthi Mohan, Tel Aviv University</font></p><div class="MsoNormal" align="center" style="font-size:11pt;margin:0in 0in 8pt;text-align:center;line-height:15.6933px;font-family:Calibri,sans-serif"><hr size="2" width="100%" align="center"></div><div><span style="background-color:rgb(255,255,255)"><font face="arial, sans-serif"><b style="color:rgb(60,64,67)">Title:          </b><span style="color:rgb(60,64,67)">Simplicity and Optimality in Multi-Dimensional Mechanism Design</span><br style="color:rgb(60,64,67)"><br style="color:rgb(60,64,67)"><b style="color:rgb(60,64,67)">Abstract: </b><span style="color:rgb(60,64,67)">Designing mechanisms to maximize revenue is a fundamental problem in mathematical economics and has various applications like online ad auctions and spectrum auctions. Unfortunately, optimal auctions for selling multiple items can be unreasonably complex and computationally intractable. In this talk, we consider a revenue-maximizing seller with n items facing a single unit-demand buyer. Our work shows that simple mechanisms can achieve almost optimal revenue. We approached the tradeoffs of simplicity formally through the lens of computation and menu size. Our main result provides a mechanism that gets a (1 − ε)-approximation to the optimal revenue in time quasi-polynomial in n and has quasi polynomial (symmetric) menu complexity.</span></font></span></div><div><span style="background-color:rgb(255,255,255)"><font face="arial, sans-serif"><br style="color:rgb(60,64,67)"><span style="color:rgb(60,64,67)">I will also briefly discuss our work on welfare maximization in rich advertising auctions. Online ad auctions have evolved from allocating a few lines of text to richer formats that include images, sitelinks, etc. In our model, advertisers can be strategic both about their bid per click and the set of ad formats they are interested in (i.e, they are of multi-dimensional types). The advertisers are unit-demand and the seller's goal is to maximize welfare subject to a knapsack constraint. We provide a simple greedy-like allocation that is monotone (in both value and the set of formats) and guarantees a 1/3-approximation to the optimal welfare.</span></font></span></div><div><span style="background-color:rgb(255,255,255)"><font face="arial, sans-serif"><br style="color:rgb(60,64,67)"><span style="color:rgb(60,64,67)">This talk is based on the following two works:</span><br style="color:rgb(60,64,67)"><span style="color:rgb(60,64,67)">- Approximation Schemes for a Unit-Demand Buyer with Independent Items via Symmetries. Pravesh Kothari, Divyarthi Mohan, Ariel Schvartzman, Sahil Singla, Matt Weinberg (FOCS 2019).</span><br style="color:rgb(60,64,67)"><span style="color:rgb(60,64,67)">- Simple Mechanisms for Welfare Maximization in Rich Advertising Auctions. Gagan Aggarwal, Kshipra Bhawalkar, Aranyak Mehta, Divyarthi Mohan, Alex Psomas (Neurips 2022).</span><br style="color:rgb(60,64,67)"><br style="color:rgb(60,64,67)"><b style="color:rgb(60,64,67)">Bio: </b><span style="color:rgb(60,64,67)">Divyarthi Mohan is a Postdoctoral Fellow at Tel Aviv University's EconCS lab hosted by Michal Feldman. She received her PhD in Computer Science from Princeton University in 2021 advised by Matt Weinberg. Divya's research interest broadly lies at the intersection of computer science and economics. She is primarily interested in algorithmic mechanism design, social learning and strategic communication. She was awarded the Simons-Berkeley Research Fellowship for Fall 2022, and the class of 2021 Siebel Scholarship. </span></font></span></div><div style="font-size:small"><span style="color:rgb(60,64,67);font-family:Roboto,Helvetica,Arial,sans-serif;font-size:14px;background-color:rgb(241,243,244)"><br></span></div></div></div></div></div></div></div></div></div><div class="gmail_quote" style="font-size:small;color:rgb(80,0,80)"><div dir="ltr" class="gmail_attr"><b style="white-space:pre-wrap;font-family:arial,sans-serif"><font color="#000000">Host:</font></b><b style="white-space:pre-wrap;font-family:arial,sans-serif"> </b><a href="mailto:avrim@ttic.edu" style="white-space:pre-wrap;font-family:arial,sans-serif" target="_blank"><b><font color="#0000ff">Avrim Blum</font></b></a></div></div></div><div style="font-size:small"><br></div><div style="font-size:small"><br></div></div><div><div dir="ltr"><div dir="ltr"><div><span style="font-family:arial,helvetica,sans-serif;font-size:x-small">Mary C. Marre</span><br></div><div><div><font face="arial, helvetica, sans-serif" size="1">Faculty Administrative Support</font></div><div><i><font face="arial, helvetica, sans-serif" color="#3d85c6" size="1"><b>Toyota Technological Institute</b></font></i></div><div><i><font face="arial, helvetica, sans-serif" color="#3d85c6" size="1">6045 S. Kenwood Avenue</font></i></div><div><font size="1"><i><font face="arial, helvetica, sans-serif" color="#3d85c6">Chicago, IL  60637</font></i><br></font></div><div><b><i><a href="mailto:mmarre@ttic.edu" target="_blank"><font face="arial, helvetica, sans-serif" size="1">mmarre@ttic.edu</font></a></i></b></div></div></div></div></div></div>
</blockquote></div></div>
</blockquote></div></div>
</blockquote></div></div>