We consider $k$-Facility Location games, where $n$ strategic agents report their locations on the real line, and a mechanism maps them to $k\ge 2$ facilities. Each agent seeks to minimize her distance to the nearest facility. We are interested in (deterministic or randomized) strategyproof mechanisms without payments that achieve a reasonable approximation ratio to the optimal social cost of the agents. To circumvent the inapproximability of $k$-Facility Location by deterministic strategyproof mechanisms, we restrict our attention to perturbation stable instances. An instance of $k$-Facility Location on the line is $\gamma$-perturbation stable (or simply, $\gamma$-stable), for some $\gamma\ge 1$, if the optimal agent clustering is not affected by moving any subset of consecutive agent locations closer to each other by a factor at most $\gamma$. We show that the optimal solution is strategyproof in $(2+\sqrt{3})$-stable instances whose optimal solution does not include any singleton clusters, and that allocating the facility to the agent next to the rightmost one in each optimal cluster (or to the unique agent, for singleton clusters) is strategyproof and $(n-2)/2$-approximate for $5$-stable instances (even if their optimal solution includes singleton clusters). On the negative side, we show that for any $k\ge 3$ and any $\delta > 0$, there is no deterministic anonymous mechanism that achieves a bounded approximation ratio and is strategyproof in $(\sqrt{2}-\delta)$-stable instances. We also prove that allocating the facility to a random agent of each optimal cluster is strategyproof and $2$-approximate in $5$-stable instances. To the best of our knowledge, this is the first time that the existence of deterministic (resp. randomized) strategyproof mechanisms with a bounded (resp. constant) approximation ratio is shown for a large and natural class of $k$-Facility Location instances.


翻译:暂无翻译

0
下载
关闭预览

相关内容

FlowQA: Grasping Flow in History for Conversational Machine Comprehension
专知会员服务
28+阅读 · 2019年10月18日
Stabilizing Transformers for Reinforcement Learning
专知会员服务
58+阅读 · 2019年10月17日
《DeepGCNs: Making GCNs Go as Deep as CNNs》
专知会员服务
30+阅读 · 2019年10月17日
Keras François Chollet 《Deep Learning with Python 》, 386页pdf
专知会员服务
151+阅读 · 2019年10月12日
【SIGGRAPH2019】TensorFlow 2.0深度学习计算机图形学应用
专知会员服务
39+阅读 · 2019年10月9日
Hierarchically Structured Meta-learning
CreateAMind
26+阅读 · 2019年5月22日
Transferring Knowledge across Learning Processes
CreateAMind
27+阅读 · 2019年5月18日
Unsupervised Learning via Meta-Learning
CreateAMind
42+阅读 · 2019年1月3日
meta learning 17年:MAML SNAIL
CreateAMind
11+阅读 · 2019年1月2日
A Technical Overview of AI & ML in 2018 & Trends for 2019
待字闺中
16+阅读 · 2018年12月24日
STRCF for Visual Object Tracking
统计学习与视觉计算组
14+阅读 · 2018年5月29日
Hierarchical Imitation - Reinforcement Learning
CreateAMind
19+阅读 · 2018年5月25日
Focal Loss for Dense Object Detection
统计学习与视觉计算组
11+阅读 · 2018年3月15日
IJCAI | Cascade Dynamics Modeling with Attention-based RNN
KingsGarden
13+阅读 · 2017年7月16日
From Softmax to Sparsemax-ICML16(1)
KingsGarden
72+阅读 · 2016年11月26日
国家自然科学基金
10+阅读 · 2017年12月31日
国家自然科学基金
1+阅读 · 2015年12月31日
国家自然科学基金
1+阅读 · 2015年12月31日
国家自然科学基金
36+阅读 · 2015年12月31日
国家自然科学基金
1+阅读 · 2015年12月31日
国家自然科学基金
0+阅读 · 2014年12月31日
国家自然科学基金
0+阅读 · 2014年12月31日
国家自然科学基金
0+阅读 · 2014年12月31日
国家自然科学基金
1+阅读 · 2014年12月31日
Arxiv
11+阅读 · 2023年3月8日
Arxiv
27+阅读 · 2023年2月10日
Arxiv
31+阅读 · 2022年12月20日
Adaptive Synthetic Characters for Military Training
Arxiv
46+阅读 · 2021年1月6日
Arxiv
45+阅读 · 2019年12月20日
Arxiv
24+阅读 · 2018年10月24日
VIP会员
相关资讯
Hierarchically Structured Meta-learning
CreateAMind
26+阅读 · 2019年5月22日
Transferring Knowledge across Learning Processes
CreateAMind
27+阅读 · 2019年5月18日
Unsupervised Learning via Meta-Learning
CreateAMind
42+阅读 · 2019年1月3日
meta learning 17年:MAML SNAIL
CreateAMind
11+阅读 · 2019年1月2日
A Technical Overview of AI & ML in 2018 & Trends for 2019
待字闺中
16+阅读 · 2018年12月24日
STRCF for Visual Object Tracking
统计学习与视觉计算组
14+阅读 · 2018年5月29日
Hierarchical Imitation - Reinforcement Learning
CreateAMind
19+阅读 · 2018年5月25日
Focal Loss for Dense Object Detection
统计学习与视觉计算组
11+阅读 · 2018年3月15日
IJCAI | Cascade Dynamics Modeling with Attention-based RNN
KingsGarden
13+阅读 · 2017年7月16日
From Softmax to Sparsemax-ICML16(1)
KingsGarden
72+阅读 · 2016年11月26日
相关论文
Arxiv
11+阅读 · 2023年3月8日
Arxiv
27+阅读 · 2023年2月10日
Arxiv
31+阅读 · 2022年12月20日
Adaptive Synthetic Characters for Military Training
Arxiv
46+阅读 · 2021年1月6日
Arxiv
45+阅读 · 2019年12月20日
Arxiv
24+阅读 · 2018年10月24日
相关基金
国家自然科学基金
10+阅读 · 2017年12月31日
国家自然科学基金
1+阅读 · 2015年12月31日
国家自然科学基金
1+阅读 · 2015年12月31日
国家自然科学基金
36+阅读 · 2015年12月31日
国家自然科学基金
1+阅读 · 2015年12月31日
国家自然科学基金
0+阅读 · 2014年12月31日
国家自然科学基金
0+阅读 · 2014年12月31日
国家自然科学基金
0+阅读 · 2014年12月31日
国家自然科学基金
1+阅读 · 2014年12月31日
Top
微信扫码咨询专知VIP会员