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

DOI10.1007/978-3-662-54110-4_17MaRDI QIDQ2959833zbMATH OpenOpenAlexFDO

Authors I. Caragiannis, Aris Filos-Ratsikas, Søren Kristoffer Stiil Frederiksen, Kristoffer Arnsfelt Hansen, Zihan Tan

Publication date 10 February 2017

Published in Web and Internet Economics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1602.08023, https://pure.au.dk/portal/da/publications/truthful-facility-assignment-with-resource-augmentation(649fe64c-d142-4b2c-88d0-2a64d08768db).html

zbMATH Keywords

facility assignmentresource augmentationserial dictatorship

Mathematics Subject Classification ID

Matching models (91B68)

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 $ggeq3$. 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.

Recommendations

• Size versus truthfulness in the house allocation problem
• The capacity constrained facility location problem
• On the power of deterministic mechanisms for facility location games
• Efficiency of truthful and symmetric mechanisms in one-sided matching
• Assignment mechanisms under distributional constraints

Cites work

• A new solution to the random assignment problem.
• Online Weighted Matching
• Random Serial Dictatorship and the Core from Random Endowments in House Allocation Problems
• Social welfare in one-sided matchings: random priority and beyond
• Speed is as powerful as clairvoyance
• Strategy-proof allocation of indivisible goods
• The efficiency of fair division
• The Impossibility of Bayesian Group Decision Making with Separate Aggregation of Beliefs and Values
• The Online Transportation Problem
• The price of matching with metric preferences

Cited in

(5)

• Ordinal approximation for social choice, matching, and facility location problems given candidate positions
• Metric-distortion bounds under limited information
• Truthful Mechanisms for Matching and Clustering in an Ordinal World
• Don’t Roll the Dice, Ask Twice: The Two-Query Distortion of Matching Problems and Beyond
• Optimizing over serial dictatorships

This page was built for publication: Truthful facility assignment with resource augmentation: an exact analysis of serial dictatorship

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2959833)