We consider the problem of locating a single facility for 2 agents in $L_p$ space ($1<p<\infty$) and give a nearly complete characterization of such deterministic strategyproof mechanisms. We use the distance between an agent and the facility in $L_p$ space to denote the cost of the agent. A mechanism is strategyproof iff no agent can reduce her cost from misreporting her private location. We show that in $L_p$ space ($1<p<\infty$) with 2 agents, any location output of a deterministic, unanimous, translation-invariant strategyproof mechanism must satisfy a set of equations and mechanisms are continuous, scalable. In one-dimensional space, the output must be one agent's location, which is easy to prove in any $n$ agents. However, in $m$-dimensional space ($m\ge 2$), the situation will be much more complex, with only 2-agent case finished. We show that the output of such a mechanism must satisfy a set of equations, and when $p=2$ the output must locate at a sphere with the segment between the two agents as the diameter. Further more, for $n$-agent situations, we find that the simple extension of this the 2-agent situation cannot hold when dimension $m>2$ and prove that the well-known general median mechanism will give an counter-example. Particularly, in $L_2$ (i.e., Euclidean) space with 2 agents, such a mechanism is rotation-invariant iff it is dictatorial; and such a mechanism is anonymous iff it is one of the three mechanisms in Section 4. And our tool implies that any such a mechanism has a tight lower bound of 2-approximation for maximum cost in any multi-dimensional space.


翻译:我们考虑的是将2个代理商的单一设施定位在$L_p美元空间(1<p ⁇ infty$)中的问题,并给出了这种确定性战略防控机制的几乎完整的描述。我们使用一个代理商与1美元空间的设施之间的距离来表示代理商的成本。如果没有任何代理商能够通过误报其私人地址来降低成本,那么这种机制就具有战略防险性。我们显示,在2个代理商的$空间(1<p ⁇ infty$)中,一个确定性、一致的、翻译性反变异战略机制的任何位置输出必须满足一系列的等式和机制的连续和可缩缩缩缩。在一维空间中,输出必须是1个代理商的距离,这很容易在任何美元空间空间空间空间空间空间的面积(m)中(metrial2)中找到一个普通的平面机制。我们发现这种机制的输出必须满足一套方程式,当$=2的输出必须位于一个平方域, 当2的平面空间机制在2个直径之间时,这种介器的尺寸是一定的平方。

0
下载
关闭预览

相关内容

iOS 8 提供的应用间和应用跟系统的功能交互特性。
  • Today (iOS and OS X): widgets for the Today view of Notification Center
  • Share (iOS and OS X): post content to web services or share content with others
  • Actions (iOS and OS X): app extensions to view or manipulate inside another app
  • Photo Editing (iOS): edit a photo or video in Apple's Photos app with extensions from a third-party apps
  • Finder Sync (OS X): remote file storage in the Finder with support for Finder content annotation
  • Storage Provider (iOS): an interface between files inside an app and other apps on a user's device
  • Custom Keyboard (iOS): system-wide alternative keyboards

Source: iOS 8 Extensions: Apple’s Plan for a Powerful App Ecosystem
【干货书】机器学习速查手册,135页pdf
专知会员服务
127+阅读 · 2020年11月20日
Diganta Misra等人提出新激活函数Mish,在一些任务上超越RuLU
专知会员服务
15+阅读 · 2019年10月15日
【哈佛大学商学院课程Fall 2019】机器学习可解释性
专知会员服务
104+阅读 · 2019年10月9日
最新BERT相关论文清单,BERT-related Papers
专知会员服务
53+阅读 · 2019年9月29日
Hierarchically Structured Meta-learning
CreateAMind
27+阅读 · 2019年5月22日
Call for Participation: Shared Tasks in NLPCC 2019
中国计算机学会
5+阅读 · 2019年3月22日
强化学习的Unsupervised Meta-Learning
CreateAMind
18+阅读 · 2019年1月7日
Ray RLlib: Scalable 降龙十八掌
CreateAMind
9+阅读 · 2018年12月28日
A Technical Overview of AI & ML in 2018 & Trends for 2019
待字闺中
17+阅读 · 2018年12月24日
人工智能 | COLT 2019等国际会议信息9条
Call4Papers
6+阅读 · 2018年9月21日
disentangled-representation-papers
CreateAMind
26+阅读 · 2018年9月12日
Hierarchical Disentangled Representations
CreateAMind
4+阅读 · 2018年4月15日
【学习】Hierarchical Softmax
机器学习研究会
4+阅读 · 2017年8月6日
Auto-Encoding GAN
CreateAMind
7+阅读 · 2017年8月4日
Arxiv
0+阅读 · 2021年1月15日
Arxiv
0+阅读 · 2021年1月14日
Arxiv
3+阅读 · 2018年1月31日
VIP会员
相关资讯
Hierarchically Structured Meta-learning
CreateAMind
27+阅读 · 2019年5月22日
Call for Participation: Shared Tasks in NLPCC 2019
中国计算机学会
5+阅读 · 2019年3月22日
强化学习的Unsupervised Meta-Learning
CreateAMind
18+阅读 · 2019年1月7日
Ray RLlib: Scalable 降龙十八掌
CreateAMind
9+阅读 · 2018年12月28日
A Technical Overview of AI & ML in 2018 & Trends for 2019
待字闺中
17+阅读 · 2018年12月24日
人工智能 | COLT 2019等国际会议信息9条
Call4Papers
6+阅读 · 2018年9月21日
disentangled-representation-papers
CreateAMind
26+阅读 · 2018年9月12日
Hierarchical Disentangled Representations
CreateAMind
4+阅读 · 2018年4月15日
【学习】Hierarchical Softmax
机器学习研究会
4+阅读 · 2017年8月6日
Auto-Encoding GAN
CreateAMind
7+阅读 · 2017年8月4日
Top
微信扫码咨询专知VIP会员