Nikhil Devanur - Lagrangian Duality in Mechanism Design
From Kathryn Gentilello on October 14th, 2019
This talk surveys the usage of Lagrangian Duality in the design and analysis of auctions. Designing optimal (revenue maximizing) auctions in multi-parameter settings has been among the most active areas in algorithmic mechanism design in the last few years. We have discovered that Lagrangian duality is a very useful and versatile tool for this purpose. It has been used to do all of the following.
1. Derive that the optimal auction is a virtual welfare maximizer.
2. Obtain a fast algorithm for approximating the optimal auction.
3. Show how simple auctions are approximately optimal.
4. Characterize optimal auctions for structured environments.
5. Get bounds on the menu-size complexity of optimal auctions.
I will survey these applications and dive deeper into a subset of these.