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.

Charting the Tractability Frontier of Mixed Multi-Unit Combinatorial Auctions

Fionda, Valeria;Greco, Gianluigi
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.
2009
9781577354260
File in questo prodotto:
Non ci sono file associati a questo prodotto.

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/20.500.11770/162119
 Attenzione

Attenzione! I dati visualizzati non sono stati sottoposti a validazione da parte dell'ateneo

Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 5
  • ???jsp.display-item.citation.isi??? 1
social impact