Computational Complexity of the Game Theory Approach to Cost Allocation for a Tree

Source abstract

In the game theory approach to the problem of allocating cost, the users of a facility are viewed as players in a cooperative n-person game. It is the nature of cooperative games that the power of each one of the 2 n−1 possible coalitions is taken into account. Thus, practical problems of allocating cost may be intractable in the game theory approach because of the computational complexity involved. However, it is shown that good algorithms do exist for the nucleolus and the Shapley value allocations for a tree. The nucleolus can be computed within O(n 3 ) operations and the Shapley allocation in O(n) operations.