# Strategyproof and Proportionally Fair Facility Location

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

## Key facts

- Cited by 6 papers in the map (data through 14 Oct 2026).
- Builds on 11 of its 82 references that are in the map.
- First posted on arXiv 2 Nov 2021.

## Builds on (most cited first, 11 of 11)

- [Justified Representation in Approval-Based Committee Voting](https://mlsanity.com/paper/1407.8269/) (2014)
- [Proportional Justified Representation](https://mlsanity.com/paper/1611.09928/) (2016)
- [Mechanism Design for Facility Location Problems: A Survey](https://mlsanity.com/paper/2106.03457/) (2021)
- [Fair mixing: the case of dichotomous preferences](https://mlsanity.com/paper/1712.02542/) (2017)
- [On Voting and Facility Location](https://mlsanity.com/paper/1512.05868/) (2015)
- [Truthful Aggregation of Budget Proposals](https://mlsanity.com/paper/1905.00457/) (2019)
- [Facility Location Problem with Capacity Constraints: Algorithmic and Mechanism Design Perspectives](https://mlsanity.com/paper/1911.09813/) (2019)
- [The Capacity Constrained Facility Location problem](https://mlsanity.com/paper/1806.00960/) (2018)
- [Strategyproof Mechanisms For Group-Fair Facility Location Problems](https://mlsanity.com/paper/2107.05175/) (2021)
- [A characterization of proportionally representative committees](https://mlsanity.com/paper/2002.09598/) (2020)
- [New Characterizations of Strategy-Proofness under Single-Peakedness](https://mlsanity.com/paper/2102.11686/) (2021)

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

- [Random Rank: The One and Only Strategyproof and Proportionally Fair Randomized Facility Location Mechanism](https://mlsanity.com/paper/2205.14798/) (2022)
- [Proportional Fairness in Obnoxious Facility Location](https://mlsanity.com/paper/2301.04340/) (2023)
- [Optimizing Multiple Simultaneous Objectives for Voting and Facility Location](https://mlsanity.com/paper/2212.03467/) (2022)
- [Facility Location Games with Scaling Effects](https://mlsanity.com/paper/2402.18908/) (2024)
- [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 focus on a simple, one-dimensional collective decision problem (often referred to as the facility location problem) and explore issues of strategyproofness and proportionality-based fairness. We introduce and analyze a hierarchy of proportionality-based fairness axioms of varying strength: Individual Fair Share (IFS), Unanimous Fair Share (UFS), Proportionality (as in Freeman et al, 2021), and Proportional Fairness (PF). For each axiom, we characterize the family of mechanisms that satisfy the axiom and strategyproofness. We show that imposing strategyproofness renders many of the axioms to be equivalent: the family of mechanisms that satisfy proportionality, unanimity, and strategyproofness is equivalent to the family of mechanisms that satisfy UFS and strategyproofness, which, in turn, is equivalent to the family of mechanisms that satisfy PF and strategyproofness. Furthermore, there is a unique such mechanism: the Uniform Phantom mechanism, which is studied in Freeman et al. (2021). We also characterize the outcomes of the Uniform Phantom mechanism as the unique (pure) equilibrium outcome for any mechanism that satisfies continuity, strict monotonicity, and UFS. Finally, we analyze the approximation guarantees, in terms of optimal social welfare and minimum total cost, obtained by mechanisms that are strategyproof and satisfy each proportionality-based fairness axiom. We show that the Uniform Phantom mechanism provides the best approximation of the optimal social welfare (and also minimum total cost) among all mechanisms that satisfy UFS.