Development of Approximation Algorithms for the Shapley Value of Minimum Cost Spanning Tree Games

最小成本生成树博弈Shapley值近似算法的开发

• 批准号: 23510166
• 负责人: ANDO Kazutoshi
• 金额: $ 2.33万
• 依托单位: Shizuoka University
• 依托单位国家: 日本
• 项目类别: Grant-in-Aid for Scientific Research (C)
• 财政年份: 2011
• 资助国家: 日本
• 起止时间: 2011 至 2013
• 项目状态: 已结题
• 来源: https://kaken.nii.ac.jp/grant/KAKENHI-PROJECT-23510166/
• 关键词: ゲーム理論; オペレーションズ・リサーチ; アルゴリズム; 組合せ最適化; 離散数学; ＯＲ

In this research, we developed two algorithms for computing the Shapley value of minimum cost spanning tree games. The first one is a randomized algorithm which, given an arbitrary minimum cost spanning tree game, outputs an approximation of its Shapley value with given precision in pseudo-polynomial time. Given a minimum cost spanning tree game, the other algorithm first approximates the cost function of the associated game by a tree metric and then it computes the exact Shapley value of the game associated with the approximated cost function. Numerical experiments show that the latter algorithm performs well when the given cost function is close to a tree metric.

在这项研究中，我们提出了两种算法来计算最小费用生成树对策的Shapley值。第一种是随机算法，给定一个任意最小代价的生成树博弈，在伪多项式时间内以给定的精度输出其Shapley值的近似值。在给定一个最小代价生成树博弈的情况下，另一种算法首先用树度量近似关联博弈的代价函数，然后计算与近似代价函数关联的博弈的精确Shapley值。数值实验表明，当给定的代价函数接近树的度量时，后一种算法的性能较好。

项目成果

Least distance based inefficient measures on the Pareto-efficient frontier in DEA

DEA 帕累托有效前沿上基于最小距离的低效措施

• 发表时间: 2012
• 期刊: Journal of the Operations Research Society of Japan
• 作者: K. Ando;A. Kai;Y. Maeda and K. Sekitani
• 通讯作者: Y. Maeda and K. Sekitani

Computation of the Shapley value of minimum cost spanning tree games: #P-hardness and polynomial cases

最小成本生成树博弈的 Shapley 值的计算：

• DOI: 10.1007/s13160-012-0078-9
• 发表时间: 2012
• 期刊: Japan Journal of Industrial and Applied Mathematics
• 影响因子: 0.9
• 作者: Hirofumi Fukuyama;Kazuyuki Sekitani;K. Ando
• 通讯作者: K. Ando

最小費用全域木ゲームのShapley値に対するサンプリングによる近似アルゴリズム

使用最小成本生成树博弈的 Shapley 值采样的近似算法

• 发表时间: 2013
• 作者: 安藤和敏;徳武忠俊
• 通讯作者: 徳武忠俊

2入力１出力ＤＥＡに対する最短距離非効率性尺度の単調性の特徴付け

二输入一输出 DEA 的最短距离无效率测度的单调性表征

• 发表时间: 2013
• 作者: 安藤和敏; 山田悠一郎;関谷和之;福山博文;安藤 和敏,金満達也,前田恭伸,関谷和之
• 通讯作者: 安藤 和敏,金満達也,前田恭伸,関谷和之

最小費用全域木ゲームの Shapley 値に対する近似手法の提案とその近似精度の実験的評価

最小成本生成树博弈中Shapley值的近似方法的提出及其近似精度的实验评估

• 发表时间: 2012
• 作者: 安藤和敏;徳武忠俊
• 通讯作者: 徳武忠俊