Mechanism Design: A New Algorithmic Framework

In his seminal paper, Myerson [1981] provides a revenue-optimal auction for a seller who is looking to sell a single item to multiple bidders. Extending this auction to simultaneously selling multiple heterogeneous items has been one of the central problems in Mathematical Economics. We provide such an extension that is also computationally efficient. Our solution proposes a novel framework for mechanism design by reducing mechanism design problems (where one optimizes an objective function on 'rational inputs') to algorithm design problems (where one optimizes an objective function on 'honest inputs'). Our reduction is generic and provides a framework for many other mechanism design problems. In the end of my talk, I will also briefly overview some of my other work, including algorithmic pricing, generalization of the Min-max theorem for multiplayer games and online matching.

©2013 Microsoft Corporation. All rights reserved.
  • SpeakerYang Cai
  • HostNicole Immorlica
  • AffiliationMIT
  • Duration00:52:58
  • Date recorded25 January 2013
  • Share
    Share this page on Facebook
    Share this page on Twitter
    Share this page on LinkedIn
    E-mail this page
    RSS feeds