Abstrac 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...Abstrac 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.展开更多
基金This work was partially supported by the Okawa Foundation for Information and TelecommunicationWe wish to thank the two anonymous reviewers for their constructive suggestions and comments.The comments have helped us significantly improve the paper.
文摘Abstrac 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.
