We address the problem of strategyproof (SP) facility location mechanisms on discrete trees. Our main result is a full characterization of onto and SP mechanisms. In particular, we prove that when a single agent significantly affects the outcome, the trajectory of the facility is almost contained in the trajectory of the agent, and both move in the same direction along the common edges. We show tight relations of our characterization to previous results on discrete lines and on continuous trees. We then derive further implications of the main result for infinite discrete lines.


翻译:我们处理离散树上防战略(SP)设施定位机制的问题,我们的主要结果就是对上方和SP机制进行充分定性。特别是,我们证明,当单一物剂对结果产生重大影响时,设施的轨迹几乎被控制在物剂的轨迹上,并且都沿着共同边缘朝同一方向移动。我们显示了我们与离散线和连续树上先前结果的定性关系密切。然后,我们从主要结果对无限离散线线产生了进一步的影响。

0
下载
关闭预览

相关内容

知识图谱推理,50页ppt,Salesforce首席科学家Richard Socher
专知会员服务
105+阅读 · 2020年6月10日
【反馈循环自编码器】FEEDBACK RECURRENT AUTOENCODER
专知会员服务
22+阅读 · 2020年1月28日
【哈佛大学商学院课程Fall 2019】机器学习可解释性
专知会员服务
103+阅读 · 2019年10月9日
计算机 | IUI 2020等国际会议信息4条
Call4Papers
6+阅读 · 2019年6月17日
CCF推荐 | 国际会议信息10条
Call4Papers
8+阅读 · 2019年5月27日
Hierarchically Structured Meta-learning
CreateAMind
26+阅读 · 2019年5月22日
Transferring Knowledge across Learning Processes
CreateAMind
27+阅读 · 2019年5月18日
计算机 | 中低难度国际会议信息6条
Call4Papers
7+阅读 · 2019年5月16日
Unsupervised Learning via Meta-Learning
CreateAMind
42+阅读 · 2019年1月3日
A Technical Overview of AI & ML in 2018 & Trends for 2019
待字闺中
16+阅读 · 2018年12月24日
Hierarchical Disentangled Representations
CreateAMind
4+阅读 · 2018年4月15日
论文浅尝 | Distant Supervision for Relation Extraction
开放知识图谱
4+阅读 · 2017年12月25日
计算机类 | 国际会议信息7条
Call4Papers
3+阅读 · 2017年11月17日
Arxiv
0+阅读 · 2021年3月30日
Arxiv
0+阅读 · 2021年3月27日
VIP会员
相关VIP内容
知识图谱推理,50页ppt,Salesforce首席科学家Richard Socher
专知会员服务
105+阅读 · 2020年6月10日
【反馈循环自编码器】FEEDBACK RECURRENT AUTOENCODER
专知会员服务
22+阅读 · 2020年1月28日
【哈佛大学商学院课程Fall 2019】机器学习可解释性
专知会员服务
103+阅读 · 2019年10月9日
相关资讯
计算机 | IUI 2020等国际会议信息4条
Call4Papers
6+阅读 · 2019年6月17日
CCF推荐 | 国际会议信息10条
Call4Papers
8+阅读 · 2019年5月27日
Hierarchically Structured Meta-learning
CreateAMind
26+阅读 · 2019年5月22日
Transferring Knowledge across Learning Processes
CreateAMind
27+阅读 · 2019年5月18日
计算机 | 中低难度国际会议信息6条
Call4Papers
7+阅读 · 2019年5月16日
Unsupervised Learning via Meta-Learning
CreateAMind
42+阅读 · 2019年1月3日
A Technical Overview of AI & ML in 2018 & Trends for 2019
待字闺中
16+阅读 · 2018年12月24日
Hierarchical Disentangled Representations
CreateAMind
4+阅读 · 2018年4月15日
论文浅尝 | Distant Supervision for Relation Extraction
开放知识图谱
4+阅读 · 2017年12月25日
计算机类 | 国际会议信息7条
Call4Papers
3+阅读 · 2017年11月17日
Top
微信扫码咨询专知VIP会员