论文标题
有效地计算低流图中连接游戏的沙普利价值
Efficiently Computing the Shapley Value of Connectivity Games in Low-Treewidth Graphs
论文作者
论文摘要
莎普利价值是合作游戏理论中的解决方案概念，在理论上用作实际设置中最常使用。不幸的是，计算沙普利值一般在计算上是棘手的。本文着重于计算（加权）连接游戏的沙普利价值。对于这些连接性游戏，这些游戏是在基础（加权）图上定义的，计算Shapley值是＃p-hard，因此即使对于具有适度数量顶点的图形，也可能（可能）棘手。我们提出了一种算法，如果底层图具有有界的树宽，则可以有效地计算出沙普利值。接下来，我们将算法应用于几个现实世界（Covert）网络。我们表明，我们的算法可以快速计算这些网络的精确沙普利值，而在先前的工作中，只能使用启发式方法近似这些值。最后，结果表明，我们的算法还可以从PACE 2018挑战中对几个较大（人工）基准图有效地计算出Shapley值的时间。
The Shapley value is the solution concept in cooperative game theory that is most used in both theoretical as practical settings. Unfortunately, computing the Shapley value is computationally intractable in general. This paper focuses on computing the Shapley value of (weighted) connectivity games. For these connectivity games, that are defined on an underlying (weighted) graph, computing the Shapley value is #P-hard, and thus (likely) intractable even for graphs with a moderate number of vertices. We present an algorithm that can efficiently compute the Shapley value if the underlying graph has bounded treewidth. Next, we apply our algorithm to several real-world (covert) networks. We show that our algorithm can compute exact Shapley values for these networks quickly, whereas in prior work these values could only be approximated using a heuristic method. Finally, it is shown that our algorithm can also compute the Shapley value time efficiently for several larger (artificial) benchmark graphs from the PACE 2018 challenge.
