论文精选 | 实现城市设备智能规划？——具有可选偏好的设施选址游戏

具有可选偏好的设施选址游戏（Facility Location Games with Optional Preference）

摘要：本文中，我们对于一条线上具有两个异构设施的设施选址游戏，提出了可选偏好模型。在这个新模型中代理允许有可选偏好，这为代理报告提供了更多的灵活性。致力于最小化代理成本或总成本的最大值，我们提出了不同的确定性策略-证明（ strategy-proof）机制（无需货币转移）。根据代理关心哪个有可选偏好的设施，我们考虑了两种版本的可选偏好模型：最小（关心最近的），最大（关心最远的）。对于最小变型，我们对于最大成本目标提出了一个2-近似的机制，以及最低下界4/3，和总成本目标的（n/2+1）-近似机制，以及最低边界2。对于Max变型，我们为最大成本目标提出了最优机制，且为总成本目标提出了2-近似机制。

第一作者简介

Hongning Yuan

邮箱：hongnyuan2-c@my.cityu.edu.hk

香港城市大学

文章总结及应用场景

我们研究了两个有着可选偏好的异构设施选址游戏，重点主要集中于确定性机制。这是一个新的模型，它涵盖了更多的现实生活场景。我们还发现，如果随机机制允许的话近似比可以更好。在我们的设置中这两个设施可以放在连续线上的任何一点，也可以放在一起，这是很有合理的。然而，设施不能放在同一点上的情况也是一个有趣的研究方向。

我们论文中提出的一些机制可以应用到离散的情况下。例如，对于最小变型的最小化最大总成本，除非所有的代理都在一起，不然我们提出的机制将永远不会找到有将两个设施放在一起的情况，这种机制可以潜在的扩展到k-设施模型。

via：ECAI  2016

PS : 本文由雷锋网(公众号：雷锋网)独家编译，未经许可拒绝转载！

原论文下载

雷锋网原创文章，未经授权禁止转载。详情见转载须知。