Speaker: Yang Cai McGill University
Time: 2016-12-23 10:30-2016-12-23 11:30
Venue: FIT 1-222

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 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.  

​Based on joint work with Nikhil R. Devanur, Matt Weinberg and Mingfei Zhao.​

Short Bio:

Yang Cai is a William Dawson Assistant Professor of Computer Science at McGill University. He received his PhD in computer science from MIT, advised by Costis Daskalakis. He was a postdoctoral researcher in UC Berkeley. Yang’s research interests lie in the area of theoretical computer science, in particular algorithmic game theory, online algorithms and logic. His Ph.D. thesis was honored with the MIT George M. Sprowls dissertation award and the SIGECOM Dissertation Award.