论文标题
设施的位置游戏超出单峰：入场费模型
Facility Location Games Beyond Single-Peakedness: the Entrance Fee Model
论文作者
论文摘要
设施位置游戏已在机械设计方面进行了广泛的研究。在经典模型中，每个代理的成本仅取决于她与最近设施的距离。在本文中，我们介绍了一个新颖的模型，每个设施都收取入口费。因此，每个代理的成本都取决于设施的距离和设施的入口费。在我们的模型中，入口费功能被允许成为任意功能，导致代理人的喜好可能不再单峰了：与经典模型的背离引入了其他挑战。我们系统地深入研究了模型的复杂性，设计了具有良好近似值的策略性防护机制。此外，我们将这些比率与几乎不可能的结果进行补充。具体而言，对于一个官方和两个实力性游戏，我们为实用和平等主义目标提供了确定性和随机机制给出的近似值和下限。
The facility location game has been studied extensively in mechanism design. In the classical model, each agent's cost is solely determined by her distance to the nearest facility. In this paper, we introduce a novel model where each facility charges an entrance fee. Thus, the cost of each agent is determined by both the distance to the facility and the entrance fee of the facility. In our model, the entrance fee function is allowed to be an arbitrary function, causing agents' preferences may no longer be single-peaked anymore: This departure from the classical model introduces additional challenges. We systematically delve into the intricacies of the model, designing strategyproof mechanisms with favorable approximation ratios. Additionally, we complement these ratios with nearly-tight impossibility results. Specifically, for one-facility and two-facility games, we provide upper and lower bounds for the approximation ratios given by deterministic and randomized mechanisms with respect to utilitarian and egalitarian objectives.
