- Authors:
- Editor:
- Lavi, Ron
- DOI:
- 10.1007/978-3-662-44803-8_1
- Abstract:
- 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 Theta(n^{-1/2}) while no truthful-in-expectation mechanism can achieve an approximation ratio better than O(n^{-1/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^{-1/2}), indicating that random priority is asymptotically the best truthful-in-expectation mechanism and the best ordinal mechanism for the problem.
- ISBN:
- 9783662448021, 9783662448038
- Type:
- Conference paper
- Language:
- English
- Published in:
- Lecture Notes in Computer Science: 7th International Symposium, Sagt 2014, Proceedings, 2014, p. 1-12
- Main Research Area:
- Science/technology
- Series:
- Lecture Notes in Computer Science
- Conference:
- Symposium on Algorithmic Game TheorySymposium on Algorithmic Game Theory, 2014
- Publisher:
- Springer-VS
- Submission year:
- 2014
- ID:
- 2150782656
Checking for on-site access...
