The capacity constrained facility location problem

Abstract

We initiate the study of the capacity constrained facility location problem from a mechanism design perspective. In the capacity constrained setting, the facility can serve only a subset of the population, assumed to be the k-closest with respect to agents' true locations (this can be justified as the essentially unique equilibrium outcome of a first-come-first game induced by the facility location). The main result is a complete characterization of dominant-strategy incentive compatible (DIC) mechanisms via the family of generalized median mechanisms (GMMs). Thus, the framework we introduce surprisingly provides a new characterization of GMMs, and is responsive to gaps in the current social choice literature highlighted by Border and Jordan (1983) and Barberà et al. (1998). We also provide algorithmic results and study the performance of DIC mechanisms in optimizing welfare. Adopting a worst-case approximation measure, we attain tight lower bounds on the approximation ratio of any DIC mechanism.