论文标题
随机等级：唯一的，也是唯一的战略性和成比例公平的随机设施位置机制
Random Rank: The One and Only Strategyproof and Proportionally Fair Randomized Facility Location Mechanism
论文作者
论文摘要
相称性是一个有吸引力的公平概念，已应用于一系列问题，包括设施位置问题，这是社会选择中的经典问题。在我们的工作中，我们提出了一个称为强比例的概念，该概念可确保当不同位置有两组代理时，两组都会产生相同的总成本。我们表明，尽管强度比例是一个充分动机且基本的公理，但没有确定性的策略性防护机制来满足该财产。然后，我们确定一种称为随机等级的随机机制（该机制均匀地选择了$ k $在$ 1 $到$ n $之间的数字$ k $，并在$ k $'的第一个最高代理位置定位该设施，可以满足预期的强大比例。我们的主要定理将随机级别描述为实现普遍真实，普遍匿名性和强烈比例性在所有随机机制中的独特机制。最后，我们通过平均范围的机制表明，通过削弱对预期战略防止的真实性，可以实现更强大的前柱公平保证。
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.
