TL;DR
This paper investigates the computational complexity of solution concepts in coalitional games, specifically focusing on the "core" and its variations, when players can form coalition structures (subgroups) instead of always acting as a single grand coalition. The authors provide a complete complexity picture for these concepts under various game structures, including superadditive games and games with restricted interaction graphs, revealing that coalition structures introduce significant computational challenges.
What Problem Does This Paper Address?
Coalitional game theory often assumes players will form a single "grand coalition" to maximize their collective gain. Solution concepts like the "core" then focus on how to distribute the total worth of this grand coalition fairly and stably. However, in many real-world scenarios (e.g., economics, politics), players might form smaller, stable subgroups or "coalition structures" because this can sometimes yield a higher total worth than the grand coalition.
When coalition structures are possible, traditional solution concepts become inadequate. This paper addresses the computational complexity of applying these concepts (like the core, least core, and cost of stability) in the context of coalition structures. Specifically, it asks:
- How complex are core-related problems for superadditive games? (Superadditive games are those where the worth of a union of disjoint coalitions is at least the sum of their individual worths, a common assumption).
- How complex are these concepts when players can form arbitrary coalition structures?
- Do restrictions on coalition formation (e.g., based on interaction graphs like trees) simplify these problems?
The paper also considers games where the worth function is not explicitly given but can be computed efficiently (polynomial-time computable worth functions), which is crucial for analyzing large games.
Methods
The paper employs a rigorous complexity-theoretic approach, analyzing problems in terms of their membership in complexity classes like P, NP, co-NP, and ∆. Key methods include:
- Reductions: The authors use reductions from known hard problems (like Boolean formula unsatisfiability) to prove hardness results for the coalitional game problems. This means if you could solve the coalitional game problem efficiently, you could also solve the known hard problem efficiently.
- Novel Characterizations: They derive new mathematical characterizations for coalition structure cores and costs of stability. For instance, they show that the coalition structure core can be characterized using the "cohesive cover" of a game, which simplifies analysis.
- Complexity Class Analysis: Problems are analyzed for membership in complexity classes (e.g., co-NP-complete, ∆-complete) and for hardness within those classes.
- Polynomial-Time Computable Worth Functions: The analysis assumes that the worth of any coalition can be computed in polynomial time, which is a standard assumption for studying complexity in compact game representations.
Datasets
Not discussed in the paper. The paper focuses on theoretical complexity analysis rather than empirical evaluation on specific datasets.
Key Insights and Ideas
- Coalition Structures Add Complexity: The most significant finding is that allowing players to form arbitrary coalition structures dramatically increases the computational complexity of core-related problems compared to scenarios where only the grand coalition is considered.
- Cohesive Covers Simplify Analysis: The concept of a "cohesive cover" provides a useful tool for analyzing coalition structure cores, linking them to the core of the original game.
- Bounded Treewidth Isn't Always Enough: While restricting interaction graphs to tree-like structures (bounded treewidth) often simplifies problems in other areas of AI and game theory, this paper shows that for core-related concepts with coalition structures, even these restrictions don't necessarily lead to tractability. Many problems remain hard (∆-hard) even for games with treewidth 2.
- Superadditivity vs. Coalition Structures: The paper clarifies the interplay between superadditivity and coalition structures, showing that while superadditive games have certain properties, the complexity of core concepts can still be high when coalition structures are allowed.
Key Results
The paper provides a comprehensive complexity landscape for core-related problems:
- Superadditive Games: CORE-NONEMPTINESS and CORE-CHECK are co-NP-complete. COS and LCV are also co-NP-complete. Hardness holds even for superadditive games.
- Arbitrary Coalition Structures:
- CS-CORE-CHECK is co-NP-complete.
- CS-CORE-NONEMPTINESS, CS-COS, and CS-LCV are ∆-complete. This is a significant result, showing these problems are at least as hard as problems solvable with an NP oracle and a polynomial-time algorithm.
- Restricted Interaction Graphs (Treewidth 2): The hardness results for CS-CORE-NONEMPTINESS, CS-COS, and CS-LCV still hold even when the game's interaction graph has a treewidth of 2. This means structural restrictions don't offer a computational escape hatch for these problems.
Limitations and Future Work
- Computational Setting: The analysis is primarily theoretical, focusing on complexity classes. While the results are general for polynomial-time computable worth functions, specific algorithms for solving these problems in practice are not detailed.
- Specific Game Classes: While the paper touches upon superadditive games and games with bounded treewidth, further investigation into other specific classes of games might reveal more nuanced complexity results.
- Practical Implications: The paper highlights the computational intractability of many core-related problems in the presence of coalition structures. Future work could explore approximation algorithms or heuristics that can provide practical solutions for these complex scenarios.
- Other Solution Concepts: The paper focuses on the core, least core, and cost of stability. Extending this analysis to other solution concepts in the context of coalition structures would be valuable.
Summary updated