Art

J-GLOBAL ID：202002251526486045   Reference number：20A0995665

MONTE CARLO ALGORITHM FOR CALCULATING THE SHAPLEY VALUES OF MINIMUM COST SPANNING TREE GAMES

最小全域木ゲームのShapley値を計算するためのモンテカルロアルゴリズム

Author (2)： Ando Kazutoshi (Shizuoka University) ,  Takase Koichi (Shizuoka University)
Material： Journal of the Operations Research Society of Japan  (日本オペレーションズ・リサーチ学会論文誌)
Volume： 63  Issue： 1  Page： 31-40(J-STAGE)  Publication year： 2020 
JST Material Number： G0402A  ISSN： 0453-4514  Document type： Article
Article type： 原著論文  Country of issue： Japan (JPN)  Language： ENGLISH (EN)

Thesaurus term： *spanning tree ,  *graph theory ,  *cooperative game ,  index number ,  *Monte Carlo method ,  algorithm ,  numerical calculation
Semi thesaurus term： *minimum spanning tree ,  Shapley value ,  calculation algorithm ,  numerical experiment

Author keywords (5)： Game theory ,  algorithm ,  cooperative game ,  Shapley value ,  minimum cost spanning tree

JST classification (2)： Game thoery  (KA03060T) ,  Numerical computation  (JE02000J)

Reference (17)：

• [1] K. Ando: Computation of the Shapley value of minimum cost spanning tree games: #P-hardness and polynomial cases. Japan Journal of Industrial and Applied Mathematics, 29 (2012), 385-400.
• [2] K. Ando and T. Tokutake: Approximation algorithm for the Shapley value of minimum cost spanning tree games based on sampling (in Japanese). Proceedings of the 2013 Spring National Conference of the Operations Research Society of Japan (2013), 148-149.
• [3] Y. Bachrach, E. Markakis, E. Resnick, A.D. Procaccia, J.S. Rosenschein and A. Saberi: Approximating power indices: theoretical and empirical analysis. Autonomous Agents and Multi-Agent Systems, 20 (2010), 105-122.
• [4] C.G. Bird: On cost allocation for a spanning tree. A game theoretic approach. Networks, 6 (1976), 335-350.
• [5] J. Castro, D. Gómez, E. Molina and J. Tejada: Improving polynomial estimation of the Shapley value by stratified random sampling with optimum allocation. Computers & Operations Research, 82 (2017), 180-188.

Terms in the title (6)： 最小全域木 ,  ゲーム ,  Shapley値 ,  計算 ,  モンテカルロ ,  アルゴリズム