Stable partitions in additively separable hedonic games

Details Stable partitions in additively separable hedonic games Stable partitions in additively separable hedonic games

2010-07-31

arxiv.org/abs/1008.0074v3

Computer Science

Computer Science and Game Theory

13 pages, 5 Figures

Scientific paper

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 NP-hard 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 contractually strict core stable or Pareto optimal is coNP-complete.

Affiliated with

Also associated with

No associations

Rating

Stable partitions in additively separable hedonic games does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Stable partitions in additively separable hedonic games, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Stable partitions in additively separable hedonic games will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-8651