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机制进行充分定性。特别是,我们证明,当单一物剂对结果产生重大影响时,设施的轨迹几乎被控制在物剂的轨迹上,并且都沿着共同边缘朝同一方向移动。我们显示了我们与离散线和连续树上先前结果的定性关系密切。然后,我们从主要结果对无限离散线线产生了进一步的影响。