Conference item icon

Conference item

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

Actions


Access Document


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

Authors


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

Contributors

Role:
Editor
More from this funder
Funding agency for:
Zhang, J
Grant:
Advanced Grant 321171 (ALGAME
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
Host title:
SAGT 2014: 7th International Symposium on Algorithmic Game Theory
Publication date:
2014-10-01
DOI:
EISSN:
1611-3349
Source identifiers:
578433
ISBN:
9783662448021
Pubs id:
pubs:578433
UUID:
uuid:3f94eb43-1ea6-4bfc-ad3e-597978c90968
Local pid:
pubs:578433
Deposit date:
2016-02-10

Terms of use


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