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

研究了在代理人对有限物品具有不受限制的基数偏好时，近似社会福利最大化（无货币）的问题，在此问题中随机优先级是一个非常著名的期望真实机制，证明了随机优先级的近似比率是 Θ（n ^ {-1 / 2}），而没有期望真实机制可以实现比 O（n^{-1/2}）更好的近似比率。此外，证明了所有序数（不一定是期望真实的）机制的近似比率都是 O（n^{-1/2}），表明随机优先级是问题的渐近最好的期望真实机制和最好的序数机制。