Abstract / Description of output
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 language | English |
---|---|
Title of host publication | Algorithmic Game Theory: 7th International Symposium, SAGT 2014, Haifa, Israel, September 30 -- October 2, 2014, Proceedings |
Editors | Ron Lavi |
Place of Publication | Berlin, Heidelberg |
Publisher | Springer |
Pages | 1-12 |
Number of pages | 12 |
ISBN (Electronic) | 978-3-662-44803-8 |
ISBN (Print) | 978-3-662-44802-1 |
DOIs | |
Publication status | Published - 5 Sept 2014 |
Event | The 7th International Symposium on Algorithmic Game Theory, 2014 - Haifa, Israel Duration: 30 Sept 2014 → 2 Oct 2014 Conference number: 7 |
Publication series
Name | Lecture Notes in Computer Science |
---|---|
Publisher | Springer Berlin, Heidelberg |
Volume | 8768 |
ISSN (Print) | 0302-9743 |
ISSN (Electronic) | 1611-3349 |
Symposium
Symposium | The 7th International Symposium on Algorithmic Game Theory, 2014 |
---|---|
Abbreviated title | SAGT 2014 |
Country/Territory | Israel |
City | Haifa |
Period | 30/09/14 → 2/10/14 |