On cost allocation for a spanning tree: A game theoretic approach
On cost allocation for a spanning tree: A game theoretic approach
复制标题
DOI：
10.1002/net.3230060404
复制
发表时间：
1976
期刊：
影响因子：
2.1
通讯作者：
C. Bird
中科院分区：
文献类型：
--
作者：
C. Bird
在生成树网络中，利用合作博弈论解决方案的概念来分配成本。稳定的成本分配与合作博弈的核心有关，并证明了由具有不可移动源的最小成本生成树生成的每个博弈都有一个核心。引入了核心的细化，称为不可约核心，并且解的极值点可以通过最小代价生成树的排列来表征。不可约核心中的点在附加参与者的联合下是稳定的。使用加权Shapley值来获得唯一的成本分配。当只有一个最小生成树时，这个值与生成树的边际成本一致。当允许使用多个源时，除非对用户征收额外的税，否则会提供核心存在的反例。
Cooperative game theory solution concepts are used to allocate costs in a spanning tree network. Stable cost allocations are related to the core of a cooperative game and it is proved that every game generated from a minimum cost spanning tree with an immovable source has a core. A refinement of the core, called the irreducible core, is introduced and the extreme points of the solution can be characterized by permutations of the minimal cost spanning tree. Points in the irreducible core are shown to be stable under unions of additional players. A weighted Shapley value is used to obtain a unique allocation of costs. This value coincides with the marginal costs of the spanning tree when there is only one minimal spanning tree. When multiple sources are allowed, counterexamples to the existence of a core are presented unless extra taxes are levied on the users.