Conference icon

Conference

Social welfare in one-sided matchings: Random priority and beyond.

Abstract:

We study the problem of approximate social welfare maximization (without money) in onesided 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 Θ(n1=2) while no truthful-in-expectation mechanism can achieve an approximation ratio better than O(n1=2), where n is the number of agents and items. Furthermor...

Expand abstract
Publication status:
Published
Peer review status:
Peer reviewed
Version:
Accepted manuscript

Actions


Access Document


Files:
Publisher copy:
10.1007/978-3-662-44803-8_1

Authors


More by this author
Institution:
University of Oxford
Department:
Oxford, MPLS, Computer Science
Role:
Author

Contributors

Role:
Editor
Center for Research in Foundations of Electronic Markets More from this funder
Publisher:
Springer Verlag Publisher's website
Volume:
abs/1403.1508
Pages:
1-12
Publication date:
2014-10-05
DOI:
EISSN:
1611-3349
URN:
uuid:3f94eb43-1ea6-4bfc-ad3e-597978c90968
Source identifiers:
578433
Local pid:
pubs:578433
ISBN:
978-3-662-44802-1

Terms of use


Metrics


Views and Downloads






If you are the owner of this record, you can report an update to it here: Report update to this record

TO TOP