Mechanism Design for Facility Location Problems with Capacity Constraints in Bounded Location Space

We consider the k-facility location problems with capacity constraints in bounded location space from the mechanism design perspective. In this problem, we seek to locate k capacity constrained facilities in a bounded interval (i.e., B=[bl,br]) to serve agents, who have preferences on the ideal locations of the facilities in the interval. Our goal is to design strategyproof mechanisms to elicit agents' true ideal locations and locate facilities that minimize the social cost and maximum cost, which are defined to be the sum and the maximum of the agents' costs (i.e., agents' distances to their facilities), respectively. For the equal capacity setting without spare capacity (i.e., all the agents can be served exactly), we provide a deterministic strategyproof mechanism. For any bounded interval (i.e., bl, br?R), our mechanism has approximation ratios of n-1 for the social cost and 4 for the maximum cost with k≥3 facilities and n≥3 agents. We also establish lower bounds of n/2 for the social cost by a common class of deterministic mechanisms that order agents from left to right, and 2 for the maximum cost by any deterministic mechanism. Our mechanism also achieves tight bounds for both costs with k<3 facilities. We then consider the equal capacity setting with spare capacity and the arbitrary capacity setting without spare capacity. For these two settings and any bounded interval, we provide randomized strategyproof mechanisms with approximation ratios of n/2 for the social cost and 2 for the maximum cost with any number of facilities. We complement this result by establishing lower bounds of 5/3 for the social cost and 3/2 for the maximum cost.