Computer Science – Computer Science and Game Theory
Scientific paper
2011-05-09
Computer Science
Computer Science and Game Theory
16 pages
Scientific paper
We consider coalition formation games in which each player has preferences over the other players and his preferences over coalitions are based on the best player ($\mathcal{B}$-/B-hedonic games) or the worst player ($\mathcal{W}$/W-hedonic games) in the coalition. We show that for $\mathcal{B}$-hedonic games, an individually stable partition is guaranteed to exist and can be computed efficiently. Similarly, there exists a polynomial-time algorithm which returns a Nash stable partition (if one exists) for $\mathcal{B}$-hedonic games with strict preferences. Both $\mathcal{W}$- and W-hedonic games are equivalent if individual rationality is assumed. It is also shown that for B- or $\mathcal{W}$-hedonic games, checking whether a Nash stable partition or an individually stable partition exists is NP-complete even in some cases for strict preferences. We identify a key source of intractability in compact coalition formation games in which preferences over players are extended to preferences over coalitions.
Aziz Haris
Harrenstein Paul
Pyrga Evangelia
No associations
LandOfFree
Individual-based stability in hedonic games depending on the best or worst players 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 Individual-based stability in hedonic games depending on the best or worst players, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Individual-based stability in hedonic games depending on the best or worst players will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-278417