Conference item
Truthful facility assignment with resource augmentation: an exact analysis of serial dictatorship
- Abstract:
-
We study the truthful facility assignment problem, where a set of agents with private most-preferred points on a metric space are assigned to facilities that lie on the metric space, under capacity constraints on the facilities. The goal is to produce such an assignment that minimizes the social cost, i.e., the total distance between the most-preferred points of the agents and their corresponding facilities in the assignment, under the constraint of truthfulness, which ensures that agents do not misreport their most-preferred points.
We propose a resource augmentation framework, where a truthful mechanism is evaluated by its worst-case performance on an instance with enhanced facility capacities against the optimal mechanism on the same instance with the original capacities. We study a well-known mechanism, Serial Dictatorship, and provide an exact analysis of its performance.
Among other results, we prove that Serial Dictatorship has approximation ratio g/(g − 2) when the capacities are multiplied by any integer g ≥ 3. Our results suggest that even a limited augmentation of the resources can have wondrous effects on the performance of the mechanism and in particular, the approximation ratio goes to 1 as the augmentation factor becomes large. We complement our results with bounds on the approximation ratio of Random Serial Dictatorship, the randomized version of Serial Dictatorship, when there is no resource augmentation.
- Publication status:
- Published
- Peer review status:
- Peer reviewed
Actions
Access Document
- Files:
-
-
(Preview, Accepted manuscript, pdf, 306.7KB, Terms of use)
-
- Publisher copy:
- 10.1007/978-3-662-54110-4_17
Authors
- Funding agency for:
- Filos-Ratsikas, A
- Grant:
- 61361136003
- Funding agency for:
- Filos-Ratsikas, A
- Grant:
- 61361136003
- Funding agency for:
- Filos-Ratsikas, A
- Grant:
- 61361136003
- Funding agency for:
- Filos-Ratsikas, A
- Grant:
- 61361136003
- Publisher:
- Springer
- Host title:
- International Conference on Web and Internet Economics: WINE 2016: Web and Internet Economics
- Journal:
- International Conference on Web and Internet Economics More from this journal
- Volume:
- 10123
- Pages:
- 236-250
- Series:
- Lecture Notes in Computer Science
- Publication date:
- 2016-12-01
- Acceptance date:
- 2016-09-24
- Event location:
- Montreal, Canada
- DOI:
- ISSN:
-
0302-9743
- ISBN:
- 9783662541098
- Pubs id:
-
pubs:628617
- UUID:
-
uuid:e3767bc4-fc99-4465-af64-3fa66873ca4b
- Local pid:
-
pubs:628617
- Source identifiers:
-
628617
- Deposit date:
-
2016-11-08
Terms of use
- Copyright holder:
- Springer-Verlag GmbH Germany
- Copyright date:
- 2016
- Notes:
- Copyright © Springer-Verlag GmbH Germany 2016. This is the accepted manuscript version of the article. The final version is available online from Springer at: https://doi.org/10.1007/978-3-662-54110-4_17
If you are the owner of this record, you can report an update to it here: Report update to this record