论文标题
分布式设施位置的近似机制设计
Approximate mechanism design for distributed facility location
论文作者
论文摘要
我们考虑了一个单一的位置问题，其中代理位于实际线路上，并将其划分为多个不相交的地区。目的是选择一个位置（要建造公共设施），以最大程度地减少代理商的总距离。该过程分布：每个地区的代理商的位置首先汇总到该地区的代表位置，然后选择一个地区代表作为设施位置。这种间接进入代理位置不可避免地会导致效率低下，这是由于失真概念所捕获的。我们研究了该问题的离散版本，其中替代位置是有限的，以及连续的位置，其中每个点都是替代方案，并几乎完整地描绘了一般和策略性防护分布式机制的失真景观。
We consider a single-facility location problem, where agents are positioned on the real line and are partitioned into multiple disjoint districts. The goal is to choose a location (where a public facility is to be built) so as to minimize the total distance of the agents from it. This process is distributed: the positions of the agents in each district are first aggregated into a representative location for the district, and then one of the district representatives is chosen as the facility location. This indirect access to the positions of the agents inevitably leads to inefficiency, which is captured by the notion of distortion. We study the discrete version of the problem, where the set of alternative locations is finite, as well as the continuous one, where every point of the line is an alternative, and paint an almost complete picture of the distortion landscape of both general and strategyproof distributed mechanisms.
