ARC/ACO Alumni Colloquium: Nikhil Devanur (Amazon)

Event Details
  • Date/Time:
    • Monday September 30, 2019
      11:00 am - 12:00 pm
  • Location: Klaus 1116 East
  • Phone:
  • URL:
  • Email:
  • Fee(s):
  • Extras:
No contact information submitted.

Summary Sentence: Lagrangian Duality in Mechanism Design - Klaus 1116 East at 11am

Full Summary: No summary paragraph submitted.

ARC/ACO Alumni Colloquium

Nikhil Devanur (Amazon)

Monday, September 30, 2019

Klaus 1116 East- 11:00 am


Title:  Lagrangian Duality in Mechanism Design

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


Speaker's Webpage

Videos of recent talks are available at:

Click here to subscribe to the seminar email list:

Additional Information

In Campus Calendar


Invited Audience
Faculty/Staff, Postdoc, Public, Graduate students, Undergraduate students
No keywords were submitted.
  • Created By: Francella Tonge
  • Workflow Status: Published
  • Created On: Jul 15, 2019 - 3:09pm
  • Last Updated: Sep 25, 2019 - 6:23pm