论文标题
欧几里得和曼哈顿空间中设施位置的策略证明机制
Strategy Proof Mechanisms for Facility Location in Euclidean and Manhattan Space
论文作者
论文摘要
我们研究了从一个维度到两个（或更多）维度以及欧几里得或曼哈顿距离的设施位置的机制的影响。我们考虑三个基本的公理特性：匿名性是基本的公平特性，帕累托最优性，它是最重要的效率属性之一，以及确保代理人没有动力错误报告的策略证明。我们还考虑了这种机制如何近似最佳福利。我们的结果有些负面。从一个维度转移到两个（或更多）维度通常会使这些公理特性更难实现。例如，在欧几里得空间中有两个设施，或者在曼哈顿空间中只有一个设施，没有任何机制是匿名，帕累托的最佳和策略证明。相比之下，这三个属性都存在该线上的机制。我们还表明，移动到两个（或更多）维度时近似值可能会增加。我们所有的不可能结果都是最小的。如果我们删除三个公理之一（匿名，帕累托最优性或策略证明），多种机制满足其他两个公理。
We study the impact on mechanisms for facility location of moving from one dimension to two (or more) dimensions and Euclidean or Manhattan distances. We consider three fundamental axiomatic properties: anonymity which is a basic fairness property, Pareto optimality which is one of the most important efficiency properties, and strategy proofness which ensures agents do not have an incentive to mis-report. We also consider how well such mechanisms can approximate the optimal welfare. Our results are somewhat negative. Moving from one dimension to two (or more) dimensions often makes these axiomatic properties more difficult to achieve. For example, with two facilities in Euclidean space or with just a single facility in Manhattan space, no mechanism is anonymous, Pareto optimal and strategy proof. By contrast, mechanisms on the line exist with all three properties.We also show that approximation ratios may increase when moving to two (or more) dimensions. All our impossibility results are minimal. If we drop one of the three axioms (anonymity, Pareto optimality or strategy proofness) multiple mechanisms satisfy the other two axioms.
