论文精选 | 实现城市设备智能规划?——具有可选偏好的设施选址游戏-阿里云开发者社区

开发者社区> 雷锋网> 正文
登录阅读全文

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

简介:

具有可选偏好的设施选址游戏(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 : 本文由雷锋网(公众号:雷锋网)独家编译,未经许可拒绝转载!

原论文下载

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


本文作者:章敏


本文转自雷锋网禁止二次转载,原文链接

版权声明:本文内容由阿里云实名注册用户自发贡献,版权归原作者所有,阿里云开发者社区不拥有其著作权,亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容,填写侵权投诉表单进行举报,一经查实,本社区将立刻删除涉嫌侵权内容。

分享: