Nash Stability in Additively Separable Hedonic Games and Community Structures |
| |
Authors: | Martin Olsen |
| |
Affiliation: | (1) MADALGO, Department of Computer Science, University of Aarhus, Aabogade 34, 8200 Aarhus N, Denmark |
| |
Abstract: | We prove that the problem of deciding whether a Nash stable partition exists in an Additively Separable Hedonic Game is NP-complete.
We also show that the problem of deciding whether a non trivial Nash stable partition exists in an Additively Separable Hedonic Game with non-negative and symmetric preferences is NP-complete. We motivate our study of the computational complexity by linking Nash stable partitions in Additively
Separable Hedonic Games to community structures in networks. Our results formally justify that computing community structures
in general is hard.
The research is partly sponsored by the company Cofman (). |
| |
Keywords: | Additively separable hedonic games NP-completeness Nash stability Community structures |
本文献已被 SpringerLink 等数据库收录! |