Abstract
In this talk, we will walk through a case study of how techniques developed to design differentially private algorithms can be brought to bear to design asymptotically dominant strategy truthful mechanisms in large markets, without the need to make any assumptions about the structure of individual preferences. Specifically, we will consider the many-to-one matching problem, and see a mechanism for computing school optimal stable matchings, that makes truthful reporting an approximately dominant strategy for the student side of the market. The approximation parameter becomes perfect at a polynomial rate as the number of students grows large, and the analysis holds even for worst-case preferences for both students and schools. This case study is a special case of a general technique, that has found many applications, and is an invitation to think of more.
Based on joint work with Sampath Kannan, Jamie Morgenstern, and Steven Wu