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). We show that every embedded/weighted MC-nets rule can be represented as (one or more) graphs and that each extended Shapley value can be expressed as the weighted sum over all proper vertex colorings in these graphs. 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.