Nikhil Devanur - Lagrangian Duality in Mechanism Design

From Katie Gentilello October 14th, 2019

25 plays 0 comments

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.

Tags: arc colloquiumalgorithms and randomness centergeorgia techrecorded by gtlibraryfall 2019

name: Nikhil Devanur
Date: September 30th, 2019
Appears In: Open Scholarship

Comments
Related Media

Loading…

Nikhil Devanur - Lagrangian Duality in Mechanism Design

Related Media