ソン　ショウシュウ   Shao Chin Sung   宋　少秋    所属   青山学院大学  理工学部 経営システム工学科    職種   教授
言語種別	英語
発行・発表の年月	2010/06
形態種別	学術雑誌
標題	Computational complexity in additive hedonic games
執筆形態	共同
掲載誌名	European Journal of Operational Research
巻・号・頁	pp.635-639
著者・共著者	*Shao-Chin Sung and Dinko Dimitrov
概要	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.