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

• Ando Kazutoshi

  Shizuoka University

• Takase Koichi

  Shizuoka University

抄録

In this paper, we address a Monte Carlo algorithm for calculating the Shapley values of minimum cost spanning tree games. We provide tighter upper and lower bounds for the marginal cost vector and improve a previous study's lower bound on the number of permutations required for the output of the algorithm to achieve a given accuracy with a given probability. In addition, we present computational experiments for estimating the lower bound on the number of permutations required by the Monte Carlo algorithm.

収録刊行物

• 日本オペレーションズ・リサーチ学会論文誌

  日本オペレーションズ・リサーチ学会論文誌 63 (1), 31-40, 2020-01-31

  公益社団法人 日本オペレーションズ・リサーチ学会

キーワード

• Game theory
• algorithm
• cooperative game
• Shapley value
• minimum cost spanning tree

詳細情報

• CRID: 1390846609801396608
• NII論文ID: 130007792573
• NII書誌ID: AA00703935
• DOI: 10.15807/jorsj.63.31
• ISSN: 21888299
• ISSN: 04534514
• NDL書誌ID: 030213062
• Web Site: https://ndlsearch.ndl.go.jp/books/R000000004-I030213062
• Web Site: https://www.jstage.jst.go.jp/article/jorsj/63/1/63_31/_pdf
• 本文言語コード: en
• データソース種別:
  • JaLC
  • NDL
  • Crossref
  • CiNii Articles
  • KAKEN
• 抄録ライセンスフラグ: 使用不可