  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.
