# The Capacity Constrained Facility Location problem

arXiv: https://arxiv.org/abs/1806.00960 · HTML: https://mlsanity.com/paper/1806.00960/

## Key facts

- Cited by 5 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 4 Jun 2018.

## Built on by (most cited first, 5 of 5)

- [Strategyproof and Proportionally Fair Facility Location](https://mlsanity.com/paper/2111.01566/) (2021)
- [Random Rank: The One and Only Strategyproof and Proportionally Fair Randomized Facility Location Mechanism](https://mlsanity.com/paper/2205.14798/) (2022)
- [Nash Welfare and Facility Location](https://mlsanity.com/paper/2310.04102/) (2023)
- [Facility Location Games Beyond Single-Peakedness: the Entrance Fee Model](https://mlsanity.com/paper/2204.11282/) (2022)
- [Facility Location Games with Scaling Effects](https://mlsanity.com/paper/2402.18908/) (2024)

## Abstract (arXiv)

We initiate the study of the capacity constrained facility location problem from a mechanism design perspective. The capacity constrained setting leads to a new strategic environment where a facility serves a subset of the population, which is endogenously determined by the ex-post Nash equilibrium of an induced subgame and is not directly controlled by the mechanism designer. Our focus is on mechanisms that are ex-post dominant-strategy incentive compatible (DIC) at the reporting stage. We provide a complete characterization of DIC mechanisms via the family of Generalized Median Mechanisms (GMMs). In general, the social welfare optimal mechanism is not DIC. Adopting the worst-case approximation measure, we attain tight lower bounds on the approximation ratio of any DIC mechanism. The well-known median mechanism is shown to be optimal among the family of DIC mechanisms for certain capacity ranges. Surprisingly, the framework we introduce provides a new characterization for the family of GMMs, and is responsive to gaps in the current social choice literature highlighted by Border and Jordan (1983) and Barbar`a, Mass'o and Serizawa (1998).