On the Complexity of the Core over Coalition Structures

Greco, Gianluigi; Malizia, Enrico; Palopoli, Luigi; Scarcello, Francesco

doi:10.5591/978-1-57735-516-8/IJCAI11-047

On the Complexity of the Core over Coalition Structures

Gianluigi Greco, Enrico Malizia, Luigi Palopoli, Francesco Scarcello

Download BibTeX Cite

Proceedings of the Twenty-Second International Joint Conference on Artificial Intelligence. Pages 216-220.

https://doi.org/10.5591/978-1-57735-516-8/IJCAI11-047

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.

Gianluigi Greco, Enrico Malizia, Luigi Palopoli, and Francesco Scarcello. 2011. On the Complexity of the Core over Coalition Structures. In Proceedings of the Twenty-Second International Joint Conference on Artificial Intelligence, IJCAI-11. IJCAI, 216–220. https://doi.org/10.5591/978-1-57735-516-8/IJCAI11-047

@inproceedings{ijcai2011p47,
  title     = {On the Complexity of the Core over Coalition Structures},
  author    = {Greco, Gianluigi and Malizia, Enrico and Palopoli, Luigi and Scarcello, Francesco},
  booktitle = {Proceedings of the Twenty-Second International Joint Conference on
               Artificial Intelligence, {IJCAI-11}},
  publisher = {AAAI Press/International Joint Conferences on Artificial Intelligence},
  editor    = {Toby Walsh},
  pages     = {216--220},
  year      = {2011},
  month     = {7},
  doi       = {10.5591/978-1-57735-516-8/IJCAI11-047},
  url       = {https://doi.org/10.5591/978-1-57735-516-8/IJCAI11-047},
}

TY  - CPAPER
TI  - On the Complexity of the Core over Coalition Structures
AU  - Greco, Gianluigi
AU  - Malizia, Enrico
AU  - Palopoli, Luigi
AU  - Scarcello, Francesco
T2  - Proceedings of the Twenty-Second International Joint Conference on Artificial Intelligence, IJCAI-11
PB  - AAAI Press/International Joint Conferences on Artificial Intelligence
PY  - 2011
SP  - 216
EP  - 220
DO  - 10.5591/978-1-57735-516-8/IJCAI11-047
UR  - https://doi.org/10.5591/978-1-57735-516-8/IJCAI11-047
ER  -