A Duality Based Framework for Designing Simple Mechanisms

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 relatively similar, the techniques employed in these results are completely different and seemed 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, i.e. multiple buyers with XOS valuations.