TY - GEN

T1 - Social welfare in one-sided matchings: random priority and beyond

AU - Filos-Ratsikas, Aris

AU - Frederiksen, Soren Kristoffer Stiil

AU - Zhang, Jie

PY - 2014

Y1 - 2014

N2 - 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 O(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.

AB - 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 O(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.

U2 - 10.1007/978-3-662-44803-8_1

DO - 10.1007/978-3-662-44803-8_1

M3 - Chapter in a published conference proceeding

SN - 978-3-662-44802-1

VL - 8768

T3 - Lecture Notes in Computer Science

SP - 1

EP - 12

BT - Algorithmic Game Theory

A2 - Lavi, R

PB - Springer

CY - Switzerland

ER -