Efficiently Computing the Shapley Value of Connectivity Games in Low-Treewidth Graphs

Game-theoretic centrality measures are a powerful tool to identify key players in covert networks (that model, e.g., the interactions between suspected terrorists or criminals). Unfortunately, such measures are often NP-hard to compute and thus intractable, even for small graphs. However, if the graph considered has some special properties, we may be able to exploit these properties to make the computation tractable. We show that, for three connectivity games, their Shapely value can be efficiently computed if the underlying graph has low treewidth. Using this method, we are able to compute the Shapley Value for several graphs for which this was previously infeasible (including, notably, the 69-vertex graph of the terrorists involved in the 9-11 attacks studied in previous work on Shapley value-based centrality).