Abstract:

Khmelnitskaya et al. have recently proposed the average covering tree
value as a new solution concept for cooperative transferable utility games with directed
graph structure. The average covering tree value is defined as the average of
marginal contribution vectors corresponding to the specific set of rooted trees, and coincides
with the Shapley value when the game has complete communication structure.
In this paper, we discuss the computational complexity of the average covering tree
value. We show that computation of the average covering tree value is #P-complete
even if the characteristic function of the game is {0, 1}-valued. We prove this by a
reduction from counting the number of all linear extensions of a partial order, which
has been shown by Brightwell et al. to be a #P-complete counting problem. The implication
of this result is that an efficient algorithm to calculate the average covering
tree value is unlikely to exist.

Key words: #P-complete , Digraph game , Average covering tree value , Coalition , Communication structure , Linear extension