We study the Price of Anarchy of mechanisms for the well-known problem of one-sided matching, or house allocation, with respect to the social welfare objective. We consider both ordinal mechanisms, where agents submit preference lists over the items, and cardinal mechanisms, where agents may submit numerical values for the items being allocated. We present a general lower bound of Ω(√n) on the Price of Anarchy, which applies to all mechanisms and we show that a very well-known mechanisms, Probabilistic Serial achieves a matching upper bound. We extend our lower bound to the Price of Stability of a large class of mechanisms that satisfy a common proportionality property.
['George Christodoulou', 'Aris Filos-Ratsikas', 'Søren Kristoffer Stiil Frederiksen', 'Paul W. Goldberg', 'Jie Zhang', 'Jinshan Zhang']
Social Welfare in One-Sided Matching Mechanisms: (Extended Abstract)