Recently, fractional hedonic games have received considerable attention. Such a game can be represented by directed weighted graph where the weight of edge (i; j) denotes the value player i has for player j. The utility of player i is the average value that player i assigns to the members of i's coalition. In this paper, we study a variant of this game where there is a speci c upper bound k on the number of coalitions that can be formed. We rst consider how to nd a coalition partition that maximizes the social welfare, i.e., the sum of the utilities. Computing social welfare maximizing partitions for these games of all agents on undirected unweighted graphs is known to be NP-hard. Here, we study the parameterized complexity in terms of k. For all xed k 2, we show that it remains NP-hard to nd a social welfare maximizing kpartition for undirected unweighted graphs. For undirected unweighted trees, we present an algorithm nding a social welfare maximizing kpartition in time O(nk). Moreover, we consider Nash stable outcomes. We show that for all k 2, if a fractional hedonic game on a directed unweighted graph with bounded maximum out-degree admits a Nash stable k-partition, then the stable partition is almost balanced. However, we prove that determining whether a fractional hedonic game admits a Nash stable k-partition is NP-complete for all k 2.
Community detection in social networks, or network partitioning, is an important topic in social network analysis. A social network is classically represented by a directed weighted graph over the agents, where a weighted link models the relationship between two agents in the social network. Intuitively, communities in a social network corresponds to groups of the vertices that are internally more densely connected than with the rest of the vertices in the network. Partitioning a social network into disjoint communities, or revealing the hidden community structure, can o er insights regarding the organization of a social network and can signi cantly simplify the network representation. Furthermore, in online marketing, such as placing online ads or deploying viral marketing strategies, ? Copyright ' JJJJ for this paper by its authors. Use permitted under Creative
Commons License Attribution 4.0 International (CC BY 4.0). identifying communities in the social network often leads to more accurate targeting and achieves better marketing results.
A key challenge of community detection is to formally de ne what is a
community. Various attempts from various perspectives have emerged in the
literature (see [
The eld of game theory focuses on interactions between intelligent
individuals. Thus, it is natural to apply game theory to capture the dynamics behind
the formation of communities in social networks. In recent work, there has been
a considerable amount of research on using game-theoretic techniques to study
community detection in social networks. We refer to [
Our results. We study a variant of FHGs where there is a speci c upper bound k on the number of coalitions that can be formed. To motivate the study, note that in many real-world scenarios, there are physical and organizational restrictions that limit the number of possible coalitions. Consider a setting in which each coalition requires a leader, and where only a small number of agents are quali ed to act as a leader. Thus, any feasible partition cannot contain more coalitions than the number of quali ed leaders.
A central concern of coalition formation games is to de ne what constitutes
an acceptable or desired outcome. Within our setting, we consider two key
objectives. Our rst objective is to nd a partition maximizing the social welfare,
i.e., the sum of the utilities of all players. As mentioned before, computing
social welfare maximizing partitions (with no restriction number of coalitions) is
proved to be NP-hard by Aziz et al. [
A social welfare maximizing partition may not satisfy every player and hence there may exist a player who could increase their utility by deviating to another coalition. Our second objective is to consider Nash stable partitions, where no player can improve their utility by unilaterally changing their coalition. We prove that for all k 2, if a Nash stable k-partition exists in an FHG represented by nnode directed unweighted graph with bounded maximum out-degree, then each coalition in such a k-partition is of size (n). We then study the computational complexity of nding a Nash stable k-partition. Unfortunately, for all k 2, we prove that it is NP-complete to determine whether an FHG played on a directed weighted graph with edge weights in f0; 1g admits a Nash stable k-partition.
Related works. Aziz et al. [
The restriction on the number of coalitions, which is the focus of the present
paper, has been mostly overlooked. Skibski et al. [
Paper organization. The remainder of the paper is organized as follows. Section 2 presents formal de nitions. Sections 3 and 4 present our results for social welfare maximizing k-partitions and Nash stable k-partitions, respectively. Section 5 o ers some concluding remarks. Due to space restrictions, some of the proofs are omitted. Complete proofs will be provided in the full version. 2
For all positive integers n, let [n] = f1; 2; : : : ; ng. In an FHG, we are given a set N = [n] of players. The objective of the game is to partition the players into disjoint coalitions P = fP1; P2; : : :g. Let (N ) denote the set of all partitions of players N , and for all integers k 1, let k(N ) denote the set of partitions in (N ) with exactly k coalitions. We refer to each partition in k(N ) as a k-partition.
Each player i has a value function vi : N ! R that denotes how much player i values each of the players in N . We assume that vi(i) = 0. Hence, every FHG can be represented by a tuple of valuation functions v = (v1; : : : ; vn). We often associate an FHG with a weighted directed graph. Given a tuple of valuation functions v, let G = (N; E; v) denote the weighted directed graph where the weight of the tuple (i; j) in N N is vi(j) and E contains all tuples of non-zero weight. Let G(G) denote the fractional hedonic game associated with G. When there is no ambiguity, we simply refer to the FHG G(G) as G.
For convenience, for each player i, we extend the input domain of the value function vi to N [ fP j P N ^ i 2 P g [ (N ). For any coalition P N that contains player i, the utility vi(P ) of agent i is de ned as Pj2jPP jvi(j) : For any partition P in (N ), let P(u) denote the coalition that contains player u, and the utility vi(P) of player vi in the partition P is de ned as vi(P(i)).
Given an FHG G(G) and a partition P, the social welfare SWG(P) of the partition P is de ned as the sum of the utilities of all players, i.e., SWG(P) = Pi2N vi(P). We often drop the subscript G when there is no ambiguity.
Given a partition P in (N ), we say a player i is Nash stable for P if there is no other coalition P 0 6= P(i) in P such that vi(P 0 [ f g i ) > vi(P). We say a partition P in (N ) is Nash stable if all players are Nash stable for P.
We use the following notations from graph theory. Let G = (N; E) be an unweighted graph. Given a subset U of N , we denote by EG(U ) the set of edges of G having both endpoints in U . Moreover, for two disjoint sets N1 and N2, we denote by EG(N1; N2) the set of edges having exactly one endpoint in N1 and exactly one endpoint in N2. We drop the subscript G when there is no ambiguity. For any graph G = (N; E) and any subset S of N , we let G[S] denote the subgraph of graph G induced by S.
We now state the two problems studied in this paper. { The social welfare maximizing k-partition problem: Given a fractional hedonic game G(G) and an integer k, nd a k-partition P in k(N ) that maximizes the social welfare SW (P). { The Nash stable k-partition problem: Given a fractional hedonic game G(G) and an integer k, determine whether there is a k-partition P in k(N ) that is Nash stable. 3
In this section, we focus on FHGs played on undirected unweighted graphs. We remark that for an FHG played on an undirected unweighted graph G = (N; E), the social welfare of any partition P in (N ) is SWG(P) = PP 2P 2jEjGP(jP )j . In the following, for FHGs played on undirected unweighted graphs, Section 3.1 establishes the NP-hardness of the social welfare maximizing k-partition problem for every xed k 2. For FHGs played on undirected unweighted trees, Section 3.2 presents an e cient algorithm that solves the social welfare maximizing kpartition problem for all k 2. 3.1
In this section, we prove Theorem 1 below.
Theorem 1. For FHGs played on unweighted undirected graphs, the social welfare maximizing k-partition problem is NP-hard for every xed k 2.
We separate our hardness proof into two parts: k 3 and k = 2.
When k 3, we reduce from the k-colorable problem, which was proved to
be NP-complete by Leven and Galil [
It remains to prove the case when k = 2. We reduce from the max cut
problem, which was proved to be NP-complete by Karp [
jS1jjS2j
Reduction. Let I = (G; r) denote an instance of the max cut problem, where G = (V; E) denotes an undirected graph and r denotes a positive integer. We construct an undirected unweighted graph G = (V ; E ) as an instance of the social welfare maximizing 2-partition problem as follows. For convenience, let n denote jV j and let m denote jEj.
We begin by constructing an undirected graph G0 = (V 0; E0), and then let G = (V 0; K0 n E0) be the complementary graph of G0, where K0 consists of all 2-element subsets of V 0. For each v in V , we have two sets Iv and Iv0 of vertices, each of size M = 4m + 2. Thus, G0 has 2nM vertices and V 0 = Sv2V Iv [ Iv0. For each v in V , we introduce edges connecting each vertex in Iv to each vertex in I0 . Pick one distinguished vertex from each Iv to form a set A of n vertices, v and pick one distinguished vertex from each Iv0 to form a set A0 of n vertices. We proceed to insert edges in A and A0 to create two copies of G. The resulting graph is G0.
To show that our reduction is correct, we rst prove two useful properties of social welfare maximizing k-partitions. Then, we prove Lemma 1, which establishes the correctness of our reduction.
Proposition 1. Let H = (V; E) be an undirected graph, and let H be the complementary graph of H. Let P be a 2-partition in (V ). Then SWH (P) = jV j 2 SWH (P).
Proof. Let n denote jV j. Note that SWH (P) = Pi2[
1
i2[
X vH (Pi) = n 2 SWH (P):
i2[
Therefore, we obtain SWG0 (P) =
X 2E(Pi)
i2[
M
1 jP1j
M 2nM 1 Lemma 1. Let G = (V; E) be an undirected graph and let (G; r) be an instance of the max cut problem. Let G be the corresponding instance of the social welfare maximizing 2-partition problem. Let n = jV j, m = jEj, and M = 4m + 2. Then G has a cut of cardinality r if and only if G has a 2-partition with social welfare at least 2nM 2 4mnM4r .
Proof. Let G0 be the complementary graph of G . By Proposition 1, it su ces to prove that G has a cut of cardinality r if and only if G0 has a 2-partition with social welfare at most 4mnM4r . We consider two cases.
Case 1: G has a cut (S1; S2) of cardinality r. For each i in f1; 2g, let Pi = fIv j v 2 Sig and Pi0 = fIv0 j v 2 Sig. Consider the 2-partition P0 = (P1 [ P20; P10 [ P2). It is straightforward to verify that jP1 [ P20j = jP10 [ P2j = nM . Moreover, notice that jEG0 (P1 [ P20)j = jEG0 (P1)j + jEG0 (P20)j = jEG(S1)j + jEG(S2)j = jEj jEG(S1; S2)j = m r. Similarly, we have jEG0 (P10 [ P2)j = m r. Thus, SW (P0) = 2jEG0 (P1 [ P20)j + 2jEG0 (P10 [ P2)j = 4m 4r : (1) jP1 [ P20j jP10 [ P2j nM Therefore, G0 has a 2-partition with social welfare at most 4m 4r .
Case 2: G0 has a 2-partition with social welfare at mostnM4m 4r . Consider nM a social welfare minimizing 2-partition P = (P1 ; P2 ) in G0. That is, we have SWG0 (P ) 4mnM4r . By Proposition 2, we deduce that for each v in V , P partitions Iv [ Iv0 into the two sets Iv and Iv0. Therefore, either Iv P1 and Iv0 P2 , or Iv P2 and Iv0 P1 . For each i in f1; 2g, let Si = fv 2 V j Iv Pi g
F. Li and Si0 = fv 2 V j Iv0 Pi g. Clearly, S1 = S20, S2 = S10, and (S1; S10) = (S20; S2) is a partition in 2(V ). Using a calculation similar to that used to derive Eq.(1), that jEG(S1; S10)j we have SWG0 (P ) = 4(m jEnGM(S1;S10)j) . Since SWG0 (P ) 4mnM4r , we deduce r. Therefore, G has a cut of cardinality at least r. tu 3.2
In this section, we rst prove Lemma 2, which presents a useful structural property of social welfare maximizing k-partitions on undirected unweighted trees. Then, based on this property, we present a simple O(nk)-time algorithm for the social welfare maximizing k-partitions problem on unweighted undirected trees. Lemma 2. Let G = (N; E) be a tree and let k be a positive integer. Let P in k(N ) be a social welfare maximizing k-partition with k coalitions P1 ; : : : ; Pk . Then, for all coalitions Pi in P , G[Pi ] is connected.
Proof. Note that a connected subgraph of a tree is a tree, and a disconnected subgraph of a tree is a forest. Assume for the sake of contradiction that there is a coalition Pi in P such that G[Pi ] is not connected, i.e., a forest. Suppose that G[Pi ] has p connected components, where p 2. Let (T1; T2; : : : ; Tp) be the partition of Pi such that G[T1]; : : : ; G[Tp] are all connected components in G[Pi ]. Let tw = jTwj for each w in [p] and pi = jPi j. That is, pi = Pw2[p] tw. Without loss of generality, assume that t1 t2 tp.
Since G is a tree, we deduce that there is another coalition Pj in P with j 6= i such that there is an edge between Pj and T1. Now we are ready to construct a k-partition P0 in k(N ) with SW (P0) > SW (P ), which contradicts the assumption that P is a social welfare maximizing k-partition.
We construct such a k-partition P0 with coalitions P10; : : : ; Pk0 as follows. For each t in [n] n fi; jg, let Pt0 = Pt . Furthermore, let Pi0 = Pi n T1 and Pj0 = Pj [ T1. Now we prove that SW (P0) > SW (P ). For all coalitions S of N , let d(S) = E(S)=jSj. Thus, SW (P0) = Pw2[k] 2d(P w0) and SW (P ) = Pw2[k] 2d(Pw). Hence it su ces to prove that d(Pi0) + d(Pj0) > d(Pi ) + d(Pj ). To prove this, it is enough to prove that d(Pi0) d(Pi ) and d(Pj0) > d(Pj ).
First, we prove that d(Pi0) d(Pi ). Recall that the subgraph G[Pi ] contains p trees G[T1]; : : : ; G[Tp], while the subgraph G[Pi0] contains trees G[T2]; : : : ; G[Tp]. Thus, d(Pi0) =
Ppw=2(tw
Pp w=2 tw 1) = 1 p pi 1 t1 ; d(Pi ) =
Ppw=1(tw
Pp w=1 tw 1) = 1 p pi : Now, to show that d(Pi0) d(Pi ), it su ces to show that ppi 1t1 p p t1 pi. The last inequality follows by t1 t2 tp and pi = Ppwp=i 1, tiw.e..,
Second, we prove that d(Pj0) > d(Pj ). Let pj = jPj j and ej = jE(Pj )j. That is, d(Pj ) = pejj . Since there is at least one edge connecting Pj and T1, we have d(Pj0) = jE(Pj [ T1)j pj + t1 jE(Pj )j + 1 + jE(T1)j = ej + t1
: pj + t1
pj + t1 tu Therefore, to prove d(Pj0) > d(Pj ), it su ces to prove pejj++tt11 > pejj , i.e., pj t1 > ej t1. This follows by the observation that any subgraph of a tree is either a tree or a forest, that is, ej pj 1 < pj .
Theorem 2. For all positive integers k, the social welfare maximizing k-partition problem can be solved in O(nk) time on undirected unweighted trees. Proof. By Lemma 2, we deduce that any social welfare maximizing k-partition on a tree is a partition into k subtrees. Notice that for trees, there is a one-to-one correspondence between removing k 1 edges and partitioning into k subtrees. Thus, in O(nk) time, one can simply enumerate each possible partition of k subtrees in G and identify the optimal one in in O(nk) time. 4
In this section, we consider Nash stable k-partitions for all k 2. Throughout this section, we assume that k 2 unless stated otherwise. As an independent result, Theorem 3 below shows that a Nash stable k-partition of an unweighted directed graph with bounded out-degree is almost balanced. Then, we prove that it is NP-complete to determine whether a directed weighted graph with edges weights 1 admits a Nash stable k-partition. We remark that a directed graph is strongly connected if there is a path in each direction between each pair of vertices of the graph.
Theorem 3. Let k 2 and 2 be two integers. Let G = (N; E) denote a directed unweighted strongly connected graph with out-degree bounded by and jN j k k+1. Assume that G(G) admits a Nash stable k-partition P in k(N ). Then all coalitions in P have size at least k nk 1 .
Proof. Let P1; : : : ; Pk denote the k coalitions in P with 0 < jP1j jP2j jPkj. It su ces to prove that jP1j k nk 1 . For any t in f0; 1; : : : ; k 1g, let Q(t) dheonldostefotrhaenpyrtedinicaft0e; 1jP;:k: : t;jk 1kgn. tC. lWeaerlyu,sQe(inkduc1t)ioimnpolniest tthoaptrjoPv1ej thakt nQk (1t).
For the base case, notice that 0 < jP1j jP2j jPkj, and hence jPkj k1 Pi2[k] jPij = nk . Therefore, Q(0) holds. For the induction step, let i in [k 1] be given and suppose that Q(t) holds for each t in f0; : : : ; i 1g. Then, we shall prove that Q(i) holds, i.e., jPk ij kn i . Since (P1; : : : ; Pk) belongs to k(N ), we deduce that Sj2[k i] Pj ; Sj2[k]n[k i] Pj is a 2-partition in 2(N ). Furthermore, since G is strongly connected, there is a directed edge (b; a) from Sj2[k]n[k i] Pj to Sj2[k i] Pj . Let Pi0 ; Pj0 with i0 k i; j0 k i + 1 denote the two coalitions that contain players a and b, respectively. Therefore, jPi0 j jPk ij and k j0 i 1. By the induction hypothesis, we deduce that Q(k j0) holds, i.e., jPj0 j k nk j0 k ni 1 . Below we prove that jPi0 j 1 jPj0 j. Since jPi0 j jPk ij and jPj0 j k ni 1 , we deduce that jPk ij jPi0 j 1 jPj0 j 1 k ni 1 = kn i , as required.
F. Li
It remains to prove that jPi0 j 1 jPj0 j. Since P is Nash stable, we deduce that each player is Nash stable. Since player b is Nash stable, we have vb(Pi0 [ fbg) vb(Pj0 ): (2) have jPj0 j jPi0 j jPi0 j + n k k+1 that Since (b; a) is a directed edge, we deduce that vb(a) = 1 and hence vb(Pi0 [fbg) = Pw2PjPi0i[0 jf+bg1vb(w) jPvib0(ja+)1 = jPi01j+1 : Furthermore, since the out-degree of player b is bounded by and a is an out-neighbor of b outside Pj0 , we deduce that b has at most 1 out-neighbors in Pj0 , that is, Pw2Pj0 vb(w) 1. Thus, vb(Pw) jPj01j . Using inequality (2), we have jPi01j+1 jPj01j . By rearranging, we 1. Furthermore, we deduce from Q(k j0) and jPj0 j k n k j0 k k k+1 k j0 = j0+1: Notice that j0 k i + 1 2 as i k 1. Therefore, we have 3 j0+1 jPi0 j jPi0 j + 1. Now, we prove that jPi0 j . Assume for the sake of contradiction that jPi0 j . Hence, we have jPi0 j jPi0 j + 1 2 + 1. Since 2, we deduce that 2 + 1 < 2 2 3, which contradicts 3 jPi0 j + 1. Hence jPi0 j .
jPi0 j jPi0 j + 1 jPi0 j + 1 < jPi0 j
Thus, jPj0 j jPi0 j > 1 jPj0 j. 4.1
In this section, for each k 2, we establish the NP-completeness of determining whether a directed weighted graph with edges weights 1 admits a Nash stable k-partition. We give an NP-completeness proof rst for k = 2 and then for k 3.
First, it is convenient for us to consider Nash stable partitions in FHGs played on undirected unweighted graphs with each player aiming to minimize the utility, rather than considering Nash stability in weighted directed graphs with negative edge weights. Formally, we state the following observation. Observation 4 Let H = (N; E; v) denote a directed weighted graph with edge weight 1. Let H0 = (N; E) denote the directed unweighted graph that contains the same vertices and edges as H. Let P denote a k-partition in k(N ) for all k 1. Then, the k-partition P is Nash stable in G(H) if and only if P is Nash stable in G(H0) with each player seeking to minimize, rather than maximize, their utility.
We now prove the following proposition, which will be used in our NPcompleteness proofs for both k = 2 and k 3.
Proposition 3. Let N denote the set of utility-minimizing players, and let k
2 be an integer. Let G(G) denote a fractional hedonic game, where G = (N; E) is
an unweighted directed graph. Let x in N denote a player such that x has exactly
k 1 out-neighbors y1; : : : ; yk 1 in G. Then, for all Nash stable k-partitions P
in k(N ), we have P(x) 6= P(yi) for each i in [k 1].
jPi0 j, i.e.,
tu
Proof. Assume for the sake of contradiction that there is an index i in [k 1]
such that P(x) = P(yi). That is, vx(P(x)) = vx(P(yi)) > 0 since yi is in P(yi)
and yi is an out-neighbor of x. Since x has exactly k 1 out-neighbors, there
is a coalition P in the k-partition P such that P does not contain x and any
out-neighbors of x. Therefore, vx(P [ fxg) = 0 < vx(P(x)). That is, the
utilityminimizing player x is not Nash stable for P, a contradiction. tu
Nash Stable 2-Partition For k = 2, we reduce from the balanced unfriendly
2-partition problem. A 2-partition of an undirected graph is called unfriendly if
each vertex has at least as many neighbors outside its part as within. Bazgan et
al. [
Lemma 4. For FHGs with utility-minimizing players and played on directed unweighted graphs, the Nash stable k-partition problem is NP-complete for all k 3.
Proof. Clearly, this problem is in NP. For hardness, we reduce from the NPcomplete problem stated in Lemma 3. Let G = (V; E) denote an instance of the problem stated in Lemma 3, where G is a directed unweighted graph with an isolated 2-cycle of vertices p1; p2. Let n denote jV j, and suppose that n 3. We construct a directed unweighted graph G0 = (V 0; E0) as follows.
The graph G0 has all vertices in V , and all edges in E. Note that p1; p2 are the two vertices of the isolated 2-cycle in G. Add k 2 vertices, p3; : : : ; pk, and add edges letting p1; p2; : : : ; pk form a clique, i.e., add directed edges (pi; pj ) for each i 6= j in [k] unless fi; jg = f1; 2g. Let M = n2 2n + 2. For each j in f3; : : : ; kg, add M dummy vertices dj;q for each q in [M ], and add edges connecting these dummy vertices dj;q to all vertices pi for each i in [k] n fjg. That is, for each j in f3; : : : ; kg, the vertices in the set fpj g [ fdj;q j q 2 [M ]g have the same k 1 outneighbors. Add edges connecting all vertices in V n fp1; p2g to dummy vertices dj;q for all j in f3; : : : ; kg and all q in [M ]. In total, G0 has n + k 2 + (k 2)M vertices. Claims 1 and 2 below imply that the lemma holds
Claim 1: If G admits a Nash stable 2-partition P = (P1; P2) for utilityminimizing players, then G0 admits a Nash stable k-partition for utility-minimizing players.
F. Li
Let P0 denote the k-partition (Pi0)i2[k], where P10 = P1; P20 = P2; and Pi0 = fpig [ fdi;q j q 2 [M ]g for each i in f3; : : : ; ng. Clearly, for each i in f3; : : : ; ng, all players in Pi0 = fpig [ fdi;q j q 2 [M ]g have utility 0, and hence are Nash stable. To prove that P0 is Nash stable, it remains to prove that all of the players in P 0
1 [ P20 are Nash stable. Assume for the sake of contradiction that there exists
an integer i in [
j p ) = M=(M + 2) = 1 2=(M + 2). Moreover, p has at most jPi0j 1 out-neighbors in Pi0 and has utility at most 1 1=jPi0j 1 1=(n 1) as jPi0j = jPij = jV n P3 ij n 1. Note that M = n2 2n + 2 = (n 1)2 + 1 > 2n 2 as n 3. Therefore, we have 2=(M + 2) < 1=n, i.e., vp(Pj0 [ fpg) = 1 2=(M + 2) > 1 1=n vp(Pi0). Thus, player p's utility does not decrease by letting p deviate to Pj0, a contradiction. This completes the proof of Claim 1.
Claim 2: If G0 admits a Nash stable k-partition P0 = (Pi0)i2[k] in k(V 0), then G admits a Nash stable 2-partition.
Notice that for each i in [k], the player pi has k 1 out-neighbors in fpj j j 2 [k] n figg. Thus, we deduce by Proposition 3 that P0(pi) 6= P0(pj ) for all j in [k] n fig. Therefore, the k vertices p1; : : : ; pk belong to distinct coalitions in the k-partition. Without loss of generality, suppose that Pi0 contains pi for all i in [k]. That is, P0(pi) = Pi0 for all i in [k]. It now su ces to prove that (P10; P20) is a 2-partition in 2(V ). After we prove this, the desired statement that G admits the Nash stable 2-partition (P10; P20) directly follows, since the Nash stability of (P10; P20) follows by the Nash stability of P0 = (Pi0)i2[k].
To prove that (P10; P20) is in 2(V ), it su ces to prove that P10 [P20 = V . That
is, it is enough to prove that V 0 n V Si2f3;:::;kg Pi0 and V \ Si2f3;:::;kg Pi0 = ;.
We rst prove that V 0 n V Si2f3;:::;kg Pi0. Since pi belongs to Pi0 for each i in
[k] n [
j . That is, we obtain that P0(dj;q) = Pj0 for all i in [k] n fjg. Therefore,
for all j in [k] n [
The theorem below summarizes the main result of this section.
Theorem 5. For FHGs played on directed weighted graphs where all edges have weight 1, the Nash stable k-partition problem is NP-complete for every xed k 2. 5
Following the direction of using game-theoretic methods to study community detection, we initiated the study of the fractional hedonic games by restricting the number of coalitions. We considered this scenario from two aspects: social welfare maximization and Nash stability. We applied parameterized complexity theory to understand the computational barriers.
For future work, given our NP-hardness results, we propose to design
approximation algorithms or heuristic algorithms. As a starting point, one could study
the approximation algorithms for nding social welfare maximizing k-partition in
FHGs played on undirected unweighted graphs. Note that for this problem, it is
easy to see that the classical algorithm nding a densest subgraph by Goldberg
[