Title: Reading group: Social welfare in one-sided matchings: Random priority and beyond
Speaker: Søren Kristoffer Stiil Frederisken Aarhus University
Time: 2014-04-22 14:00-2014-04-22 16:00
Venue: FIT 1-222


We study the problem of approximate social welfare maximization (without money) in one-sided matching problems when agents have unrestricted cardinal preferences over a ?nite set of items. Random priority is a very well-known truthful-in-expectation mechanism for the problem. We prove that the approximation ratio of random priority is ?Theta(n^1/2) while no truthful-in-expectation mechanism can achieve an approximation ratio better than O(n^1/2), where n is the number of agents and items. Furthermore, we prove that the approximation ratio of all ordinal (not necessarily truthful-in-expectation) mechanisms is upper bounded by O(n^1/2), indicating that random priority is asymptotically the best truthful-in-expectation mechanism and the best ordinal mechanism for the problem.

Short Bio: