|
| | | | |
| | | |
| Stat |
Members: 3645
Articles: 2'501'711
Articles rated: 2609
20 April 2024 |
|
| | | | |
|
Article overview
| |
|
|
Truthful Facility Assignment with Resource Augmentation: An Exact Analysis of Serial Dictatorship | | Ioannis Caragiannis
; Aris Filos-Ratsikas
; Soren Kristoffer Stiil Frederiksen
; Kristoffer Arnsfelt Hansen
; Zihan Tan
; | | Date: |
25 Feb 2016 | | 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 very well-known mechanism, Serial Dictatorship, and
provide an exact analysis of its performance. Although Serial Dictatorship is a
purely combinatorial mechanism, our analysis uses linear programming; a linear
program expresses its greedy nature as well as the structure of the input, and
finds the input instance that enforces the mechanism have its worst-case
performance. Bounding the objective of the linear program using duality
arguments allows us to compute tight bounds on the approximation ratio. Among
other results, we prove that Serial Dictatorship has approximation ratio
$g/(g-2)$ when the capacities are multiplied by any integer $g geq 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. | | Source: | arXiv, 1602.8023 | | Services: | Forum | Review | PDF | Favorites | |
|
|
No review found.
Did you like this article?
Note: answers to reviews or questions about the article must be posted in the forum section.
Authors are not allowed to review their own article. They can use the forum section.
browser Mozilla/5.0 AppleWebKit/537.36 (KHTML, like Gecko; compatible; ClaudeBot/1.0; +claudebot@anthropic.com)
|
| |
|
|
|
|
News, job offers and information for researchers and scientists:
| |
REGISTER