Truthful Facility Assignment with Resource Augmentation: An Exact Analysis of Serial Dictatorship

Ioannis Caragiannis, Aris Filos-Ratsikas*, Søren Kristoffer Stiil Frederiksen, Kristoffer Arnsfelt Hansen, Zihan Tan

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

Abstract

We study the truthful facility assignment problem, where a set of agents with private mostpreferred 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 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 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.
Original languageEnglish
Number of pages27
JournalMathematical Programming, Series B
Early online date2 Nov 2022
DOIs
Publication statusE-pub ahead of print - 2 Nov 2022

Keywords

  • Mechanism design without money
  • Serial dictatorship
  • Resource augmentation
  • Approximation ratio

Fingerprint

Dive into the research topics of 'Truthful Facility Assignment with Resource Augmentation: An Exact Analysis of Serial Dictatorship'. Together they form a unique fingerprint.

Cite this