A linear approximation method for the Shapley value

DOI10.1016/j.artint.2008.05.003zbMath1184.91029OpenAlexW2436401953WikidataQ57377393 ScholiaQ57377393MaRDI QIDQ2389675

Shaheen S. Fatima, Michael Wooldridge, Nicholas R. Jennings

Publication date: 17 July 2009

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

Full work available at URL: https://eprints.soton.ac.uk/265802/1/aij08.pdf

zbMATH Keywords

Shapley valueapproximation methodcoalitional game theory

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Cooperative games (91A12) Approximation algorithms (68W25)

Related Items

Variance allocation and Shapley value ⋮ Internal structure of coalitions in competitive and altruistic graphical coalitional games ⋮ A Bayesian Monte Carlo method for computing the Shapley value: application to weighted voting and bin packing games ⋮ Manipulating the quota in weighted voting games ⋮ A Shapley Value Index for Market Basket Analysis: Efficient Computation Using an Harsanyi Dividend Representation ⋮ Variance Reduction for Estimation of Shapley Effects and Adaptation to Unknown Input Distribution ⋮ Sensitivity indices for independent groups of variables ⋮ Coalitional games induced by matching problems: complexity and islands of tractability for the Shapley value ⋮ Generating Functions of Weighted Voting Games, MacMahon’s Partition Analysis, and Clifford Algebras ⋮ Values for level structures with polynomial-time algorithms, relevant coalition functions, and general considerations ⋮ Monte Carlo methods for the Shapley-Shubik power index ⋮ The Computational Complexity of Understanding Binary Classifier Decisions ⋮ Explanation with the winter value: efficient computation for hierarchical Choquet integrals

Cites Work

• An algorithm for distributing coalitional value calculations among cooperating agents
• Methods for task allocation via agent coalition formation
• Coalitions among computationally bounded agents
• Computing power indices in weighted multiple majority games.
• Coalition structure generation with worst case guarantees
• Voting power in the European Union enlargement
• On the computational complexity of weighted voting games
• Complexity of constructing solutions in the core based on synergies among coalitions
• Computing Power Indices for Large Voting Games
• On the Complexity of Cooperative Solution Concepts
• Multilinear Extensions of Games
• Generating functions for computing power indices efficiently
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: A linear approximation method for the Shapley value