文献

J-GLOBAL ID：202002251526486045   整理番号：20A0995665

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

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

著者 (2件)： Ando Kazutoshi (Shizuoka University) ,  Takase Koichi (Shizuoka University)
資料名： Journal of the Operations Research Society of Japan  (Journal of the Operations Research Society of Japan)
巻： 63  号： 1  ページ： 31-40(J-STAGE)  発行年： 2020年 
JST資料番号： G0402A  ISSN： 0453-4514  資料種別： 逐次刊行物 (A)
記事区分： 原著論文  発行国： 日本 (JPN)  言語： 英語 (EN)

抄録/ポイント： 本論文では,最小全域木ゲームのShapley値を計算するためのモンテカルロアルゴリズムに取り組む。限界費用ベクトルに対するより厳密な上下限を規定し,指定した確率により指定した精度を達成するために,アルゴリズムの出力に必要な順列数に関する先行研究の下限を改善する。さらに,モンテカルロアルゴリズムに必要とされる順列数の下限を推定するための計算実験を提示する。(翻訳著者抄録)

シソーラス用語： *スパンニング木 ,  *グラフ理論 ,  *協力ゲーム ,  指数 ,  *モンテカルロ法 ,  アルゴリズム ,  数値計算 ,  Shapley値 ,  計算アルゴリズム ,  数値実験
準シソーラス用語： *最小全域木

著者キーワード (5件)： ゲーム理論 ,  アルゴリズム ,  協調ゲーム ,  Shapley値 ,  最小コストスパンニング木

分類 (2件)： ゲーム理論  (KA03060T) ,  数値計算  (JE02000J)

引用文献 (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.

タイトルに関連する用語 (6件)： 最小全域木 ,  ゲーム ,  Shapley値 ,  計算 ,  モンテカルロ ,  アルゴリズム