# Random Rank: The One and Only Strategyproof and Proportionally Fair Randomized Facility Location Mechanism

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

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- Builds on 12 of its 49 references that are in the map.
- First posted on arXiv 30 May 2022.

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

- [Justified Representation in Approval-Based Committee Voting](https://mlsanity.com/paper/1407.8269/) (2014)
- [Proportional Participatory Budgeting with Additive Utilities](https://mlsanity.com/paper/2008.13276/) (2020)
- [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)
- [Strategyproof and Proportionally Fair Facility Location](https://mlsanity.com/paper/2111.01566/) (2021)
- [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)
- [Improved Truthful Mechanisms for Combinatorial Auctions with Submodular Bidders](https://mlsanity.com/paper/1911.02716/) (2019)
- [A Probabilistic Approach to Voting, Allocation, Matching, and Coalition Formation](https://mlsanity.com/paper/2002.10171/) (2020)

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

- [Proportional Fairness in Obnoxious Facility Location](https://mlsanity.com/paper/2301.04340/) (2023)
- [A Note on Bias to Complete](https://mlsanity.com/paper/2402.11710/) (2024)
- [Equitable Mechanism Design for Facility Location](https://mlsanity.com/paper/2506.10460/) (2025)

## Abstract (arXiv)

Proportionality is an attractive fairness concept that has been applied to a range of problems including the facility location problem, a classic problem in social choice. In our work, we propose a concept called Strong Proportionality, which ensures that when there are two groups of agents at different locations, both groups incur the same total cost. We show that although Strong Proportionality is a well-motivated and basic axiom, there is no deterministic strategyproof mechanism satisfying the property. We then identify a randomized mechanism called Random Rank (which uniformly selects a number k between 1 to n and locates the facility at the k'th highest agent location) which satisfies Strong Proportionality in expectation. Our main theorem characterizes Random Rank as the unique mechanism that achieves universal truthfulness, universal anonymity, and Strong Proportionality in expectation among all randomized mechanisms. Finally, we show via the AverageOrRandomRank mechanism that even stronger ex-post fairness guarantees can be achieved by weakening universal truthfulness to strategyproofness in expectation.