  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.
