*********************************
There is now a CONTENT FREEZE for Mercury while we switch to a new platform. It began on Friday, March 10 at 6pm and will end on Wednesday, March 15 at noon. No new content can be created during this time, but all material in the system as of the beginning of the freeze will be migrated to the new platform, including users and groups. Functionally the new site is identical to the old one. webteam@gatech.edu
*********************************
Algorithms & Randomness Center (ARC)
Divyarthi Mohan (Tel Aviv University)
Monday, January 10, 2022
Klaus 1116 - 11:00 am
Title: Simplicity and Optimality in Multi-Item Auctions
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.
Joint work with Pravesh Kothari, Ariel Schvartzman, Sahil Singla, and Matt Weinberg.
----------------------------------
Videos of recent talks are available at: https://smartech.gatech.edu/handle/1853/46836
Click here to subscribe to the seminar email list: arc-colloq@Klauscc.gatech.edu
