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.

我们提出了一种叫做 “强比例” 的概念，可以用来解决设施选址问题。我们证明了一个称为随机排名机制的方法，可以在期望上满足强比例，但是没有确定性的策略证明机制可以满足该性质。最后，我们证明了在强比例的基础上，即使弱化了普遍的真实性，通过减少策略真实性可以达到更强的后验公平保证。