Social welfare in one-sided matchings: Random priority and beyond.

We study the problem of approximate social welfare maximization (without money) in onesided matching problems when agents have unrestricted cardinal preferences over a finite 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 Θ(n1=2) while no truthful-in-expectation mechanism can achieve an approximation ratio better than O(n1=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(n1=2), indicating that random priority is asymptotically the besttruthful-in-expectation mechanism and the best ordinal mechanism for the problem