Computer Science – Computer Science and Game Theory
Scientific paper
2011-01-05
Computer Science
Computer Science and Game Theory
17 pages
Scientific paper
We revisit the coalition structure generation problem in which the goal is to partition the players into exhaustive and disjoint coalitions so as to maximize the social welfare. One of our key results is a general polynomial-time algorithm to solve the problem for all coalitional games provided that player types are known and the number of player types is bounded by a constant. As a corollary, we obtain a polynomial-time algorithm to compute an optimal partition for weighted voting games with a constant number of weight values and for coalitional skill games with a constant number of skills. We also consider well-studied and well-motivated coalitional games defined compactly on combinatorial domains. For these games, we characterize the complexity of computing an optimal coalition structure by presenting polynomial-time algorithms, approximation algorithms, or NP-hardness and inapproximability lower bounds.
Aziz Haris
Keijzer Bart de
No associations
LandOfFree
Complexity of coalition structure generation 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 Complexity of coalition structure generation, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Complexity of coalition structure generation will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-267326