A Duality Based Framework for Designing Simple Mechanisms

  • Yang Cai | McGill University

A central theme in mechanism design is understanding the tradeoff between simplicity and optimality of the designed mechanism. An important and challenging task here is to design simple multi-item mechanisms that can approximately optimize the revenue, as the revenue-optimal mechanisms are known to be extremely complex and thus hard to implement. Recently, we have witnessed several breakthroughs on this front obtaining simple and approximately optimal mechanisms when the buyers have unit-demand (Chawla et. al. ’10) or additive (Yao ’15) valuations. Although these two settings are highly similar, the techniques employed in these results are completely different and difficult to extend to more general settings. In this talk, I will present a principled approach to design simple and approximately optimal mechanisms based on duality theory. Our approach unifies and improves both of the aforementioned results, and extends these simple mechanisms to broader settings. Based on joint work with Nikhil R. Devanur, Matt Weinberg and Mingfei Zhao.

Series: Microsoft Research Talks