# Equitable Mechanism Design for Facility Location

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 11 of its 29 references that are in the map.
- First posted on arXiv 12 Jun 2025.

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

- [Mechanism Design for Facility Location Problems: A Survey](https://mlsanity.com/paper/2106.03457/) (2021)
- [Strategyproof and Proportionally Fair Facility Location](https://mlsanity.com/paper/2111.01566/) (2021)
- [Strategyproof Mechanisms for One-Dimensional Hybrid and Obnoxious Facility Location](https://mlsanity.com/paper/1412.3414/) (2014)
- [Optimality of the coordinate-wise median mechanism for strategyproof facility location in two dimensions](https://mlsanity.com/paper/2007.00903/) (2020)
- [Strategy Proof Mechanisms for Facility Location at Limited Locations](https://mlsanity.com/paper/2009.07982/) (2020)
- [Strategy Proof Mechanisms for Facility Location with Capacity Limits](https://mlsanity.com/paper/2009.07986/) (2020)
- [Mechanism Design for Facility Location Games with Candidate Locations](https://mlsanity.com/paper/2010.09640/) (2020)
- [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)
- [A Survey on Approximation Mechanism Design without Money for Facility Games](https://mlsanity.com/paper/1503.07426/) (2015)
- [Nash Welfare and Facility Location](https://mlsanity.com/paper/2310.04102/) (2023)

## Abstract (arXiv)

We consider strategy proof mechanisms for facility location which maximize equitability between agents. As is common in the literature, we measure equitability with the Gini index. We first prove a simple but fundamental impossibility result that no strategy proof mechanism can bound the approximation ratio of the optimal Gini index of utilities for one or more facilities. We propose instead computing approximation ratios of the complemented Gini index of utilities, and consider how well both deterministic and randomized mechanisms approximate this. In addition, as Nash welfare is often put forwards as an equitable compromise between egalitarian and utilitarian outcomes, we consider how well mechanisms approximate the Nash welfare.