Split Manipulations in Cost Sharing of Minimum Cost Spanning Tree
Split Manipulations in Cost Sharing of Minimum Cost Spanning Tree
复制标题
DOI：
10.3233/faia200096
复制
发表时间：
2020-08
期刊：
影响因子：
--
通讯作者：
Taiki Todo;M. Yokoo
中科院分区：
文献类型：
--
作者：
Taiki Todo;M. Yokoo
.本文研究了最小费用生成树问题，其中一个代理人可以通过添加假帐户来表现为多个代理人。由于这种拆分操作可能会增加MCST的成本，因此重要的是（i）设计一个成本分配规则，在该规则下，没有代理人有动机拆分她的账户，以及（ii）分析现有成本分配规则对拆分操作的阻力。我们首先证明了在一般域下不存在既有效又防分裂的成本分配规则。然后，我们专注于单调权重函数的MCST问题，并表明存在一个成本分配规则，是有效的，核心选择，分裂证明。最后，我们从三个不同的角度分析了Bird规则（文献中研究最多的成本分配规则之一）对分裂操纵的抵抗力：无政府状态的混合价格，操纵的计算难度和域限制。
. This paper studies minimum cost spanning tree (MCST) problems, in which an agent can behave as multiple agents by adding fake accounts. Since such split manipulations may increase the cost of MCST, it is important to (i) design a cost allocation rule under which no agent has an incentive to split her accounts, and (ii) analyze the resistance of the existing cost allocation rules against split manipulations. We first show that there exists no cost allocation rule that is both efficient and split-proof under the general domain. We then focus on the MCST problems with monotonic weight functions and show that there exists a cost allocation rule that is efficient, core-selecting, and split-proof. We finally analyze the resistance of the Bird rule, one of the most studied cost allocation rules in the literature, against split manipulations from three different perspectives: the mixed price of anarchy, the computational difficulty of manipulation, and domain restrictions.