Optimal Partitions in Additively Separable Hedonic Games

Details Optimal Partitions in Additively Separable Hedonic Games Optimal Partitions in Additively Separable Hedonic Games

2010-05-25

arxiv.org/abs/1005.4540v3

Computer Science

Computer Science and Game Theory

11 pages; A preliminary version of this work was invited for presentation in the session `Cooperative Games and Combinatorial

Scientific paper

We conduct a computational analysis of fair and optimal partitions in additively separable hedonic games. We show that, for strict preferences, a Pareto optimal partition can be found in polynomial time while verifying whether a given partition is Pareto optimal is coNP-complete, even when preferences are symmetric and strict. Moreover, computing a partition with maximum egalitarian or utilitarian social welfare or one which is both Pareto optimal and individually rational is NP-hard. We also prove that checking whether there exists a partition which is both Pareto optimal and envy-free is $\Sigma_{2}^{p}$-complete. Even though an envy-free partition and a Nash stable partition are both guaranteed to exist for symmetric preferences, checking whether there exists a partition which is both envy-free and Nash stable is NP-complete.

Affiliated with

Also associated with

No associations

Rating

Optimal 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 Optimal Partitions in Additively Separable Hedonic Games, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Optimal Partitions in Additively Separable Hedonic Games will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-298058