Presenter: Divya Mohan
Topic: Simplicity and Optimality in Algorithmic Economics
The EconCS Group holds an Economics and Computer Science research seminar each semester.
Fall 2021 meetings are held at 1 - 2:30 PM on Fridays. Seminar Coordinators for Fall '21 are Srivatsa R Sai and Daniel Halpern.
Title: Simplicity and Optimality in Algorithmic Economics
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 my work on strategic communication in a sender-receiver game. In our model, to reflect real social exchanges, the sender simply shares a signal (or anecdote) they observed instead of sending arbitrary messages. The receiver then takes an action that is payoff relevant to both the agents. A key result in our work shows that, when the agents' preferences are misaligned, the optimal communication scheme can vary drastically depending on whether the receiver can observe the communication scheme used by the sender.
This talk is based on the following two works:
- Approximation Schemes for a Unit-Demand Buyer with Independent Items via Symmetries. Kothari, Mohan, Schvartzman, Singla, Weinberg (FOCS 2019).
- Communicating with Anecdotes. Haghtalab, Immorlica, Lucier, Mobius, Mohan (Working Paper).
LOCATION:Zoom STATUS:CONFIRMED DTSTART:20211119T180000Z DTEND:20211119T180000Z END:VEVENT END:VCALENDAR