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

• Ando Kazutoshi

  Shizuoka University

• Takase Koichi

  Shizuoka University

Abstract

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.

Journal

• Journal of the Operations Research Society of Japan

  Journal of the Operations Research Society of Japan 63 (1), 31-40, 2020-01-31

  The Operations Research Society of Japan

Keywords

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

Details

• CRID: 1390846609801396608
• NII Article ID: 130007792573
• NII Book ID: AA00703935
• DOI: 10.15807/jorsj.63.31
• ISSN: 21888299
• ISSN: 04534514
• NDL BIB 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
• Text Lang: en
• Data Source:
  • JaLC
  • NDL
  • Crossref
  • CiNii Articles
  • KAKEN
• Abstract License Flag: Disallowed