News & Events

CS seminar series - Jie Zhang

CS seminar series presents

Social Welfare in One-Sided Matchings: Game Analysis, Mechanism Design, and Applications

by Jie Zhang

Monday, May 2 at 14:30 in 205

Abstract:

We study the problem of approximate social welfare maximization (without money) in one-sided matching problems when agents have unrestricted cardinal preferences over a finite set of items. From the mechanism design perspective, we show that the folklore mechanism Random Priority is asymptotically the best truthful-in-expectation mechanism and the best ordinal mechanism for the problem. From the game analysis perspective, we present a general lower bound of $\Omega(\sqrt{n})$ on the Price of Anarchy, which applies to all mechanisms and we show that the  Probabilistic Serial protocol achieves a matching upper bound. We discuss some applications and extensions of the problem. 

About speaker: 

Jie Zhang got his PhD in Computer Science from City University of Hong Kong, advised by Xiaotie Deng. During PhD, he visited Yiling Chen at Harvard. After that he joined CTIC (led by Peter Bro Miltersen) at Aarhus University as a postdoc. Currently he is a postdoc at Oxford University, working with Elias Koutsoupias.