Random Rank: The One and Only Strategyproof and Proportionally Fair Randomized Facility Location Mechanism
This work addresses fairness and incentive issues in social choice problems like facility location, offering a novel randomized solution with theoretical guarantees, though it is incremental in extending existing fairness concepts.
The paper tackles the problem of designing a fair and strategyproof randomized mechanism for facility location by introducing Strong Proportionality, which ensures equal total cost for groups at different locations, and proves that Random Rank is the unique mechanism satisfying universal truthfulness, anonymity, and this property in expectation.
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.