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 problemswere 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.
On the Complexity of Compact Coalitional Games
GRECO, Gianluigi;PALOPOLI, Luigi;SCARCELLO F.
2009-01-01
Abstract
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 problemswere 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.I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
