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 @math when the capacities are multiplied by any integer @math . 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.
@cite_24: We present the first poly-logarithmic competitive online algorithm for minimum metric bipartite matching. Via induction and a careful use of potential functions, we show that a simple randomized greedy algorithm is competitive on a hierarchically separated tree. Application of recent results on randomized embedding of metrics into trees yield the poly-logarithmic result for general metrics.
@cite_2: We study the online transportation problem under the assumption that the adversary has only half as many servers at each site as the online algorithm. We show that the GREEDY algorithm is @math -competitive under this assumption, where m is the number of server sites and C is the total number of servers. We then present an algorithm BALANCE, which is a simple modification of the GREEDY algorithm, that is, O(1)-competitive under this assumption.
Most closely related to our problem is the @cite_2 @cite_24 (also known as the minimum online metric bipartite matching). In particular, as we explain in Section of the Appendix, results about the greedy algorithm in the online transportation problem imply bounds for the facility assignment problem. However, contrary to @cite_2 , our analysis is , i.e. our results involve no asymptotics. Furthermore, compared to the related result in @cite_2 , we remark that our analysis is substantially different due to the use of linear programming; our primal-dual technique could be applicable for greedy assignment mechanisms on other resource augmentation settings, beyond the specific problem.