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

2016-09-03 10:30:44     作者:章敏      来源:雷锋网

我们研究了两个有着可选偏好的异构设施选址游戏,重点主要集中于确定性机制。这是一个新的模型,它涵盖了更多的现实生活场景。

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

原论文下载

返回沙发首页  
沙发管家微信
扫描关注沙发管家微信 QQ群: 沙发网官方群 微博:

资讯评论

亲,你需要登录后才能进行评论喔!

还没有评论,快来抢沙发吧!

提示

热门设备安装方法 查看更多>>

最新设备

智能电视 / 盒子评测

安装指南

应用

热门专题