Merge-proofness in minimum cost spanning tree problems

摘要

In the context of cost sharing in minimum cost spanning tree problems, we introduce a property called merge-proofness. This property says that no group of agents can be better off claiming to be a single node. We show that the sharing rule that assigns to each agent his own connection cost (the Bird rule) satisfies this property. Moreover, we provide a characterization of the Bird rule using merge-proofness. 【Keywords】Minimum cost spanning tree problems • Cost sharing • Bird rule ■Merge-proofness