The Shapley value for two-source minimum cost spanning tree problems

Minimum cost spanning tree problems;Boruvka algorithm;Irreducible form;Cost allocation;Shapley value;330

사회과학대학 경제학부 ;

University:서울대학교 대학원

关键词: Minimum cost spanning tree problems;    Boruvka algorithm;    Irreducible form;    Cost allocation;    Shapley value;    330;   

Others  :  http://s-space.snu.ac.kr/bitstream/10371/134623/1/000000018336.pdf

美国|英语

来源: Seoul National University Open Repository

【 摘 要 】

We study two-source minimum cost spanning tree problem. Agents need to connect to the sources either directly or through other agents. For each connection there is an associated cost, and the total cost of connecting all agents must be shared among them. We introduce a cost allocation rule that is defined based on the Boruvka algorithm and show that this rule coincides with a widely used rule, the Shapley value, in the irreducible form of the problem.