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.


翻译:我们研究的是各式各样的美元-设施定位游戏。 在这个模型中,每个设施都有一个不同的用途。 因此, 代理商对设施的偏好可以任意地变化。 我们的目标是设计战略验证机制, 将设施置于代理商的最低限度效用最大化。 对于 $=1 美元, 如果代理商的所在地为已知, 我们证明将设施置于最佳位置的机制是战略证明。 对于 $k\geq 2 美元, 我们证明没有最佳的战略验证机制, 确定性或随机化, 即使只有两个已知地点的代理商2美元, 并且设施必须放在线段上。 我们为确定性和随机化的战略验证机制制定不协调的界限。 最后, 我们侧重于线段, 并提供战略验证机制, 实现恒定的近似。 我们所有的机制都是简单而有效的。 作为产品, 我们的一些机制可以用来实现作为社会福利和幸福的其他目标的恒定要素。

0
下载
关闭预览

相关内容

Effective.Modern.C++ 中英文版,334页pdf
专知会员服务
66+阅读 · 2020年11月4日
Linux导论,Introduction to Linux,96页ppt
专知会员服务
75+阅读 · 2020年7月26日
知识图谱推理,50页ppt,Salesforce首席科学家Richard Socher
专知会员服务
105+阅读 · 2020年6月10日
Fariz Darari简明《博弈论Game Theory》介绍,35页ppt
专知会员服务
104+阅读 · 2020年5月15日
[综述]深度学习下的场景文本检测与识别
专知会员服务
76+阅读 · 2019年10月10日
【哈佛大学商学院课程Fall 2019】机器学习可解释性
专知会员服务
96+阅读 · 2019年10月9日
【SIGGRAPH2019】TensorFlow 2.0深度学习计算机图形学应用
专知会员服务
39+阅读 · 2019年10月9日
Hierarchically Structured Meta-learning
CreateAMind
23+阅读 · 2019年5月22日
Transferring Knowledge across Learning Processes
CreateAMind
24+阅读 · 2019年5月18日
Unsupervised Learning via Meta-Learning
CreateAMind
41+阅读 · 2019年1月3日
分布式TensorFlow入门指南
机器学习研究会
4+阅读 · 2017年11月28日
已删除
将门创投
4+阅读 · 2017年11月1日
【今日新增】IEEE Trans.专刊截稿信息8条
Call4Papers
7+阅读 · 2017年6月29日
Arxiv
0+阅读 · 2020年11月23日
Arxiv
0+阅读 · 2020年11月22日
Arxiv
0+阅读 · 2020年11月19日
VIP会员
相关VIP内容
Effective.Modern.C++ 中英文版,334页pdf
专知会员服务
66+阅读 · 2020年11月4日
Linux导论,Introduction to Linux,96页ppt
专知会员服务
75+阅读 · 2020年7月26日
知识图谱推理,50页ppt,Salesforce首席科学家Richard Socher
专知会员服务
105+阅读 · 2020年6月10日
Fariz Darari简明《博弈论Game Theory》介绍,35页ppt
专知会员服务
104+阅读 · 2020年5月15日
[综述]深度学习下的场景文本检测与识别
专知会员服务
76+阅读 · 2019年10月10日
【哈佛大学商学院课程Fall 2019】机器学习可解释性
专知会员服务
96+阅读 · 2019年10月9日
【SIGGRAPH2019】TensorFlow 2.0深度学习计算机图形学应用
专知会员服务
39+阅读 · 2019年10月9日
相关资讯
Hierarchically Structured Meta-learning
CreateAMind
23+阅读 · 2019年5月22日
Transferring Knowledge across Learning Processes
CreateAMind
24+阅读 · 2019年5月18日
Unsupervised Learning via Meta-Learning
CreateAMind
41+阅读 · 2019年1月3日
分布式TensorFlow入门指南
机器学习研究会
4+阅读 · 2017年11月28日
已删除
将门创投
4+阅读 · 2017年11月1日
【今日新增】IEEE Trans.专刊截稿信息8条
Call4Papers
7+阅读 · 2017年6月29日
Top
微信扫码咨询专知VIP会员