2011 · 44 citations · 18 references
Social SciencesComputer ScienceAlgorithmsCombinatoricsGame TheoryAlgorithmic Game TheoryCoalition FormationCooperative Game TheoryCoordination GamesNash EquilibriumPareto OptimalityComputational Complexity Of DecompositionNoncooperative Coalition FormationPolynomial Time ComplexityPolynomial-time Algorithms
An important aspect in systems of multiple autonomous agents is the exploitation of synergies via coalition formation. In this paper, we solve various open problems concerning the computational complexity of stable partitions in additively separable hedonic games. First, we propose a polynomial-time algorithm to compute a contractually individually stable partition. This contrasts with previous results such as the NP-hardness of computing individually stable or Nash stable partitions. Secondly, we prove that checking whether the core or the strict core exists is NPhard in the strong sense even if the preferences of the players are symmetric. Finally, it is shown that verifying whether a partition consisting of the grand coalition is contractual strict core stable or Pareto optimal is coNP-complete.
18
Theory of Games and Economic Behavior
E. N., John von Neumann, Oskar Morgenstern · The Journal of Philosophy · 1945 · 4.1K citations
Coalition structure generation with worst case guarantees
Tüomas Sandholm, Kate Larson, Martin Andersson et al. · Artificial Intelligence · 1999 · 743 citations