On The Complexity of the Core over Coalition Structures
Gianluigi Greco, Enrico Malizia, Luigi Palopoli and Francesco Scarcello
The computational complexity of core-related questions for coalitional games is addressed from the coalition structure viewpoint, i.e., without assuming that the grand-coalition necessarily forms. In order to avoid the exponential blow-up that results by explicitly listing all associations of coalitions with their worths, in the analysis, games are assumed to be given in "compact" form, i.e., their worth functions are implicitly given as polynomial-time computable functions over succinct game encodings provided as input. Within this setting, a complete picture of the complexity issues arising with the core, as well as with the related stability concepts of least core and cost of stability, is depicted. In particular, the special cases of superadditive games and of games whose sets of feasible coalitions are restricted over tree-like interaction graphs are also studied.