|
Shao Chin Sung
Department Aoyama Gakuin University Department of Industrial and Systems Engineering, College of Science and Engineering Position Professor |
|
| Language | English |
| Publication Date | 2010/06 |
| Type | Academic Journal |
| Title | Computational complexity in additive hedonic games |
| Contribution Type | Collaboration |
| Journal | European Journal of Operational Research |
| Volume, Issue, Page | pp.635-639 |
| Author and coauthor | *Shao-Chin Sung and Dinko Dimitrov |
| Details | 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. |