.png){kind=icon}
返回
Constant-Approximate and Constant-Strategyproof Two-Facility Location
.png){kind=icon}
PRE
AI
DOI：10.1007/978-3-032-03639-1_7.png)
.png){kind=icon}
原文求助.png){kind=icon}
分享.png){kind=icon}
收藏
摘要
En 中文
我们研究了双设施选址问题的确定性机制。给定n个代理人在实线上的报告位置，这样一种机制指定了在何处建造两个设施。该问题的一个设施变体存在一个简单的不容策略欺骗机制，该机制最小化社会成本。然而，对于两个设施，已知任何不容策略欺骗机制都是Ω(n)近似的。我们试图通过放宽问题要求来规避这个强下界。遵循设施选址文献中的其他工作，我们考虑一种放松形式的不容策略欺骗性，其中没有任何代理人可以通过撒谎来改善其结果超过一个常数因子。由于上述Ω(n)下界可以很容易地推广到常数不容策略欺骗机制，我们引入第二种放松：允许设施（而非代理人）位于平面上。我们的第一个主要结果是针对这种放松的一种自然机制，它是常数近似且常数不容策略欺骗的。该机制的一个特点是，输入配置的微小变化可能产生解决方案的大幅变化。受此观察结果以及设施重新分配文献中的结果的启发，我们的第二个主要结果是常数近似、常数不容策略欺骗且利普希茨连续的机制。
Keyword:
Facility Location Problem
Mechanism Design
期刊
A
IF:
0
论文数:
26
被引数:
0
机构
引用论文
.png){kind=icon}
Characterization of Group-strategyproof Mechanisms for Facility Location in Strictly Convex Space严格凸空间中设施选址的群体策略证明机制表征
PREAI
分享收藏The k-Facility Location Problem via Optimal Transport: A Bayesian Study of the Percentile Mechanisms通过最优运输的k-设施选址问题：基于百分位机制的贝叶斯研究
PREAI
分享收藏
查看更多内容