# Mechanism Design for Facility Location Games with Candidate Locations

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

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 19 Oct 2020.

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

- [Optimizing Multiple Simultaneous Objectives for Voting and Facility Location](https://mlsanity.com/paper/2212.03467/) (2022)
- [Equitable Mechanism Design for Facility Location](https://mlsanity.com/paper/2506.10460/) (2025)
- [Mechanism Design for Facility Location using Predictions](https://mlsanity.com/paper/2508.03818/) (2025)

## Abstract (arXiv)

We study the facility location games with candidate locations from a mechanism design perspective. Suppose there are n agents located in a metric space whose locations are their private information, and a group of candidate locations for building facilities. The authority plans to build some homogeneous facilities among these candidates to serve the agents, who bears a cost equal to the distance to the closest facility. The goal is to design mechanisms for minimizing the total/maximum cost among the agents. For the single-facility problem under the maximum-cost objective, we give a deterministic 3-approximation group strategy-proof mechanism, and prove that no deterministic (or randomized) strategy-proof mechanism can have an approximation ratio better than 3 (or 2). For the two-facility problem on a line, we give an anonymous deterministic group strategy-proof mechanism that is (2n-3)-approximation for the total-cost objective, and 3-approximation for the maximum-cost objective. We also provide (asymptotically) tight lower bounds on the approximation ratio.