Social Welfare in One-Sided Matchings: Random Priority and Beyond

Aris Filos-Ratsikas, Søren Kristoffer Stiil Frederiksen, Jie Zhang

Research output: Chapter in Book/Report/Conference proceedingConference contribution


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 $(n−thinspace1/2) while no truthful-in-expectation mechanism can achieve an approximation ratio better than O(n−thinspace1/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−thinspace1/2), indicating that random priority is asymptotically the best truthful-in-expectation mechanism and the best ordinal mechanism for the problem.
Original languageEnglish
Title of host publicationAlgorithmic Game Theory: 7th International Symposium, SAGT 2014, Haifa, Israel, September 30 -- October 2, 2014, Proceedings
EditorsRon Lavi
Place of PublicationBerlin, Heidelberg
PublisherSpringer Berlin Heidelberg
Number of pages12
ISBN (Electronic)978-3-662-44803-8
ISBN (Print)978-3-662-44802-1
Publication statusPublished - 5 Sep 2014
EventThe 7th International Symposium on Algorithmic Game Theory, 2014 - Haifa, Israel
Duration: 30 Sep 20142 Oct 2014
Conference number: 7

Publication series

NameLecture Notes in Computer Science
PublisherSpringer Berlin, Heidelberg
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349


SymposiumThe 7th International Symposium on Algorithmic Game Theory, 2014
Abbreviated titleSAGT 2014

Cite this