Truthful facility assignment with resource augmentation: An exact analysis of serial dictatorship

Research output: Contribution to book/anthology/report/proceedingArticle in proceedingsResearchpeer-review

  • Ioannis Caragiannis, Department of Computer Engineering and Informatics, University of Patras
  • ,
  • Aris Filos-Ratsikas, University of Oxford, Oxford
  • ,
  • Søren Kristoffer Stiil Frederiksen
  • ,
  • Kristoffer Arnsfelt Hansen
  • Zihan Tan, University of Chicago, Chicago, Illinois.

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 mostpreferred 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.

Original languageEnglish
Title of host publicationWeb and Internet Economics - 12th International Conference, WINE 2016, Proceedings
Number of pages15
Volume10123
PublisherSpringer VS
Publication year2016
Pages236-250
ISBN (print)9783662541098
DOIs
Publication statusPublished - 2016
EventWINE 2016: The 12th Conference on Web and Internet Economics - Montreal, Canada
Duration: 11 Dec 201614 Dec 2016
http://cs.mcgill.ca/~wine2016/

Conference

ConferenceWINE 2016: The 12th Conference on Web and Internet Economics
LandCanada
ByMontreal
Periode11/12/201614/12/2016
Internetadresse
SeriesLecture Notes in Computer Science
Volume 10123
ISSN0302-9743

See relations at Aarhus University Citationformats

ID: 108472287