AAAI Publications, Twenty-First International Joint Conference on Artificial Intelligence

Font Size: 
On the Complexity of Compact Coalitional Games
Gianluigi Greco, Enrico Malizia, Luigi Palopoli, Francesco Scarcello

Last modified: 2009-06-24


A significantly complete account of the complexity underlying the computation of relevant solution concepts in compact coalitional games is provided. The starting investigation point is the setting of graph games, about which various long-standing open problems were stated in the literature. The paper gives an answer to most of them, and in addition provides new insights on this setting, by stating a number of complexity results about some relevant generalizations and specializations. The presented results also pave the way towards precisely carving the tractability frontier characterizing computation problems on compact coalitional games.


Coalitional Games; Computational Complexity; Bargaining Set; Kernel; Nucleolus; Graph Games; Bounded Treewidth

Full Text: PDF