Efficient Computation of Semivalues for Game-Theoretic Network Centrality


  • Piotr Szczepański Warsaw University of Technology
  • Mateusz Tarkowski University of Oxford
  • Tomasz Michalak University of Oxford and University of Warsaw
  • Paul Harrenstein University of Oxford
  • Michael Wooldridge University of Oxford




game-theoretic network centrality, Shapley value, emivalue


Solution concepts from cooperative game theory, such as the Shapley value or the Banzhaf index, have recently been advocated as interesting extensions of standard measures of node centrality in networks. While this direction of research is promising, the computation of game-theoretic centrality can be challenging. In an attempt to address the computational issues of game-theoretic network centrality, we present a generic framework for constructing game-theoretic network centralities. We prove that all extensions that can be expressed in this framework are computable in polynomial time. Using our framework, we present the first game-theoretic extensions of weighted and normalized degree centralities, impact factor centrality,distance-scaled and normalized betweenness centrality,and closeness and normalized closeness centralities.




How to Cite

Szczepański, P., Tarkowski, M., Michalak, T., Harrenstein, P., & Wooldridge, M. (2015). Efficient Computation of Semivalues for Game-Theoretic Network Centrality. Proceedings of the AAAI Conference on Artificial Intelligence, 29(1). https://doi.org/10.1609/aaai.v29i1.9215