Computational Complexity of a Solution for Directed Graph Cooperative Games
- PDF / 422,405 Bytes
- 9 Pages / 439.37 x 666.142 pts Page_size
- 68 Downloads / 210 Views
Computational Complexity of a Solution for Directed Graph Cooperative Games Ayumi Igarashi · Yoshitsugu Yamamoto
Received: 24 January 2013 / Revised: 23 August 2013 / Accepted: 24 August 2013 / Published online: 13 September 2013 © Operations Research Society of China, Periodicals Agency of Shanghai University, and Springer-Verlag Berlin Heidelberg 2013
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. Keywords #P -complete · Digraph game · Average covering tree value · Coalition · Communication structure · Linear extension Mathematics Subject Classification (2010) 05C57 · 91A43 · 03D15 · 68Q17
This work was partially supported by the Okawa Foundation for Information and Telecommunication.
B
A. Igarashi ( ) Graduate School of Systems and Information Engineering, University of Tsukuba, Tsukuba, Ibaraki 305-8573, Japan e-mail: [email protected] Y. Yamamoto Faculty of Engineering, Information and Systems, University of Tsukuba, Tsukuba, Ibaraki 305-8573, Japan e-mail: [email protected]
406
A. Igarashi, Y. Yamamoto
1 Introduction The central question of cooperative game theory is how to distribute the total benefit gained from cooperative behavior of players, and many solution concepts have been proposed to date. Computational complexity is one of the most important criteria to judge whether a given solution concept is appropriate. A solution concept is not applicable in real settings if it requires computation time proportional to an exponential of the problem size; see, for example, [3]. This paper studies cooperative games with directed graph structure from the viewpoint of computational complexity. Khmelnitskaya et al. [5] introduced a cooperative game on a directed graph that furnishes the game with a communication structure. They proposed a single-valued solution concept, and named it the average covering tree value. To construct the average covering tree value, they introduced a so-called covering tree of a directed graph. The average covering tree value is defined as the average of marginal contribution vectors, each of which corresponds to a covering tree. The solution coincides with the Shapley
Data Loading...
