Instruct: Identify the main and secondary category of Arxiv papers based on the titles and abstracts
Query: Complexity of coalition structure generation   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.

25
The categories of this paper are: patt-sol
31
The categories of this paper are: ao-sci
12
The categories of this paper are: nucl-th
8
The categories of this paper are: hep-ex
18
The categories of this paper are: econ
32
The categories of this paper are: atom-ph
19
The categories of this paper are: eess
15
The categories of this paper are: nucl-ex
2
The categories of this paper are: math
10
The categories of this paper are: q-bio
30
The categories of this paper are: q-alg
22
The categories of this paper are: chao-dyn
5
The categories of this paper are: gr-qc
16
The categories of this paper are: stat
4
The categories of this paper are: cond-mat
11
The categories of this paper are: hep-lat