The capacity constrained facility location problem

• 成果类型: Article
• 署名作者: Aziz, Haris; Chan, Hau; Lee, Barton E.; Parkes, David C.
• 署名单位: University of New South Wales Sydney; Commonwealth Scientific & Industrial Research Organisation (CSIRO); University of Nebraska System; University of Nebraska Lincoln; Harvard University
• 刊物名称: GAMES AND ECONOMIC BEHAVIOR
• ISSN/ISSBN: 0899-8256
• DOI: 10.1016/j.geb.2020.09.001
• 发表日期: 2020
• 页码: 478-490
• 关键词: Facility location; Median mechanisms; strategy-proofness; characterization; Worst-case approximation

摘要

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 Barbera 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. (c) 2020 Elsevier Inc. All rights reserved.