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:
-
-
(Accepted manuscript, pdf, 328.4KB)
-
- Publisher copy:
- 10.1007/978-3-662-44803-8_1
Funding
+ European Research Council
More from this funder
Funding agency for:
Zhang, J
Grant:
Advanced Grant 321171 (ALGAME
321171
Center for Research in Foundations of Electronic Markets
More from this funder
Bibliographic Details
- Publisher:
- Springer Verlag Publisher's website
- Host title:
- SAGT 2014: 7th International Symposium on Algorithmic Game Theory
- Volume:
- abs/1403.1508
- Pages:
- 1-12
- Publication date:
- 2014-10-01
- DOI:
- EISSN:
-
1611-3349
- ISBN:
- 9783662448021
Item Description
- Pubs id:
-
pubs:578433
- UUID:
-
uuid:3f94eb43-1ea6-4bfc-ad3e-597978c90968
- Local pid:
- pubs:578433
- Source identifiers:
-
578433
- Deposit date:
- 2016-02-10
Terms of use
- Copyright holder:
- Springer Verlag
- Copyright date:
- 2014
- Notes:
- © Springer-Verlag Berlin Heidelberg 2014. Published by Springer Verlag in Lecture Notes on Computer Science as the proceedings of SAGT 2014: 7th International Symposium on Algorithmic Game Theory. This is the accepted manuscript version of the article. The final version is available online from Springer at: [10.1007/978-3-662-44803-8_1]
Metrics
If you are the owner of this record, you can report an update to it here: Report update to this record