Skip to content. Skip to navigation
CIM Menus

Informal Systems Seminar (ISS) - Centre for Intelligent Machines (CIM) and Groupe d'Etudes et de Recherche en Analyse des Decisions (GERAD)

Algorithmic Bayesian Mechanism Design

Yang Cai, Assistant Professor
School of Computer Science McGill University

March 20, 2015 at  10:30 AM
McConnell Engineering Room 320

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, e.g. makespan minimization with strategic machines and fair resource allocation.