Abstract
This paper investigates the computational complexity of calculating the Shapley value in coalitional games characterized by externalities, where the payoff of a coalition depends on the actions of non-members. By mapping logic-based game representations (MC-nets) to graph-theoretic problems, the study establishes that while compact representations reduce storage requirements, they often render the computation of fair payoff distributions intractable. Specifically, most extensions of the Shapley value to games with externalities are shown to be #P-complete, with the McQuillin (MQ) value being a notable exception.
Introduction
In traditional coalitional game theory, the value generated by a group of agents is independent of the behavior of agents outside that group. However, real-world scenarios—such as market competition or environmental agreements—frequently involve externalities, where the formation of one coalition affects the profits of others. The Shapley value serves as a foundational solution concept for "fair" payoff distribution, but its extension to games with externalities is non-trivial due to the exponential explosion of possible coalition structures (partitions).
While several extensions (MQ, EF, HY, SS, and MY values) and compact representation languages like Marginal Contribution nets (MC-nets) have been proposed, the computational complexity of calculating these values using these representations was previously unknown.
Methods: Graph-Theoretic Reductions
The author evaluates the complexity of computing Shapley value extensions using two primary representations: embedded MC-nets and weighted MC-nets. The core methodology involves a novel reduction strategy:
- Representation Analysis: The paper focuses on how logic-based rules represent games compactly.
- Graph Mapping: The core technical innovation is showing that every rule in these MC-nets can be represented as a graph, where vertices correspond to players or groups of players.
- Weighted Coloring Counting: The author proves that computing an extended Shapley value is equivalent to "Weighted Coloring Counting"—calculating a weighted sum over all proper vertex colorings of these graphs.
- Reductions: To prove hardness, the author reduces well-known #P-complete problems (like counting independent sets or matchings) to the task of computing specific Shapley value extensions.
Key Results
The study reveals a significant trade-off between the conciseness of a representation and its computational tractability. Weighted MC-nets, which are more expressive and compact than embedded MC-nets, make computing the Externality-Free (EF) value #P-complete, whereas it remains in P for embedded MC-nets.
The McQuillin (MQ) value is identified as the most computationally robust extension, remaining in polynomial time (P) for both representations. This is attributed to its focus on relatively simple partitions involving at most two coalitions. In contrast, the Hu-Yang (HY), Stochastic (SS), and Myerson (MY) values are consistently #P-complete across both representations.
Discussion and Future Work
The findings suggest that while MC-nets are effective for storage, they may be unsuitable for applications requiring exact calculations of HY, SS, or MY values. The author notes that a different representation—partition decision trees—allows all five values to be computed in polynomial time, suggesting a better path forward for developers.
Since most of these problems are #P-complete, a natural next step is investigating whether these values can be efficiently approximated rather than calculated exactly. Future research may also address other proposed values, such as the Bolger value, which were not covered in this study.
Summary updated