Social welfare in one-sided matching mechanisms

George Christodoulou, Aris Filos-Ratsikas, Soren Kristoffer Stiil Frederiksen, Paul W. Goldberg, Jie Zhang, Jinshan Zhang

Research output: Chapter or section in a book/report/conference proceedingChapter in a published conference proceeding

8 Citations (SciVal)


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. We show that two well-known mechanisms, Probabilistic Serial, and Random Priority, achieve 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, and show stronger bounds on the Price of Anarchy of all deterministic mechanisms.
Original languageEnglish
Title of host publicationAutonomous Agents and Multiagent Systems
EditorsN. Osman, C. Sierra
PublisherSpringer, Cham; Fondazione C.I.M.E., Florence
Number of pages21
ISBN (Print)978-3-319-46881-5
Publication statusPublished - 24 Sept 2016

Bibliographical note

© 2016 Springer International Publishing AG; AAMAS '16 International Conference on Autonomous Agents and Multiagent Systems, AAMAS '16 ; Conference date: 09-05-2016 Through 13-05-2016

Cite this