The capacity constrained facility location problem

Haris Aziz, Hau Chan, Barton Lee and David C. Parkes

Games and Economic Behavior, 2020, vol. 124, issue C, 478-490

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.

Keywords: Facility location; Median mechanisms; Strategy-proofness; Characterization; Worst-case approximation (search for similar items in EconPapers)
Date: 2020
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (4)

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0899825620301317
Full text for ScienceDirect subscribers only

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:eee:gamebe:v:124:y:2020:i:c:p:478-490

DOI: 10.1016/j.geb.2020.09.001

Access Statistics for this article

Games and Economic Behavior is currently edited by E. Kalai

More articles in Games and Economic Behavior from Elsevier
Bibliographic data for series maintained by Catherine Liu ().