On the Complexity of the Core over Coalition Structures
Abstract
The computational complexity of relevant corerelatedquestions for coalitional games is addressed from the coalition structure viewpoint, i.e., withoutassuming that the grand-coalition necessarily forms. In the analysis, games are assumed to be 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.
Cite
Text
Greco et al. "On the Complexity of the Core over Coalition Structures." International Joint Conference on Artificial Intelligence, 2011. doi:10.5591/978-1-57735-516-8/IJCAI11-047Markdown
[Greco et al. "On the Complexity of the Core over Coalition Structures." International Joint Conference on Artificial Intelligence, 2011.](https://mlanthology.org/ijcai/2011/greco2011ijcai-complexity/) doi:10.5591/978-1-57735-516-8/IJCAI11-047BibTeX
@inproceedings{greco2011ijcai-complexity,
title = {{On the Complexity of the Core over Coalition Structures}},
author = {Greco, Gianluigi and Malizia, Enrico and Palopoli, Luigi and Scarcello, Francesco},
booktitle = {International Joint Conference on Artificial Intelligence},
year = {2011},
pages = {216-221},
doi = {10.5591/978-1-57735-516-8/IJCAI11-047},
url = {https://mlanthology.org/ijcai/2011/greco2011ijcai-complexity/}
}