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

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