Fall 2016

A Unified Duality Theory for Bayesian Mechanism Design

Thursday, September 22nd, 2016 11:30 am12:00 pm

Add to Calendar


Calvin Lab Auditorium 

It is well-known by now that the simple mechanisms we see in practice are rarely, if ever, optimal. Recent work within TCS has aimed to understand this through the lens of approximation, and has successfully shown that while virtually never optimal, the simple mechanisms we see in practice are often approximately optimal. Still, the techniques used to prove these claims were setting-specific and therefore limited their applicability to broad settings. In this work, we provide a unified duality theory, and show that all benchmarks used in prior works comes from the same duality approach within our framework. 
In this talk, I'll briefly introduce Bayesian Mechanism Design and its challenges, and overview our duality framework. At the end I will also state some very recent applications of our framework that greatly extend known settings where simple mechanisms are approximately optimal [Cai/Zhao 16], and provide multi-dimensional Bulow-Klemperer results [Eden/Feldman/Friedler/Talgam-Cohen/W. 16]. 
Based on joint work with Yang Cai and Nikhil Devanur.