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


Tom van der Zanden
Tom van der Zanden
  • Speaker
Faculty of Science, Utrecht University

Event Information

Type
Research Seminar
Programme
Logistics
Date
Fri. 2 Mar. 2018
Contact
Remy Spliet
Time
12:00-13:00
Location
H10-31


Abstract

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).

Remy Spliet
  • Coordinator