Abstract
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 (improving the approximation ratio from 33.75 to 24 for unit-demand buyers and 69 to 8 for additive buyers). I will also mention several new extensions to broader settings obtained using our duality-based approach.
Based on joint work with Nikhil R. Devanur, Matt Weinberg and Mingfei Zhao.
Time
2016-07-13 10:00 ~ 11:00Speaker
Yang Cai, McGill UniversityRoom
Room 308,School of Information Management & Engineering, Shanghai University of Finance & Economics
