Truthful facility assignment with resource augmentation: an exact analysis of serial dictatorship
Author(s)
Caragiannis, Ioannis
Filos-Ratsikas, Aris
Frederiksen, Søren Kristoffer Stiil
Hansen, Kristoffer Arnsfelt
Tan, Zihan
Type
Journal Article
Abstract
<jats:title>Abstract</jats:title><jats:p>We study the<jats:italic>truthful facility assignment</jats:italic>problem, where a set of agents with private most-preferred points on a metric space have to be 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<jats:italic>resource augmentation framework</jats:italic>, 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<jats:inline-formula><jats:alternatives><jats:tex-math>$$g/(g-2)$$</jats:tex-math><mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mrow><mml:mi>g</mml:mi><mml:mo>/</mml:mo><mml:mo>(</mml:mo><mml:mi>g</mml:mi><mml:mo>-</mml:mo><mml:mn>2</mml:mn><mml:mo>)</mml:mo></mml:mrow></mml:math></jats:alternatives></jats:inline-formula>when the capacities are multiplied by any integer<jats:inline-formula><jats:alternatives><jats:tex-math>$$g \ge 3$$</jats:tex-math><mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mrow><mml:mi>g</mml:mi><mml:mo>≥</mml:mo><mml:mn>3</mml:mn></mml:mrow></mml:math></jats:alternatives></jats:inline-formula>. Our results suggest that with a limited augmentation of the resources we can achieve exponential improvements 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.</jats:p>
Date Issued
2024-01
Citation
Mathematical Programming, 2024, 203 (1-2), pp.901-930
ISSN
0025-5610
Publisher
Springer Science and Business Media LLC
Start Page
901
End Page
930
Journal / Book Title
Mathematical Programming
Volume
203
Issue
1-2
Publication Status
Published
Date Publish Online
2022-11-02