[Theory] 10/13 Talks at TTIC: Divyarthi Mohan, Tel Aviv University

[Mary Marre]

*When:*        Thursday, October 13th at* 1:00 pm CT*


*Where:       *Talk will be given *live, in-person* at

                   TTIC, 6045 S. Kenwood Avenue

                   5th Floor, Room 530

*Virtually:*  *via* Panopto (*livestream*
<https://uchicago.hosted.panopto.com/Panopto/Pages/Viewer.aspx?id=ae483ef4-1fa6-44ce-8419-af2a00c0323b>
)

*Who: *         Divyarthi Mohan, Tel Aviv University
------------------------------
*Title:          *Simplicity and Optimality in Multi-Dimensional Mechanism
Design

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

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.

This talk is based on the following two works:
- Approximation Schemes for a Unit-Demand Buyer with Independent Items via
Symmetries. Pravesh Kothari, Divyarthi Mohan, Ariel Schvartzman, Sahil
Singla, Matt Weinberg (FOCS 2019).
- Simple Mechanisms for Welfare Maximization in Rich Advertising Auctions.
Gagan Aggarwal, Kshipra Bhawalkar, Aranyak Mehta, Divyarthi Mohan, Alex
Psomas (Neurips 2022).

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

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


Mary C. Marre
Faculty Administrative Support
*Toyota Technological Institute*
*6045 S. Kenwood Avenue*
*Chicago, IL  60637*
*mmarre at ttic.edu <mmarre at ttic.edu>*
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mailman.cs.uchicago.edu/pipermail/theory/attachments/20221010/3c92cf9a/attachment.html>