Complexity of Computing the Shapley Value in Games with Externalities

We study the complexity of computing the Shapley value in games with externalities. We focus on two representations based on marginal contribution nets (embedded MC-nets and weighted MC-nets) and five extensions of the Shapley value to games with externalities. Our results show that while weighted MC-nets are more concise than embedded MC-nets, they have slightly worse computational properties when it comes to computing the Shapley value: two out of five extensions can be computed in polynomial time for embedded MC-nets and only one for weighted MC-nets.

Computer Science Mathematics Economics

View graph Source

Paper

References (48)

01Signed Graph Games: Coalitional Games with Friends, Enemies and AlliesOskar Skibski, Takamasa Suzuki, Tomasz Grabowski et al.2020 · Adaptive Agents and Multi-Agent Systems · 3 citations

02Partition decision trees: representation for efficient computation of the Shapley value extended to games with externalitiesOskar Skibski, Tomasz P. Michalak, Y. Sakurai et al.2019 · Autonomous Agents and Multi-Agent Systems · 4 citations

03Attachment centrality: Measure for connectivity in networksOskar Skibski, Talal Rahwan, Tomasz P. Michalak et al.2019 · Artificial Intelligence · 33 citations

04The non-emptiness of the core of a partition function form gameTakaaki Abe, Yukihiko Funaki2017 · International Journal of Game Theory · 23 citations

05k-Coalitional Cooperative GamesOskar Skibski, Szymon Matejczyk, Tomasz P. Michalak et al.2016 · Adaptive Agents and Multi-Agent Systems · 8 citations

06A Graphical Representation for Games in Partition Function FormOskar Skibski, Tomasz P. Michalak, Y. Sakurai et al.2015 · AAAI Conference on Artificial Intelligence · 8 citations

07The cost of principles: analyzing power in compatibility weighted voting gamesA. See, Yoram Bachrach, Pushmeet Kohli2014 · Adaptive Agents and Multi-Agent Systems · 16 citations

08Efficient Computation of the Shapley Value for Game-Theoretic Network CentralityTomasz P. Michalak, Aadithya V. Karthik, Piotr L. Szczepanski et al.2014 · Journal of Artificial Intelligence Research · 206 citations In Library

09Computational Analysis of Connectivity Games with Applications to the Investigation of Terrorist NetworksTomasz P. Michalak, Talal Rahwan, Piotr L. Szczepanski et al.2013 · International Joint Conference on Artificial Intelligence · 51 citations

10Anytime coalition structure generation in multi-agent systems with positive or negative externalitiesTalal Rahwan, Tomasz P. Michalak, M. Wooldridge et al.2012 · Artificial Intelligence · 79 citations

11Computational Aspects of Cooperative Game TheoryM. Wooldridge2011 · Agent and Multi-Agent Systems: Technologies and Applications · 495 citations

12Extension of MC-net-based coalition structure generation: handling negative rules and externalitiesRyo Ichimura, Takato Hasegawa, Suguru Ueda et al.2011 · Adaptive Agents and Multi-Agent Systems · 10 citations

Scroll for more · 36 remaining

Similar papers

Complexity of Computing the Shapley Value in Partition Function Form GamesOskar Skibski2023 · Journal of Artificial Intelligence Research · 0 citations In Library

Computational Aspects of Extending the Shapley Value to Coalitional Games with ExternalitiesTomasz P. Michalak, Talal Rahwan, D. Marciniak et al.2010 · European Conference on Artificial Intelligence · 16 citations In Library

Complete null agent for games with externalitiesJ. M. Alonso-Meijide, M. Álvarez-Mozos, M. G. Fiestras-Janeiro et al.2019 · Expert systems with applications · 6 citations In Library

Efficient Computation of the Shapley Value for Game-Theoretic Network CentralityTomasz P. Michalak, Aadithya V. Karthik, Piotr L. Szczepanski et al.2014 · Journal of Artificial Intelligence Research · 206 citations In Library

Coalitional games induced by matching problems: Complexity and islands of tractability for the Shapley valueG. Greco, Francesco Lupia, Francesco Scarcello2020 · Artificial Intelligence · 11 citations In Library

Approximating the Shapley Value without Marginal ContributionsPatrick Kolpaczki, Viktor Bengs, Eyke Hüllermeier2023 · AAAI Conference on Artificial Intelligence · 53 citations In Library

Shapley Value Approximation Based on Complementary ContributionQiheng Sun, Jiayao Zhang, Jinfei Liu et al.2024 · IEEE Transactions on Knowledge and Data Engineering · 11 citations In Library

Stratified Sampling for Shapley Value Estimation: A Variance-Optimal ApproachAlberto Almech2026 · Zenodo (CERN European Organization for Nuclear Research) In Library

Unlocking the Game: Estimating Games in Möbius Representation for Explanation and High-Order Interaction DetectionMajid Mohammadi, Ilaria Tiddi, Annette ten Teije2025 · Proceedings of the AAAI Conference on Artificial Intelligence · 4 citations In Library

On the Computational Tractability of the (Many) Shapley ValuesReda Marzouk, Shahaf Bassan, Guy Katz et al.2025 · International Conference on Artificial Intelligence and Statistics · 14 citations In Library

Source of record

arXiv

44B

Welcome.

This panel sticks with you. Pick anything below and it opens right beside it, so you can dig through 60,000-plus records without ever losing your spot here.

Travel 44B

LibraryPapers, policy, standards, statute LabsEvery organization building AI ModelsIntelligence, price, and speed BenchmarksThe evaluation catalog IncidentsAI failures and harms SearchOne field across everything DashboardThe state of AI accountability in NY 44B RegistryThe Art. 44-B compliance portal