论文标题
设施的机理设计与候选位置的位置游戏
Mechanism Design for Facility Location Games with Candidate Locations
论文作者
论文摘要
我们从机制设计的角度研究了具有候选位置的设施位置游戏。假设有n个代理位于公制空间中，其位置是其私人信息，以及建筑设施的一组候选人位置。当局计划在这些候选人之间建立一些同质设施，以服务代理商，他们的成本等于距离最接近设施的距离。目的是设计用于最大程度地减少代理商中总成本/最高成本的机制。对于最大成本目标下的单官方问题，我们给出了确定性的3-抗抗性组防策略机制，并证明没有确定性（或随机）防止策略机制的近似值比3（或2）更好。对于一条线上的两个实现问题，我们给出了一个匿名确定性的群体防策略机制，即（2n-3） - 总成本目标的APPRXIMATION，以及最大成本目标的3- APPRXIMATION。我们还（渐近地）在近似比（渐近）紧密的下限。
We study the facility location games with candidate locations from a mechanism design perspective. Suppose there are n agents located in a metric space whose locations are their private information, and a group of candidate locations for building facilities. The authority plans to build some homogeneous facilities among these candidates to serve the agents, who bears a cost equal to the distance to the closest facility. The goal is to design mechanisms for minimizing the total/maximum cost among the agents. For the single-facility problem under the maximum-cost objective, we give a deterministic 3-approximation group strategy-proof mechanism, and prove that no deterministic (or randomized) strategy-proof mechanism can have an approximation ratio better than 3 (or 2). For the two-facility problem on a line, we give an anonymous deterministic group strategy-proof mechanism that is (2n-3)-approximation for the total-cost objective, and 3-approximation for the maximum-cost objective. We also provide (asymptotically) tight lower bounds on the approximation ratio.
