Split manipulations in cost sharing of minimum cost spanning tree

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.