Proceedings

Approximation Algorithms for the Shapley Value: Taxonomy and Properties

Patrick Kolpaczki, Eyke Hüllermeier

Download BibTeX Cite

Proceedings of the Thirty-Fifth International Joint Conference on Artificial Intelligence. Survey Track. Pages 7873-7881.

https://doi.org/10.24963/ijcai.2026/874

Keywords

  • Machine Learning: Game Theory
  • Game Theory and Economic Paradigms: Cooperative games

Abstract

Attributing importance to the individual components of a larger unit has become a popular method for understanding models and data in AI and machine learning. Starting with feature explanation, this method is now also used in data valuation or federated learning, just to name a few. Despite their differences, all of these applications use the same mathematical attribution mechanism: the Shapley value, which is rooted in cooperative game theory. While the Shapley value is appealing and has strong axiomatic foundations, it is computationally intractable due to the combinatorial explosion of player subsets. Therefore, there is a need for approximation algorithms, which have been studied intensively in recent years. This survey provides an overview of general-purpose approximation methods applicable to any domain. We categorize these methods into algorithmic classes, compare their properties, and highlight connections between approaches in a comprehensive taxonomy.

Patrick Kolpaczki, and Eyke Hüllermeier. 2026. Approximation Algorithms for the Shapley Value: Taxonomy and Properties. In Proceedings of the Thirty-Fifth International Joint Conference on Artificial Intelligence, IJCAI-26. IJCAI, 7873–7881. https://doi.org/10.24963/ijcai.2026/874
Welcome Future Conferences AI Journal Division IJCAI Proceedings About IJCAI IJCAI Awards