论文标题
异构设施位置游戏
Heterogeneous Facility Location Games
论文作者
论文摘要
我们研究异质$ K $ - 易度域位置游戏。在此模型中，每个设施都有不同的目的。因此，代理人对设施的偏好可能会随意变化。我们的目标是设计策略证明机制，以使设施以最大化代理商之间的最低效用。对于$ k = 1 $，如果已知代理商的位置，我们证明将设施放置在最佳位置的机制是策略的证明。对于$ k \ geq 2 $，我们证明，即使$ k = 2 $，也只有两个具有已知位置的代理，并且必须将设施放置在线段上。我们为确定性和随机策略证明机制提供了不Xibibibibility的界限。最后，我们专注于线段，并提供实现恒定近似的策略证明机制。我们所有的机制都是简单而沟通的。作为副产品，我们表明我们的某些机制可用于实现其他目标的恒定因素近似，例如社会福利和幸福。
We study heterogeneous $k$-facility location games. In this model there are $k$ facilities where each facility serves a different purpose. Thus, the preferences of the agents over the facilities can vary arbitrarily. Our goal is to design strategy proof mechanisms that place the facilities in a way to maximize the minimum utility among the agents. For $k=1$, if the agents' locations are known, we prove that the mechanism that places the facility on an optimal location is strategy proof. For $k \geq 2$, we prove that there is no optimal strategy proof mechanism, deterministic or randomized, even when $k=2$ there are only two agents with known locations, and the facilities have to be placed on a line segment. We derive inapproximability bounds for deterministic and randomized strategy proof mechanisms. Finally, we focus on the line segment and provide strategy proof mechanisms that achieve constant approximation. All of our mechanisms are simple and communication efficient. As a byproduct we show that some of our mechanisms can be used to achieve constant factor approximations for other objectives as the social welfare and the happiness.
