Sabiia Seb
PortuguêsEspañolEnglish
Embrapa
        Busca avançada

Botão Atualizar


Botão Atualizar

Registro completo
Provedor de dados:  AgEcon
País:  United States
Título:  Computational Complexity in Additive Hedonic Games
Autores:  Sung, Shao Chin
Dimitrov, Dinko
Data:  2009-01-15
Ano:  2008
Palavras-chave:  Additive Preferences
Coalition Formation
Computational Complexity
Hedonic Games
NP-hard
NP-complete
Research Methods/ Statistical Methods
C63
C70
C71
D02
D70
D71
Resumo:  We investigate the computational complexity of several decision problems in hedonic coalition formation games and demonstrate that attaining stability in such games remains NP-hard even when they are additive. Precisely, we prove that when either core stability or strict core stability is under consideration, the existence problem of a stable coalition structure is NP-hard in the strong sense. Furthermore, the corresponding decision problems with respect to the existence of a Nash stable coalition structure and of an individually stable coalition structure turn out to be NP-complete in the strong sense.
Tipo:  Working or Discussion Paper
Idioma:  Inglês
Identificador:  http://purl.umn.edu/46655
Relação:  Fondazione Eni Enrico Mattei (FEEM)>Coalition Theory Network Working Papers
CTN
98.2008
Formato:  36
Fechar
 

Empresa Brasileira de Pesquisa Agropecuária - Embrapa
Todos os direitos reservados, conforme Lei n° 9.610
Política de Privacidade
Área restrita

Embrapa
Parque Estação Biológica - PqEB s/n°
Brasília, DF - Brasil - CEP 70770-901
Fone: (61) 3448-4433 - Fax: (61) 3448-4890 / 3448-4891 SAC: https://www.embrapa.br/fale-conosco

Valid HTML 4.01 Transitional