Efficient Computation of the Shapley Value for Game-Theoretic Network Centrality

DOI10.1613/jair.3806zbMath1280.91035arXiv1402.0567OpenAlexW3102501663MaRDI QIDQ4917616

Nicholas R. Jennings, Karthik V. Aadithya, Piotr L. Szczepański, Balaraman Ravindran, Tomasz P. Michalak

Publication date: 2 May 2013

Published in: Journal of Artificial Intelligence Research (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1402.0567

Mathematics Subject Classification ID

Applications of graph theory (05C90) Small world graphs, complex networks (graph-theoretic aspects) (05C82) Network design and communication in computer systems (68M10) Games involving graphs (91A43)

Related Items (24)

Parallelization of game theoretic centrality algorithms ⋮ A modified Myerson value for determining the centrality of graph vertices ⋮ Efficient computation of the Shapley value for large-scale linear production games ⋮ Tournament solutions based on cooperative game theory ⋮ Unnamed Item ⋮ A graph-theoretical basis of stochastic-cascading network influence: characterizations of influence-based centrality ⋮ Centrality measures in networks ⋮ Braess' paradox: A cooperative game‐theoretic point of view ⋮ Directed communication in games with directed graphs ⋮ Efficient algorithms for game-theoretic betweenness centrality ⋮ Coalition structure generation: a survey ⋮ A Shapley Value Index for Market Basket Analysis: Efficient Computation Using an Harsanyi Dividend Representation ⋮ Network Essence: PageRank Completion and Centrality-Conforming Markov Chains ⋮ Unnamed Item ⋮ Analyzing power in weighted voting games with super-increasing weights ⋮ On influence, stable behavior, and the most influential individuals in networks: a game-theoretic approach ⋮ Coalitional games induced by matching problems: complexity and islands of tractability for the Shapley value ⋮ Algorithms for computing the Shapley value of cooperative games on lattices ⋮ Answers set programs for non-transferable utility games: expressiveness, complexity and applications ⋮ Values for level structures with polynomial-time algorithms, relevant coalition functions, and general considerations ⋮ On network analysis using non-additive integrals: extending the game-theoretic network centrality ⋮ Attachment centrality: measure for connectivity in networks ⋮ Tensor approximation of cooperative games and their semivalues ⋮ A Shapley distance in graphs

This page was built for publication: Efficient Computation of the Shapley Value for Game-Theoretic Network Centrality