全球智库信息集成服务系统(G2TT): Computational Complexity in Additive Hedonic Games

G2TT

来源类型	FEEM working papers "Note di lavoro" series
规范类型	论文
	Computational Complexity in Additive Hedonic Games
	Dinko Dimitrov; Shao-Chin Sung
发表日期	2008
出处	Climate Change and Sustainable Development
出版年	2008
语种	英语
摘要	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.
特色分类	C63,C70,C71,D02,D70,D71
关键词	Additive Preferences,Coalition Formation,Computational Complexity,Hedonic Games,NP-hard,NP-complete
URL	https://www.feem.it/en/publications/feem-working-papers-note-di-lavoro-series/computational-complexity-in-additive-hedonic-games/
来源智库	Fondazione Eni Enrico Mattei (Italy)
资源类型	智库出版物
条目标识符	http://119.78.100.153/handle/2XGU8XDN/117622
推荐引用方式 GB/T 7714	Dinko Dimitrov,Shao-Chin Sung. Computational Complexity in Additive Hedonic Games. 2008.