# On a Simple Hedonic Game with Graph-Restricted Communication

Vittorio Bilò, Laurent Gourvès, Jérôme Monnot

<figure><img src="image_1.png" /></figure>

## To cite this version:

Vittorio Bilò, Laurent Gourvès, Jérôme Monnot. On a Simple Hedonic Game with Graph-Restricted Communication. Journal of Artificial Intelligence Research, 2025, 84, 10.1613/jair.1.14956. hal-05350463

HAL Id: hal-05350463

https://hal.science/hal-05350463v1

Submitted on 6 Nov 2025

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_2.png" /></figure>
# On a Simple Hedonic Game with Graph-Restricted Communication

VITTORIO BILÒ, University of Salento, Italy

LAURENT GOURVÈS, Université Paris-Dauphine, Université PSL, CNRS, LAMSADE, France

JÉRÔME MONNOT, Université Paris-Dauphine, Université PSL, CNRS, LAMSADE, France

We study a hedonic game for which feasible coalitions are prescribed by a graph representing the agents' social relations. A group of agents can form a feasible coalition if and only if their corresponding vertices can be spanned with a star. This requirement guarantees that agents are connected, close to each other, and one central agent can coordinate the actions of the group. In our game, everyone strives to join the largest feasible coalition. We study the existence and computational complexity of both Nash stable and core stable partitions. Then, we provide tight or asymptotically tight bounds on their efficiency, measured in terms of the price of anarchy and the price of stability, under two natural social functions, namely, the number of agents who are not in a singleton coalition, and the number of coalitions. We also derive refined bounds for games in which the social graph is claw-free. Finally, we investigate the complexity of computing socially optimal partitions, as well as extreme Nash stable ones.

**JAIR Associate Editor:** Sanmay Das

**JAIR Reference Format:**

Vittorio Bilò, Laurent Gourvès, and Jérôme Monnot. 2025. On a Simple Hedonic Game with Graph-Restricted Communication. *Journal of Artificial Intelligence Research* 84, Article 7 (September 2025), 23 pages. doi: 10.1613/jair.1.14956

## 1 Introduction

Coalition formation, that is the process by which agents gather into groups, is a fervent research topic at the intersection of Multi-Agent Systems, Computational Social Choice and Algorithmic Game Theory. One of the most studied models of coalition formation is that of *hedonic games* (Banerjee et al. 2001; Bogomolnaia and Jackson 2002; Drèze and Greenberg 1980; Hoefer et al. 2018), where agents have preferences over all possible coalitions they can belong to. As agents are usually assumed to be self-interested, an acceptable *outcome* for a hedonic game, that is a partition of agents into coalitions, needs to be resistant to agents' deviations. Several notions of stability have been investigated in the literature, such as, individual stability, Nash stability, core stability (see, for instance, (Aziz and Savani 2016)).

Igarashi and Elkind (2016) add a further constraint to the definition of acceptable outcomes for hedonic games, by introducing the notion of *feasible coalition*: a coalition is feasible if and only if it complies with some prescribed properties. For instance, they assume that the set of agents corresponds to the vertex set of a social graph $G$ and require a coalition to *induce a connected subgraph* of $G$.

In this work, we strengthen the feasibility constraint of Igarashi and Elkind (2016) to coalitions inducing a subgraph of $G$ *admitting a spanning star*. This requirement guarantees that agents are connected, close to each other, and at least one central agent can coordinate the actions of the group. We stress that we are not requiring the coalition to induce a spanning star, but simply to induce a subgraph containing one. We apply this framework

Authors' Contact Information: Vittorio Bilò, ORCID: 0000-0001-7848-4904, vittorio.bilo@unisalento.it, University of Salento, Lecce, Italy; Laurent Gourvès, ORCID: 0000-0002-5076-1583, laurent.gourves@dauphine.fr, Université Paris-Dauphine, Université PSL, CNRS, LAMSADE, Paris, France; Jérôme Monnot, ORCID: 0000-0002-7452-6553, Université Paris-Dauphine, Université PSL, CNRS, LAMSADE, Paris, France.

<figure><img src="image_3.png" /></figure>

This work is licensed under a Creative Commons Attribution International 4.0 License.

© 2025 Copyright held by the owner/author(s).

DOI: 10.1613/jair.1.14956
to a basic model, falling within the class of anonymous hedonic games (Banerjee et al. 2001), in which each agent's preference only depends on the cardinality of the coalition she belongs to.

## 1.1 Game Model, Definitions and Notation

Given an unweighted and undirected graph $G = (V, E)$ with $|V| = n$, a *coalition* is any non-empty subset of $V$. A *partition* of $V$ is a set of pairwise disjoint coalitions whose union equals $V$. We denote by $\mathcal{F} \subseteq 2^V$ the set of *feasible coalitions*. We shall consider

$$ \mathcal{F} = \{C \in 2^V : G[C] \text{ can be spanned with a star}\}, $$

where $G[C]$ is the subgraph of $G$ induced by $C$ and a star is a tree of depth at most 1. A star on one vertex will be called *trivial*. A partition is feasible if all of its coalitions are feasible.

Given an undirected, unweighted and connected graph $G$, game $(G, \mathcal{F})$ is defined as follows. Each vertex of $G$ is associated with an agent in the game. Let $\Pi$ be the set of partitions of $V$ and $\Pi_{\mathcal{F}} \subseteq \Pi$ be the set of feasible partitions of $V$. Observe that every game admits at least one feasible partition where every agent is alone. For a partition $\pi \in \Pi$ and a vertex $i \in V$, denote as $\pi(i)$ the coalition in $\pi$ containing $i$. All agents share the same preference relations over coalitions which is defined as follows. For two coalitions $C, C' \in \Pi$, we have $C \sim C'$ if $C, C' \notin \mathcal{F}$, $C \prec C'$ if $C \notin \mathcal{F}$ and $C' \in \mathcal{F}$, $C \sim C'$ if $C, C' \in \mathcal{F}$ and $|C| = |C'|$, and $C \prec C'$ if $C, C' \in \mathcal{F}$ and $|C| < |C'|$. Therefore, belonging to a feasible coalition is a primary criterion for all agents. The next criterion is the cardinality of the coalition (the larger the better).

We say that agent $i$ has a *profitable deviation* in $\pi$, if either $\pi(i) \notin \mathcal{F}$, or there exists a coalition $C \in \pi$ such that $C \cup \{i\} \in \mathcal{F}$ and $|C| \ge |\pi(i)|$. In the first case, agent $i$ can form the singleton coalition $\{i\}$, which is feasible because it is spanned by a trivial star and thus it is preferred to $\pi(i)$. In the second case, agent $i$ is better off by joining $C$ as both $C \cup \{i\}$ and $\pi(i)$ belong to $\mathcal{F}$ and $|\pi(i)| < |C \cup \{i\}|$. More generally, a set of agents $S$ has a *joint profitable deviation* in $\pi$, if there exists a partition $\pi'$, obtained from $\pi$ by letting every agent $i \in S$ leave coalition $\pi(i)$ and join either another existing coalition in $\pi$ or a newly formed one, in such a way that $\pi(i) \prec \pi'(i)$ for each $i \in S$.

A partition $\pi$ is *Nash stable* (resp., *Strong Nash stable*) if no agent (resp., no set of agents) has a profitable deviation (resp., a joint profitable deviation) in $\pi$. Nash and Strong Nash stable partitions correspond to pure Nash equilibria (Nash 1950) and Strong Nash equilibria (Aumann 1959), respectively. Clearly, every Strong Nash stable partition is also Nash stable by definition; so, the set of Strong Nash stable partitions is a subset of the set of Nash stable ones. It is easy to see that, by definition, any Nash stable partition, and so any Strong Nash stable one, is feasible. In a *core stable* partition, there is no set of agents $C \subseteq V$ for which all its members are better off by forming coalition $C$. Clearly, Strong Nash stability implies core stability, so, the set of core stable partitions (simply called the *core*) is a subset of the set of Strong Nash stable ones. In general, the converse implication is not always true. Nevertheless, because every agent only cares about the size of its coalition whenever it is feasible, Strong Nash stability and core stability coincide in our game, as shown in the following.

**PROPOSITION 1.1.** *A partition is Strong Nash stable for game $(G, \mathcal{F})$ if and only if it is core stable for $(G, \mathcal{F})$.*

**PROOF.** As already said, a Strong Nash stable partition is also core stable by definition. Thus, we now prove that a core stable partition $\pi$ is also Strong Nash stable. Assume, by way of contradiction, that this is not the case. Then, there exists a set of agents $S$ possessing a joint profitable deviation in $\pi$ which gives life to a new partition $\pi'$. As $\pi$ is feasible and every agent improves after the deviation, we have $|\pi'(i)| > |\pi(i)|$ for each agent $i \in S$. Let $i^* \in S$ be a deviating agent belonging to the largest coalition in $\pi$. We have

$$ |\pi'(i^*)| > |\pi(i^*)| \ge |\pi(i)|, \quad \forall i \in S. \quad (1) $$
If $\pi'(i^*) \subseteq S$, then (1) implies that $\pi'(i^*)$ is a set of agents whose members are all better off after forming a new coalition and this contradicts the core stability of $\pi$. Thus, $i^*$ has to join a coalition $C \in \pi$. If $C \cap S = \emptyset$, that is, $C$ does not lose any agent, then we have that $|\pi'(i^*)| > |C| = |\pi(i)|$ for each $i \in \pi'(i^*) \setminus S$. Together with (1), this implies that $\pi'(i^*)$ is a set of agents whose members are all better off after forming a new coalition, thus contradicting the core stability of $\pi$. □

In light of Proposition 1.1, we shall use the word core instead of Strong Nash for the rest of this article.

A social function is a function, defined from $\Pi$ to $\mathbb{R}_{\ge 0}$, measuring the social value of a partition. A social optimum is a partition $\pi^* \in \Pi_F$ optimizing a given social function. We consider the following two social functions (some motivations are given below in Section 1.2):

* sociality, defined as $\text{soc}(\pi) = |\{i \in V : |\pi(i)| > 1\}|$, and

* fragmentation, defined as $\text{frag}(\pi) = |\pi|$.

Sociality needs to be maximized, while fragmentation needs to be minimized.

We evaluate the efficiency of stable partitions by means of the well established notions of price of anarchy (Koutsoupias and Papadimitriou 1999), price of stability (Anshelevich et al. 2004), and their strong versions (Andelman et al. 2009). The price of anarchy of game $(G, \mathcal{F})$ with respect to sociality is defined as $\text{PoA}_s(G, \mathcal{F}) = \frac{\text{soc}(\pi^*)}{\text{soc}(\pi)}$, where $\pi^*$ is a social optimum and $\pi$ is a Nash stable partition of minimum sociality. Conversely, the price of stability of game $(G, \mathcal{F})$ with respect to sociality is defined as $\text{PoS}_s(G, \mathcal{F}) = \frac{\text{soc}(\pi^*)}{\text{soc}(\pi)}$, where $\pi^*$ is a social optimum and $\pi$ is a Nash stable partition of maximum sociality. The price of anarchy of game $(G, \mathcal{F})$ with respect to fragmentation is defined as $\text{PoA}_f(G, \mathcal{F}) = \frac{\text{frag}(\pi)}{\text{frag}(\pi^*)}$, where $\pi^*$ is a social optimum and $\pi$ is a Nash stable partition of maximum fragmentation, while its price of stability is defined as $\text{PoS}_f(G, \mathcal{F}) = \frac{\text{frag}(\pi)}{\text{frag}(\pi^*)}$, where $\pi^*$ is a social optimum and $\pi$ is a Nash stable partition of minimum fragmentation. Observe that the social optimum appears at the numerator when considering sociality and at the denominator when focusing on fragmentation. This makes the PoA and the PoS vary in the interval $[1, \infty)$, with the interpretation that the closer to 1, the better. By substituting the notion of Nash stable partition with that of core stable one, we obtain the definitions of the strong price of anarchy (SPoA) and the strong price of stability (SPoS). Observe that, for a given game $(G, \mathcal{F})$ and for each $\phi \in \{s, f\}$, we have

$$ \text{PoS}_{\phi}(G, \mathcal{F}) \le \text{SPoS}_{\phi}(G, \mathcal{F}) \le \text{SPoA}_{\phi}(G, \mathcal{F}) \le \text{PoA}_{\phi}(G, \mathcal{F}). \quad (2) $$

We are interested in bounding these four metrics as a function of the number of agents $n$ in the game. In particular, for each $n \ge 2$ and $\phi \in \{s, f\}$,

$$ \text{PoA}_{\phi}(n) = \sup_{(G, \mathcal{F}) : |V(G)| = n} \text{PoA}_{\phi}(G, \mathcal{F}). $$

The quantities $\text{PoS}_{\phi}(n)$, $\text{SPoS}_{\phi}(n)$ and $\text{SPoA}_{\phi}(n)$ are defined accordingly. By relation (2), for each $n \ge 2$ and $\phi \in \{s, f\}$, we clearly get

$$ \text{PoS}_{\phi}(n) \le \text{SPoS}_{\phi}(n) \le \text{SPoA}_{\phi}(n) \le \text{PoA}_{\phi}(n). $$

## 1.2 Some Motivations

In this subsection, we discuss justifications and motivations behind our modelling hypotheses. To this aim, we put forward some real-life examples fitting within our hedonic game model which, besides of providing practical motivations for this work, will also give us the chance of discussing some of our modelling choices and possible extensions.
First of all, we would like to start by providing a theoretical justification to our feasibility assumption. Towards this end, we observe that requiring subgraphs spanned by a star can be interpreted as restricting the model of Igarashi and Elkind (2016) to communication patterns of small length. In comparison, unbounded multi-hop communication may be costlier, slower, and prone to errors or misunderstandings. Therefore, distant communication should be avoided.

For real-life examples fitting within our model, one may consider the following scenarios.

**Unions.** Assume that $V(G)$ models a set of workers of a given company, the edge set $E(G)$ the ideological acquaintance, and that the power of a union is measured by its size. Thus, workers want to join the largest unions. However, a union can survive only if it has a leader who is ideologically close to its partners. For this model, it makes sense considering the fragmentation social function that aims at minimizing the number of unions as, the larger the number of unions, the less is their negotiating power. Moreover, a large number of unions also poses a problem of mediation and coordination among their potentially conflictual interests and requests.

**Group Buying.** Assume that $V(G)$ models a set of buyers, all interested in purchasing from a same shop/site, and $E(G)$ models their knowledge/trust relationships. Buyers enjoy flowing into large buying groups, as the larger the group, the better the purchasing conditions they can fetch (for instance, they can share the shipping costs). However, negotiation with the seller is carried out by one group member only, who then gets also in charge of redistributing what is bought to the others. Thus, this agent needs to be trusted by everybody. If one considers the case in which each order has a fixed shipping cost which is shared (according to any rule) by the group members, then fragmentation times the per-order shipping cost becomes equal to the total shipping cost suffered by all agents.

**Sport Tournaments.** Assume that $V(G)$ models a set of teams and there is an edge between two teams if they are close enough to meet and practice a given sport (e.g. football). The participants gather into groups in such a way that a central member can host all teams of its group and organize a tournament. Teams will prefer larger tournaments to small ones in order to maximize the number of opponents against which they can play a match. Sociality, here, aims at involving as many teams as possible into the organization of local tournaments<fnref n="1" />.

**Public Infrastructures.** The previous example, although reasonable, may leave itself open to the following criticism: with respect to sociality, arranging *n* teams into *c* tournaments of roughly *n*/*c* teams each is a social optimum for any *c* ∈ {1, ..., *n*/2}. However, solutions with smaller values of *c* appear to be preferable. The following scenario deals with this issue, by considering situations in which it is of fundamental importance for an agent to be part of some coalition, no matter how big this is.

There are *n* villages, each interested in building a hospital. For each *i* ∈ {1, ..., *n*}, village *i* would like to have a hospital with $b_i$ beds. Building a hospital with *b* beds requires a budget $B(b) = \alpha + \beta(b)$, where *α* models an aggregation of fixed costs, which are independent of the dimensions of the hospital and $\beta(\cdot)$ models an aggregation of per-bed costs. Assume that no village can afford the construction of a hospital with its own budget, but, as soon as two (or more) villages cooperate to share the fixed costs, while keeping the overall number of beds equal to the sum of the beds required by each member, the construction costs become affordable (this is equivalent to say that each village *i* has a budget of at least $\alpha/2 + \beta(b_i)$, but smaller than $\alpha + \beta(b_i)$). The pairwise distances among villages define an undirected graph, in which there is an edge between two villages *i* and *j* if and only if the distance between them is such that, if a hospital is built in village *i*'s territory, then it can also serve village *j* (and vice-versa). Thus, in order for a coalition of villages to jointly build a hospital which can serve all of them, it must be the case that their induced subgraph admits a spanning star. Each village strictly prefers having a access to a hospital over not benefiting from this service; subordinately, among all possible situations in which a village has access to a hospital, it wants to minimize the budget spent in the construction. As the larger

<footnote n="1">¹This is the same as minimizing the number of teams excluded from any tournament, but this is a less preferable function, as it may lead to pathological cases in which the social optimum has value zero.</footnote>
the coalition, the smaller the fraction of fixed costs ascribed to each member, each village wants to be part of the largest possible coalition. In such a setting, the social function sociality, counting the number of villages having a serving hospital, best captures the interests of the community. This example can be recast, *mutatis mutandis*, to other types of public infrastructures such as schools, landfills, etcetera.

The majority of the literature in Algorithmic Game Theory measures the efficiency of stable solutions through social functions defined on some aggregation of the agents' utilities: the utilitarian social welfare looks at the set of agents as a monolithic entity, by summing up the agents' utilities; the egalitarian social welfare cares of the most penalized agent by considering the minimum agent utility (or the maximum agent cost, depending on the context); the Nash social welfare produces an interesting interpolation on the previous two extremes, by considering, instead, the product of the agents' utilities. In this work, however, we investigate a general game model in which agents have an ordinal preference relation among partitions, rather than a cardinal utility function. For such a reason, we depart from the classical approach and propose the new social welfare functions of fragmentation and sociality, which only depend on structural properties of a partition, such as the number of coalitions (fragmentation) or the number of agents not being in a singleton coalition (sociality). Clearly, it is possible to simulate the ordinal preference relation considered in this work by means of a cardinal utility function and, indeed, there are infinitely many ways to achieve this task, each then suffering from a certain margin of discretion. In fact, our model does not specify by how much the utility of an agent increases when she makes a profitable move from a feasible coalition with $t$ members to a feasible coalition with $t+1$ ones. For instance, we can define the utility for an agent when being in a feasible coalition of cardinality $t$ to be equal to $u(t) := z + t - 1$, where $z$ is the utility for being in a singleton coalition. This yields $u(t+1) - u(t) = 1$ for each value of $t$ (the increase is independent of $t$). Another approach may be that of setting $u(t) := z + \sum_{i=1}^{t-1} \frac{1}{i}$. This yields $u(t+1) - u(t) = 1/t$ for each value of $t$ (the increase is decreasing in $t$). Thus, although all possible approaches end up defining games that are all isomorphic to the one we analyse here, the prices of anarchy and stability of stable outcomes may tremendously differ depending on the choice of the particular cardinal utility function. Moreover, we would like to stress that, in all those situations in which agents experience an extremely high improvement when moving from a singleton coalition to a coalition of cardinality two, and then have only a tiny preference in favour of larger coalitions as the cardinality increases (as, for instance, in the hospitals example), we can define $u(t) := t - 1 + \epsilon(t - 2)$, where $\epsilon$ is such that $\epsilon n \in o(1)$. Under this definition, sociality becomes equivalent, up to a negligible amount, to the utilitarian social welfare.

In our model, there must be at least one agent who can be the center of a spanning star. However, we do not designate a center in each feasible coalition, as we assume that being a center has no positive or negative impact on the agent's preferences. One can argue that a person would be happier to be the leader of a trade union of $t$ persons, rather than being a member of a union of $t+1$ persons; similarly, a village may prefer hosting a hospital, rather than being served by a slightly bigger hospital located in another village. However, it should be worth observing that being the center of a coalition not always brings benefits to the agent. Indeed, it may be the case that leading a group of people only comes with duties and responsibilities, without any sort of compensation, or it may be the case that the infrastructure to be hosted in a village is highly unwanted, such as in the case of a landfill. Given the generality of our model, we do not delve deeper into this question and leave further investigations to possible future works focusing on more specific games with context dependent agents' preferences.

## 1.3 Contribution

We focus on the complexity and efficiency of both Nash stable and core stable partitions. As to complexity results, we provide two constructive evidences showing existence of core stable partitions, and so also of Nash stable ones. In particular, in Theorem 2.1, we show that any sequence of joint profitable deviations converges to a core
<table><caption>Table 1. Bounds on the efficiency of both Nash stable and core stable partitions with respect to social functions sociality and fragmentation for games induced by general graphs. All bounds implicitly assume $n \ge 4$ as, for $n \in \{2, 3\}$, we show that $\text{PoA}(n) = 1$ under both social functions.</caption><thead><tr><th>Measure</th><th>Sociality</th><th>Fragmentation</th></tr></thead><tbody><tr><td>PoA(n)</td><td>n/3</td><td>n-2/2</td></tr><tr><td>SPoA(n)</td><td>(n/(1+√n-1), n/(1+√n-1))</td><td>(n/2)/(2, n/4 + 11/20)</td></tr><tr><td>SPoS(n)</td><td>(n/(2+√n-2), n/(1+√n-1))</td><td>(n/2)/(2, n/4 + 11/20)</td></tr><tr><td>PoS(n)</td><td>(n/(2√n-1), n/(1+√n-1))</td><td>(n/2)/(2, n/4 + 11/20)</td></tr></tbody></table>

stable partition, while Theorem 2.2 characterizes the core as the set of all possible outputs of a polynomial time greedy algorithm. These two facts complement each other, as the first does not need strong coordination among the agents, but provides no guarantees of fast convergence, whereas the second, while requiring centralized coordination (dictated by the greedy choices of the proposed algorithm), guarantees efficient computation. We then provide bounds on the PoA, PoS, SPoA and SPoS under social functions sociality and fragmentation. In particular, we consider games induced by general (unrestricted) graphs and games induced by claw-free graphs<fnref n="2" /> because the presence of a claw will be proved to be a source of inefficiency. These results are either tight or asymptotically tight and are summarized in Tables 1 and 2. More precisely, with the only exception of the PoS for general games under the sociality social function which is tight up to a multiplicative factor of 2, all non-exact bounds are indeed tight up to a small additive term which vanishes as $n$ goes to infinity. We stress that the result for the PoS under the fragmentation social function in games induced by claw-free graphs is obtained by leveraging the convergence result given in Theorem 2.1. This provides another evidence of the usefulness of Theorem 2.1, even in presence of the stronger existential result presented in Theorem 2.2.

Finally, we also address the problem of computing outcomes with prescribed welfare guarantees. In particular, we consider the computation of social optima and extreme (i.e., either best or worst) Nash stable partitions under both social functions. We design a polynomial time algorithm to compute a social optimum for sociality and prove that all other problems are NP-hard, except for that of computing a worst Nash stable partition under fragmentation whose complexity remains open.

## 1.4 Significance of the Results

From our findings, it turns out that the presence of claws in the social graph defining the game is a provable source of inefficiency that has to be taken into account, for instance, whenever mechanisms for coping with selfish behavior can be designed and applied.

Another interesting consequence is the following. Consider the third application of the model illustrated in Subsection 1.2, that is, that of sport tournaments. Recall that, in this case, there is an edge between two teams if they are close enough to meet. We can think that closeness may be determined on the basis of the Euclidean distance between the headquarters of the two teams (this is a good approximation when one considers air travel), and that all teams agree on the same definition of closeness. Let us say, for the ease of exposition, that two teams are close if their distance is within $\theta$ kilometres. This can also be restated by saying that each team does not want to undergo a trip whose length exceeds a certain threshold $\theta$. Thus, the presence of a claw in the graph means that there is a team $t_0$ which is close to three other teams $t_1, t_2$ and $t_3$, but no two of them are close to each other.

<footnote n="2">²A graph is claw-free if it does not contain an induced $K_{1,3}$, i.e., the complete bipartite graph with 1 and 3 vertices on the respective sides.</footnote>
<table><caption>Table 2. Bounds on the efficiency of both Nash stable and core stable partitions with respect to social functions sociality and fragmentation for games induced by claw-free graphs. All bounds implicitly assume $n \ge 4$ as, for $n \in \{2, 3\}$, we show that $\text{PoA}(n) = 1$ under both social functions. The lower bound for the SPoS of the social function sociality when $n$ is odd holds for $n \ge 9$, otherwise, a lower bound of $\frac{2n}{n+3}$ holds. The lower bound for the fragmentation social function holds for $n \ge 12$, otherwise, the trivial lower bound of 1 holds.</caption><thead><tr><th>Measure</th><th>Sociality</th><th>Fragmentation</th></tr></thead><tbody><tr><td>PoA(n)</td><td>$\frac{2n}{n+2}$ if n is even<br>$\frac{2n}{n+1}$ if n is odd</td><td>$\left[2 - \frac{2}{\sqrt{n+4}}\right] - 1, 2$</td></tr><tr><td>SPoA(n)</td><td>$\frac{2n}{n+2}$ if n is even<br>$\frac{2n}{n+1}$ if n is odd</td><td>$\left[2 - \frac{2}{\sqrt{n+4}}\right] - 1, 2$</td></tr><tr><td>SPoS(n)</td><td>$\frac{2n}{n+2}$ if n is even<br>$\frac{2n}{n+1}$ if n is odd</td><td>$\left[2 - \frac{2}{\sqrt{n+4}}\right] - 1, 2$</td></tr><tr><td>PoS(n)</td><td>$\frac{2n}{n+2}$ if n is even<br>$\left[\frac{2n}{n+3}, \frac{2n}{n+1}\right]$ if n is odd</td><td>1</td></tr></tbody></table>

What is the maximum minimum distance between two teams in $\{t_1, t_2, t_3\}$? It is easy to see that this value is equal to $\sqrt{3}\theta$ and is attained when teams $t_1, t_2$ and $t_3$ are located along a circumference of radius $\theta$ centred at $t_0$, and the angle between any two of them is of 120 degrees. This tells us that, if teams are willing to accept trips at most $\sqrt{3}$ times longer than what they originally wanted, they are guaranteed to be engaged in a game whose price of anarchy drops from $\Theta(n)$ to at most 2. This is of tremendous importance if one thinks that, under these premises, our polynomial time algorithm can be used to compute an efficient partition that happens to be core stable under this extended notion of feasibility.

## 1.5 Related Work

The language for describing which coalitions are feasible, and how agents value them, is a critical feature in hedonic games. Like in (Brânzei and Larson 2009; Deng and Papadimitriou 1994), feasible coalitions and their values can be described with the help of a (directed) graph. Igarashi and Elkind (2016) and Peters (2016) have considered hedonic games defined over graphs: agents are the vertices and feasible coalitions satisfy a given graph property. Regarding the worth of a coalition, a simple and compact representation is given by *additively separable functions* (Banerjee et al. 2001): each agent $i$ assigns a value $v_{ij}$ to agent $j$ and agent $i$'s worth for a coalition $C$ is $\sum_{j \in C} v_{ij}$. See, for example, (Olsen et al. 2012) for a simple hedonic game where $v_{ij} \in \{0, 1\}$.

Regarding existing games defined over graphs, Panagopoulou and Spirakis (2008) and Escoffier et al. (2012) studied a game where the vertices of a graph have to select a color (each color corresponds to a coalition), and a vertex's payoff is the number of agents with the same color, provided that it constitutes an independent set. A similar model has been introduced and studied by Apt et al. (2017). Igarashi, Peters, et al. (2017) studied the group activity selection problem defined over a social graph. Here, agents are partitioned into groups and each group is assigned to an activity, with the constraint that each group needs to induce a connected subgraph. Brânzei and Larson (2011) considered social distance games, where the utility of an agent for being in a coalition is given
by the closeness to the other members of the coalition. In many works including the famous stable marriage problem, the coalitions form a matching of a graph (see, for example, (Hoefer et al. 2018)).

For bounds on the price of anarchy and the price of stability in some classes of hedonic games, many works exist and we refer the interested reader to (Balliu, Flammini, Melideo, et al. 2017; Bilò, Fanelli, et al. 2018, 2019; Feldman et al. 2015; Monaco et al. 2019, 2018). The computation of socially optimal partitions in hedonic games, according to different social functions, has been treated in (Balliu, Flammini, and Olivetti 2017; Brânzei and Larson 2009; Charikar et al. 2005; Demaine et al. 2005; Flammini et al. 2018). Finally, we refer the reader to (Aziz, Brandt, et al. 2011; Ballester 2004; Olsen 2009; Peters and Elkind 2015) for an extensive treatment of the computational complexity of both decision and search problems related to stable partitions in hedonic games.

## 2 On Core Stable Partitions

Given a partition $\pi$, a strong Nash dynamics of length $\ell$ starting from $\pi$ is a sequence of partitions $\langle \pi = \pi_0, \pi_1, \dots, \pi_\ell \rangle$ such that, for each $j \ge 1$, $\pi_j$ is obtained as a result of a joint profitable deviation of some set of agents in $\pi_{j-1}$.

A game has the lexicographical improvement property (LIP) (Harks et al. 2013), if every joint profitable deviation strictly increases the lexicographical order of a certain function defined on $\Pi$. In the next theorem, we show that, for any graph $G$, game $(G, \mathcal{F})$ has the LIP property.

**THEOREM 2.1.** Any game $(G, \mathcal{F})$ has the LIP.

**PROOF.** Given a partition $\pi$ and an agent $i \in [n]$, define the value of agent $i$ in $\pi$ as $w_i(\pi) := |\pi(i)|$ if $\pi(i) \in \mathcal{F}$ and $w_i(\pi) := 0$ otherwise. Let $L(\pi)$ be the $n$-dimensional vector consisting of the values $w_i(\pi)$ for each $i \in V$, sorted in non-increasing order and denote by $L_j(\pi)$ its $j$-th element. Now consider a set $S$ of agents having a joint profitable deviation in $\pi$ and let $\pi'$ be the partition obtained after the joint deviation. Let $i^* \in S$ be an agent of maximum value $w_i(\pi)$ among those belonging to $S$. Moreover, let $j^* \in [n]$ be the index of the first element of $L(\pi)$ which is equal to $w_{i^*}(\pi)$. Observe that, as $i^*$ strictly prefers $\pi'(i^*)$ to $\pi(i^*)$, it must be that either $\pi(i^*) \notin \mathcal{F}$ and $\pi'(i^*) \in \mathcal{F}$ or $\pi(i^*)$ and $\pi'(i^*)$ both belong to $\mathcal{F}$ and $|\pi'(i^*)| > |\pi(i^*)|$. Thus, in both cases, we have $w_{i^*}(\pi') > w_{i^*}(\pi)$.

We now prove that $L(\pi')$ is lexicographically larger than $L(\pi)$, which implies the claim. Let $\pi_{BIG} \subseteq \pi$ be the set of feasible coalitions in $\pi$ with cardinality larger than $|\pi(i^*)|$ if $\pi(i^*)$ is feasible, otherwise, if $\pi(i^*)$ is not feasible, let $\pi_{BIG} \subseteq \pi$ simply be the set of feasible coalitions in $\pi$. First note that no coalition $C \in \pi_{BIG}$ loses an agent by the definition of $i^*$. So, for each $j \in [j^* - 1]$, we have $L_j(\pi') \ge L_j(\pi)$. If $i^*$ (feasibly) joins a coalition in $\pi_{BIG}$, then we get that there exists $j \in [j^* - 1]$ such that $L_j(\pi') > L_j(\pi)$ and we are done. Otherwise, it follows that, in $\pi'$, at least $j^*$ agents have value larger than $w_{i^*}(\pi)$: the $j^* - 1$ agents in $\pi_{BIG}$ and agent $i^*$. Thus, $L_{j^*}(\pi') > L_{j^*}(\pi)$ and we are done. $\square$

Theorem 2.1 implies that a core stable partition (and thus a Nash stable partition) always exists as the length of every strong Nash dynamics is finite.

We additionally prove that, if centralized coordination is allowed, a core stable partition can be computed in polynomial time. This is done by proving that the core is completely characterized by the set of all possible outputs of Algorithm 1.

In Algorithm 1, we use standard notations of graph theory, namely $d_G(i)$ is the degree of $i$ in graph $G$, $G[X]$ is the subgraph induced by the set of vertices $X$, and the closed neighborhood $N_G[i]$ of vertex $i$ in graph $G$ contains $i$ and the vertices adjacent to $i$.

**THEOREM 2.2.** A partition is core stable if and only if it is the output of Algorithm 1 (according to some given tie breaking rule).
<caption>**Algorithm 1 Greedy Core**</caption>

**Input:** Game $(G, \mathcal{F})$ where $G = (V, E)$ is a graph.
**Output:** A core stable partition $\pi$.
1: **while** $V \neq \emptyset$ **do**
2: &nbsp;&nbsp;&nbsp;&nbsp;take $i \in V$ maximizing the degree $d_G(i)$
3: &nbsp;&nbsp;&nbsp;&nbsp;$$\pi(i) \leftarrow N_G[i] * N_G[i]$$ is the closed neighbourhood of $i^*$
4: &nbsp;&nbsp;&nbsp;&nbsp;$$G \leftarrow G[V \setminus N_G[i]]$$
5: **end while**
6: **return** $\pi$

**PROOF.** It is clear that the algorithm outputs a feasible partition $\pi$. First, we show that $\pi$ is core stable. Assume, by way of contradiction, that $\pi$ is not core stable. Thus, there exists a joint profitable deviation in $\pi$ for a set of agents $S$, with $|S| \ge 1$, generating partition $\pi'$. Let $i^*$ be an agent in $S$ such that $\pi(i^*)$ is the first coalition containing agents in $S$ created by the algorithm. As $i^*$ improves and $\pi$ is feasible, $|\pi'(i^*)| > |\pi(i^*)|$. If $i^*$ joins a coalition $C$ created by the algorithm before $\pi(i^*)$, then, by the definition of $i^*$, $C$ does not lose any agent, which implies that $C \subset \pi'(i^*)$. Thus, at the step in which $C$ was created by the algorithm, $\pi'(i^*)$ was a possible alternative choice, but the algorithm chose $C$: a contradiction to the greedy choice. Hence, $i^*$ joins a coalition $C$ which either is created by the algorithm after $\pi(i^*)$, or it is a new coalition created by the joint deviation. In both cases, $\pi'(i^*)$ can only contain vertices belonging to coalitions created by the algorithm at the step in which $\pi(i^*)$ was created or after. This implies that, at the step in which $\pi(i^*)$ was created by the algorithm, $\pi'(i^*)$ was a possible alternative choice, but the algorithm chose $\pi(i^*)$: a contradiction to the greedy choice.

Now, we show that any core stable partition $\pi$ can be the output of Algorithm 1. List the coalitions in $\pi$ by non-increasing cardinality and define a tie breaking rule $R$ that:

* assigns priorities to the coalitions in $\pi$ so as to respect the given ordering, and

* gives higher priority to a coalition in $\pi$ with respect to any coalition not in $\pi$.

Run the algorithm according to rule $R$ to obtain a partition $\pi'$. Assume, by way of contradiction, that $\pi \neq \pi'$. List the coalitions in $\pi'$ by non-increasing cardinality, breaking ties according to $R$. Let $j$ be the first index at which the two sequences become different and denote as $C$ and $C'$ the $j$-th coalition in the ordering defined on $\pi$ and $\pi'$, respectively. As, up to index $j-1$ partitions $\pi$ and $\pi'$ are identical, the set of agents belonging to the $j$-th coalition onwards in both partitions coincide. Thus, by the definition of $R$ and the greedy choice, it must be $|C'| > |C|$, which implies that all vertices in $C'$, which can only belong to coalitions of size at most $|C|$, can perform a joint profitable deviation in $\pi$. This contradicts the assumption that $\pi$ is a core stable partition. $\square$

## 3 Efficiency of Core/Nash Stable Partitions

In this section, we focus on the efficiency of Nash and core stable partitions with respect to both social functions sociality and fragmentation. Before characterizing the price of anarchy, we prove some preliminary lemmas.

**LEMMA 3.1.** If $G$ admits a spanning star, then any Nash stable partition for game $(G, \mathcal{F})$ is formed by a unique coalition $V(G)$.

**PROOF.** Let $c$ be the center of the spanning star of $G$, and assume, by way of contradiction, that there exists a Nash stable partition $\pi$ such that $\pi(c) \neq V$. Thus, as every Nash stable partition is feasible, there exists an agent $i$ such that $\pi(i) \neq \pi(c)$ and $i$ is the centre of a star spanning $G[\pi(i)]$. As $c$ is adjacent to every other vertex in $V$, we have that $\{c, i\} \in E(G)$. This implies that $c$ can feasibly deviate to $\pi(i)$ and $i$ can feasibly deviate to $\pi(c)$. As one of these deviations is a profitable one, we get a contradiction to the assumption that $\pi$ is a Nash stable partition. $\square$
<figure><img src="image_4.png" /><figcaption>Fig. 1. A graph yielding a game with worst-case price of anarchy.</figcaption></figure>

**LEMMA 3.2.** Let $(G, \mathcal{F})$ be a game with $n \ge 3$ agents and let $\pi$ be a Nash stable partition for $(G, \mathcal{F})$. Then, $\pi$ either contains 2 coalitions of size at least 2, or contains a coalition of size at least 3.

**PROOF.** Fix a Nash stable partition $\pi$ for a game $(G, \mathcal{F})$ with $n \ge 3$ agents. As $G$ contains at least one edge, $\pi$ must contain at least one coalition of cardinality at least two. Assume, by way of contradiction, that $\pi$ contains exactly one coalition $C$ of cardinality two. As $G$ is connected and $n \ge 3$, there exists a vertex $i \notin C$ which is adjacent to one of the two vertices in $C$. As, by our assumption on $\pi$, $i$ belongs to a singleton coalition in $\pi$, $i$ has a profitable deviation by joining $C$. This contradicts the fact that $\pi$ is Nash stable. $\square$

We are now ready to characterize the price of anarchy. As it is equal to 1 for any game with at most three agents ($G$ being connected, it admits a spanning star which is the unique Nash stable partition by Lemma 3.1), in the remaining of the section we shall focus on the case in which $n \ge 4$.

**THEOREM 3.3.** For any $n \ge 4$, $\text{PoA}_s(n) = n/3$ and $\text{PoA}_f(n) = (n-2)/2$.

**PROOF.** For any $n \ge 4$, fix a game $(G, \mathcal{F})$ with $n$ agents and let $\pi$ be a Nash stable partition for $(G, \mathcal{F})$. By Lemma 3.2, $\text{soc}(\pi) \ge 3$. As the sociality of any partition is upper bounded by $n$, we obtain an upper bound of $n/3$ on the price of anarchy. By Lemma 3.1, if the fragmentation of the social optimum is 1, then the price of anarchy is 1, hence assume that the optimal fragmentation is at least 2. By Lemma 3.2, $\text{frag}(\pi) \le n-2$ which yields the desired upper bound on the price of anarchy.

A matching lower bound for both social functions can be obtained by considering the game induced by the graph $G$ depicted in Figure 1. The partition $\pi$ such that $\pi(v_1) = \{v_1, v_2, v_3\}$ and $\pi(v_i) = \{v_i\}$ for $i > 3$ is Nash stable and has $\text{soc}(\pi) = 3$ and $\text{frag}(\pi) = n-2$. On the other hand, the partition $\pi^*$ such that $\pi^*(v_1) = \{v_1, v_2\}$ and $\pi^*(v_3) = \{v_3, \dots, v_n\}$ has a sociality of $n$ and a fragmentation of 2. Comparing the two partitions yields the desired lower bounds. $\square$

It is also possible to give an upper bound on the price of anarchy with respect to both social functions which depends on the stability number $\alpha(G)$ of graph $G$, where $\alpha(G)$ is the largest size of an independent set.

**THEOREM 3.4.** For any $n \ge 4$, $\text{PoA}_s(G, \mathcal{F}) \le \frac{n}{n-\alpha(G)+1}$ and $\text{PoA}_f(G, \mathcal{F}) \le \frac{\alpha(G)}{2}$.

**PROOF.** For a fixed game $(G, \mathcal{F})$, let $\pi$ be a Nash stable partition for $(G, \mathcal{F})$. As the set of centres of the stars spanning the subgraph induced by each coalition in $\pi$ forms an independent set in $G$, it follows that $\text{frag}(\pi) \le \alpha(G)$. As discussed in the previous theorem, if the optimal fragmentation is 1, then Lemma 3.1 implies a price of anarchy of 1. Thus, it follows that the price of anarchy with respect to fragmentation is at most $\frac{\alpha(G)}{2}$. With respect to sociality, as $G$ has at least one edge, the number of singleton coalitions in $\pi$ can be at most $\text{frag}(\pi) - 1 \le \alpha(G) - 1$. So, $\text{soc}(\pi) \ge n - \alpha(G) + 1$ and the result follows as the optimal sociality is at most $n$. $\square$

For the efficiency of core stable outcomes under the sociality social function, we have the following asymptotically tight results.
**THEOREM 3.5.** For any $n \ge 4$,

$$ \mathrm{SPoS}_s(n) \in \left[ \frac{n}{2 + \lceil \sqrt{n-2} \rceil}, \frac{n}{1 + \sqrt{n-1}} \right] \quad \text{and} \quad \mathrm{SPoA}_s(n) \in \left[ \frac{n}{1 + \lceil \sqrt{n-1} \rceil}, \frac{n}{1 + \sqrt{n-1}} \right]. $$

**PROOF.** For any $n \ge 4$, fix a game $(G, \mathcal{F})$ with $n$ agents and let $\pi$ be a core stable partition for $(G, \mathcal{F})$. Consider a coalition $C$ in $\pi$ with $|C| = k > 2$ and let $c$ be the center of the spanning star of $G[C]$. No vertex $i$ belonging to a singleton coalition can be adjacent to $c$, otherwise $i$ would have a profitable deviation in $\pi$. Any vertex $i \in C$, with $i \ne c$ can be adjacent to at most $k-2$ vertices belonging to singleton coalitions, otherwise these vertices, together with $i$ and $c$ would have a joint profitable deviation in $\pi$. It follows that for any coalition in $\pi$ with $k > 2$ vertices, there can be at most $(k-1)(k-2)$ singleton coalitions in $\pi$. Let $s_k$ be the number of coalitions in $\pi$ with $k$ vertices for $k \ge 1$. We deduce $\sum_{k=3}^n (s_k(k^2 - 3k + 2)) \ge s_1$ which gives $\sum_{k=2}^n (s_k(k^2 - 2k + 2)) \ge n$ by adding $\sum_{k=2}^n ks_k$ on both sides.

As the sociality in a social optimum is upper bounded by $n$ and $\mathrm{soc}(\pi) = \sum_{k=2}^n (s_k k)$, we obtain that the strong price of anarchy of $(G, \mathcal{F})$ is at most

$$ \frac{n}{\sum_{k=2}^{n} (s_k k)} \le \frac{\sum_{k=2}^{n} (s_k(k^2 - 2k + 2))}{\sum_{k=2}^{n} (s_k k)} \le \frac{\bar{k}^2 - 2\bar{k} + 2}{\bar{k}}, $$

where $\bar{k} = \max\{k : s_k > 0\}$. Moreover, as $\bar{k} \ge 2$ by Lemma 3.2, we have $\mathrm{soc}(\pi) \ge \bar{k}$, so that the strong price of anarchy is trivially upper bounded by $n/\bar{k}$. It follows that the minimum of the two derived bounds is maximized for $\bar{k}^2 - 2\bar{k} + 2 = n \Leftrightarrow \bar{k} = 1 + \sqrt{n-1}$, which yields the desired upper bound on both $\mathrm{SPoA}_s(n)$ and $\mathrm{SPoS}_s(n)$.

For the lower bound on the strong price of anarchy, assume without loss of generality that $1+(\ell-1)^2 < n \le \ell^2+1$ for some integer $\ell \ge 2$ and consider the game induced by a tree $G$ rooted at vertex $x_0$ which has $\ell$ children denoted as $x_1, \dots, x_\ell$. For each $i \in [\ell-1]$, $x_i$ has $z_i$ children with $0 \le z_i \le \ell-1$ and $\sum_{i \in [\ell]} z_i = n - \ell - 1$. Observe that one such $G$ always exists as $1 + (\ell-1)^2 < n$ implies that $n \ge 1+\ell$ and $n \le \ell^2+1$ implies that $\sum_{i \in [\ell]} z_i \le \ell(\ell-1)$. As every vertex $x_i$ has degree at most $\ell$, the partition $\pi$ whose unique non-singleton coalition is $\{x_0, x_1, \dots, x_\ell\}$ is a possible outcome of Algorithm 1, thus, by Theorem 2.2, it follows that $\pi$ is a core stable partition for game $(G, \mathcal{F})$. As $\mathrm{soc}(\pi) = \ell+1$ and there is a partition with sociality $n$ (the one in which there are $\ell$ maximal coalitions centred at $x_i$, for each $i \in [\ell]$), we get that the strong price of anarchy is lower bounded by $\frac{n}{\ell+1}$. Since $\ell = \lceil \sqrt{n-1} \rceil$, the desired lower bound follows.

For the lower bound on the strong price of stability, add a vertex $y$ to the previous instance which is solely connected to $x_0$, so that now $n$ is such that $2 + (\ell-1)^2 < n \le 2+\ell^2$. In this case, the partition $\pi$ whose unique non-singleton coalition is $\{x_0, x_1, \dots, x_\ell, y\}$ is the unique possible outcome of Algorithm 1, no matter which tie breaking rule is applied. Thus, $\pi$ is the unique core stable partition for game $(G, \mathcal{F})$. As $\mathrm{soc}(\pi) = \ell+2$, we get that the strong price of stability is lower bounded by $\frac{n}{\ell+2}$. Since $\ell = \lceil \sqrt{n-2} \rceil$, the desired lower bound follows. $\square$

Under the fragmentation social function, we can prove asymptotically tight bounds which simultaneously apply to all the remaining efficiency metrics.

**THEOREM 3.6.** For any $n \ge 4$, $\lceil n/2 \rceil/2 \le \mathrm{PoS}_f(n) \le \mathrm{SPoA}_f(n) \le n/4 + 11/20$.

**PROOF.** For any $n \ge 4$, fix a game $(G, \mathcal{F})$ with $n$ agents and let $\pi$ be a core stable partition for $(G, \mathcal{F})$. Set $k = \Delta(G) + 1$, where $\Delta(G)$ is the maximum degree of $G$. It follows that the fragmentation of the social optimum is at least $\lceil n/k \rceil$. From Theorem 2.2 and the definition of Algorithm 1, we know that there is a coalition of size $k$ in $\pi$. Thus $\mathrm{frag}(\pi) \le 1+n-k$, and $\mathrm{SPoA}_f(G, \mathcal{F}) \le \frac{k(1+n-k)}{n}$. If $n$ is even then $\frac{k(1+n-k)}{n} \le \frac{n}{4} + \frac{1}{2}$, otherwise $\frac{k(1+n-k)}{n} \le \frac{(n+1)^2}{4n} = \frac{n}{4} + \frac{1}{2} + \frac{1}{4n} \le \frac{n}{4} + \frac{11}{20}$, where the last inequality is due to the hypothesis $n \ge 4$ (the smallest odd $n$ is 5).
<figure><img src="image_5.png" /><figcaption>Fig. 2. A graph yielding a game with worst-case price of stability with respect to fragmentation.</figcaption></figure>

To show the lower bound on the price of stability when $n$ is even, consider the game induced by the graph depicted in Figure 2. We have a social optimum $\pi^*$ such that $\pi^*(x_1) = \{x_1, \dots, x_{\lfloor n/2 \rfloor}\}$ and $\pi^*(y_1) = V \setminus \pi^*(x_1)$ and yielding $frag(\pi^*) = 2$. There are only two Nash stable partitions, namely $\pi_1$ and $\pi_2$, both having fragmentation equal to $\lfloor n/2 \rfloor$. In particular, $\pi_1$ is such that $\pi_1(x_1) = \{x_1, \dots, x_{\lfloor n/2 \rfloor}, y_1\}$ and $\pi_1(y_i) = \{y_i\}$ for $i > 1$, while $\pi_2$ flips the roles of $x$ and $y$. When $n$ is odd, take the same instance and add a new vertex $z$ solely connected to $x_1$ to keep getting the lower bound of $\lfloor n/2 \rfloor/2$. (We observe that, in this case, the best Nash stable partition $\pi$ has $\pi(x_1) = \{x_1, \dots, x_{\lfloor n/2 \rfloor}, z, y_1\}$.) $\square$

We conclude the section with a lower bound on the price of stability for the sociality social function showing that the quality of the best Nash stable partition cannot be better than twice that of the worst core stable one.

**THEOREM 3.7.** For any $n \ge 4$, $PoS_s(n) \ge \frac{n}{2[\sqrt{n}] - 1}$.

**PROOF.** Assume without loss of generality that $(\ell - 1)^2 < n \le \ell^2$ for some integer $\ell \ge 2$ and consider the game induced by the graph $G = (V, E)$ such that $V = X \cup Y_1 \cup \dots \cup Y_\ell$, with $X = \{x_1, \dots, x_\ell\}$ and, for each $i \in [\ell]$, $|Y_i| \le \ell - 1$. The set of edges $E$ is such that $G[X] = K_\ell$ (i.e., it is a complete graph on $\ell$ vertices) and, for each $i \in [\ell]$ each vertex in $Y_i$ is connected to $x_i$ only. Note that one such $G$ always exists as $n > (\ell - 1)^2$ implies that $n \ge \ell$, while $n \le \ell^2$ implies that $\sum_{i \in [\ell]} |Y_i| \le \ell(\ell - 1)$.

We shall prove that, in any Nash stable partition, the sociality is at most $2\ell - 1$. Fix a Nash stable partition $\pi$. We claim that $\pi$ contains a coalition $C$ containing $X$. This easily follows from the fact that $X$ defines a clique and that, by the topology of $G$, in any feasible coalition $C'$ containing a vertex $x \in X$, $C'$ induces a subgraph of $G$ admitting a spanning star centred at $x$. Moreover, as $\pi$ is feasible, $C$ cannot contain vertices belonging to two different sets $Y_i$ and $Y_j$. So, $|C| \le 2\ell - 1$. $\pi$ cannot contain other non-singleton coalitions, as the vertices in $V \setminus C$ yield an independent set of $G$. Hence, the sociality of $\pi$ is $2\ell - 1$. Given that there exists a partition with sociality $n$ (the one in which each set $Y_i$ with $|Y_i| > 0$ forms a coalition with vertex $x_i$, while all $x_j$s such that $|Y_j| = 0$ are together in the same coalition, possibly together with an $x_i$ for which $|Y_i| > 0$) and $\ell = \lceil \sqrt{n} \rceil$, the claimed lower bound follows. $\square$

## 3.1 Claw-Free Graphs

In this subsection, we consider the case in which the graph $G$ is claw-free, i.e., it does not contain an induced $K_{1,3}$ (i.e., the complete bipartite graph with 1 and 3 vertices on the respective sides). It will turn out that the presence of claws in $G$ is a provable source of inefficiency, as the price of anarchy with respect to both social functions (and so also all the other metrics) for games played on claw-free graphs drops to a value that never exceeds 2. Claws (and, more generally, induced stars with a large number of leaves) are problematic for our social functions when the center $c$ of a claw belongs to a coalition $\pi(c)$ which does not admit a spanning star of center $c$. In this case, some leaves of the claw can be isolated: they cannot join $\pi(c)$ or group themselves because they are disconnected. See, for instance, the game depicted in Figure 1 and assume $n = 5$ and that, in a given partition $\pi$, we have $\pi(c) = \{v_1, v_2, v_3\}$. Vertices $v_4$ and $v_5$, belonging to claw $\{v_2, v_3, v_4, v_5\}$, are isolated in $\pi$ and have no profitable deviations to improve their utility.
For the social function sociality, the following two theorems provide a tight characterization of all four metrics, except for the price of stability of games with an odd number of agents, which equals $\frac{2n}{n+2}$ when $n$ is even and $\frac{2n}{n+1}$ when $n$ is odd. For the leftover case, the bound is almost tight, up to an additive factor vanishing as $n$ goes to infinity.

**THEOREM 3.8.** For any $n \ge 4$, $\text{PoA}_s(n) \le \frac{n}{n-\lfloor \frac{n-1}{2} \rfloor}$, that is, $\text{PoA}_s(n) \le \frac{2n}{n+2}$ if $n$ is even and $\text{PoA}_s(n) \le \frac{2n}{n+1}$ if $n$ is odd.

**PROOF.** For any $n \ge 4$, fix a game $(G, \mathcal{F})$ defined by a claw-free graph with $n$ vertices and let $\pi$ be a Nash stable partition for $(G, \mathcal{F})$. Let $i$ be a vertex belonging to a singleton coalition in $\pi$. Clearly, $i$ cannot be adjacent to a vertex being a center of a spanning star of any subgraph induced by a coalition in $\pi$. So, $i$ can only be adjacent to leaves of spanning stars of any subgraph induced by coalitions in $\pi$. Assume that there exists a vertex $j$ also belonging to a singleton coalition in $\pi$ and sharing a neighbour $k$ with $i$. Let $c$ be the center of a star spanning $G[\pi(k)]$. As $\{i, j, c\}$ is independent, we find that the set of vertices $\{i, j, k, c\}$ induces a claw in $G$: a contradiction. Thus, two vertices forming a singleton coalition cannot be adjacent to a same leaf of a star spanning a non-singleton coalition.

Denote by $A$ the set of vertices that are centres of a star spanning the subgraph induced by a non-singleton coalition in $\pi$ and by $S$ the set of vertices belonging to singleton coalitions in $\pi$. Since any vertex in $S$ can be univocally paired with a vertex in $V \setminus (A \cup B)$, we get that $|S|$, which is integral, is upper bounded by $\lfloor \frac{n-|A|}{2} \rfloor \le \lfloor \frac{n-1}{2} \rfloor$. This implies that $\text{soc}(\pi) \ge n - \lfloor \frac{n-1}{2} \rfloor$, which yields the desired upper bound because the optimal sociality is at most $n$. $\square$

**THEOREM 3.9.** For any $n \ge 4$, $\text{PoS}_s(n) \ge \frac{2n}{n+2}$ if $n$ is even and $\text{PoS}_s(n) \ge \frac{2n}{n+3}$ if $n$ is odd. Moreover, for any odd $n \ge 5$, $\text{SPoA}_s(n) \ge \frac{2n}{n+1}$ and, for any odd $n \ge 9$, $\text{SPoS}_s(n) \ge \frac{2n}{n+1}$.

**PROOF.** Let us start with the lower bound on the price of stability. Suppose that $n$ is even, that is, $n = 2p$ for some integer $p \ge 2$ and consider the graph $G_p = (V_p, E_p)$ such that $V_p = X_p \cup Y_p$, where $X_p = \{x_1, \dots, x_p\}$, $Y_p = \{y_1, \dots, y_p\}$, $X_p$ forms a clique, and each vertex $y_i$ is adjacent to vertex $x_i$ only. For instance, $G_4$ is depicted on Figure 3.

First of all, we show that $G_p$ is claw-free. Fix a set $Z$ of 4 vertices. If $|Z \cap Y_p| = 0$, $Z \subseteq X_p$ induces a clique, while, if $|Z \cap Y_p| \ge 3$, then $Z$ induces a disconnected subgraph. If $|Z \cap Y_p| = 2$, then either $Z$ induces a disconnected subgraph or $Z = \{y_i, y_j, x_i, x_j\}$ for some pair of distinct indices $i, j \in [p]$. So, $Z$ does not induce a claw. Finally, if $|Z \cap Y_p| = 1$, then either $Z$ induces a disconnected subgraph or $Z = \{y_i, x_i, x_j, x_k\}$ for some triple of distinct indices $i, j, k \in [p]$. So, $Z$ does not induce a claw.

We continue by proving that, in any Nash stable partition $\pi$, there exists a coalition $C$ containing $X_p$. Assume, by way of contradiction, that there exist two distinct vertices $x_i$ and $x_j$ such that $\pi(x_i) \ne \pi(x_j)$. To guarantee feasibility, both these coalitions can contain at most one vertex from $Y_p$. So, both $\pi(x_j) \cup \{x_i\}$ and $\pi(x_i) \cup \{x_j\}$ are feasible coalitions. As either $|\pi(x_j) \cup \{x_i\}| > |\pi(x_i)|$ or $|\pi(x_i) \cup \{x_j\}| > |\pi(x_j)|$, $\pi$ cannot be Nash stable: a contradiction.

Now, to have feasibility, coalition $C$ can contain at most one vertex from $Y_p$. It follows that the sociality of any Nash stable partition is at most $p+1$. As there exists a partition with sociality $n = 2p$ (the one in which there are the $p$ coalitions $\{x_i, y_i\}$ for each $i \in [p]$) and $p+1 = \frac{n+2}{2}$, the claimed lower bound of $\frac{2n}{n+2}$ when $n$ is even follows.

When $n$ is odd, that is $n = 2p+1$, consider the graph $G'_p$ which is equal to graph $G_p$ defined above, with an additional node $x_0$ which is adjacent to all nodes in $X_p$. By the same arguments used above, we get that $G'_p$ is claw-free and the price of stability of the induced game is $\frac{n}{p+2}$. Using $p+2 = \frac{n+3}{2}$, the claimed lower bound of $\frac{2n}{n+3}$ when $n$ is odd follows.
<figure><img src="image_6.png" /><figcaption>Fig. 3. Graph $G_4$.</figcaption></figure>

For the lower bounds on the strong price of anarchy and stability of games with an odd number of agents, let $n = 2p+1$ for some integer $p \ge 2$. Consider a graph $G_p = (V_p, E_p)$ such that $V_p = X_p \cup Y_p$, with $X_p = \{x_0, x_1, \dots, x_p\}$ and $Y_p = \{y_1, \dots, y_p\}$. The set of edges is such that, for each $i \in [p]$, $x_i$ is adjacent to $x_0$, $y_i$ and to all other vertices $x_j$ such that $j \mod 2 = i \mod 2$.

To show that $G_p$ is claw-free, fix a set $Z$ made of 4 vertices of $V_p$. Observe that, in order to have a claw, we need a vertex $z \in Z$ of degree at least 3 in $G[Z]$. Only vertices in $X_p$ can satisfy this property when $p \ge 3$. In particular, if $z = x_0$, then no vertex in $Y_p$ can belong to $Z$, so $Z$ has to contain two distinct nodes $x_i$ and $x_j$ in $X_p \setminus \{x_0\}$ such that $j \mod 2 = i \mod 2$. Thus $x_i$ and $x_j$ are adjacent and no claw is possible. If $z = x_i$ with $i \in [p]$, then, in order for $x_i$ to have degree 3 in $G_p[Z]$, $Z$ has to contain a vertex $x_j \neq x_i$ with $j \in [p]$ and $j \mod 2 = i \mod 2$. Now $\{x_i, x_j\} \subseteq Z$ implies that $x_0 \notin Z$, otherwise $G_p[Z]$ would contain a triangle. So, in order for $x_i$ to have degree 3 in $G_p[Z]$, $Z$ has to contain another vertex $x_k \notin \{x_i, x_j\}$ with $k \in [p]$ and $k \mod 2 = i \mod 2$. Also in this case, $G_p[Z]$ contains a triangle. Thus, we conclude that $G_p$ is claw-free.

By definition, $x_0$ is a node of maximum degree in $G_p$. In fact, for each $i \in [p]$, we have

$$d_{G_p}(x_0) = p \ge d_{G_p}(x_i) = \lfloor \frac{p}{2} \rfloor + 1.$$

Moreover, this inequality is strict if $p \ge 4$. Thus, the partition $\pi$ in which the unique non-singleton coalition is $X_p$ is a possible output of Algorithm 1 for each $p \ge 2$ and the unique output when $p \ge 4$. By Theorem 2.2 and the fact that there exists a partition with sociality $n$, it follows that $\text{SPoA}_s(G_p, \mathcal{F}) \ge \frac{n}{p+1} = \frac{n}{\frac{n-1}{2}+1} = \frac{2n}{n+1}$ for each $p \ge 2$ (thus, $n$ is odd and $n \ge 5$) and $\text{SPoS}_s(G_p, \mathcal{F}) \ge \frac{2n}{n+1}$ for each $p \ge 4$ (thus, $n$ is odd and $n \ge 9$). $\square$

For the fragmentation social function, a slightly different situation occurs.

**THEOREM 3.10.** For any $n \ge 4$, $\text{PoA}_f(n) \le 2$.

**PROOF.** For any $n \ge 4$, fix a game $(G, \mathcal{F})$ defined by a claw-free graph with $n$ vertices and let $\pi$ be a Nash stable partition for $(G, \mathcal{F})$. If $\text{frag}(\pi) \le 2$, we are done. So, assume $\text{frag}(\pi) \ge 3$ and fix a social optimum $\pi^*$. Now define the following mapping between $\pi$ and $\pi^*$: each $C \in \pi$ is mapped to the coalition of $\pi^*$ containing the centre of the spanning star of $G[C]$. Consider three distinct coalitions $C_1, C_2, C_3 \in \pi$ and let $c_1, c_2$ and $c_3$ be the centres of the spanning stars of $G[C_1], G[C_2]$ and $G[C_3]$, respectively. As $\pi$ is Nash stable, the set of vertices $U = \{c_1, c_2, c_3\}$ induces an independent set of $G$. We claim that these vertices cannot belong to a same cluster in $\pi^*$. Assume, by way of contradiction, that there exists a cluster $C^* \in \pi^*$ containing $U$. As $U$ induces an independent set of $G$ no vertex in $U$ can be the center of the star spanning $G[C^*]$. So, there exists $c^* \in C^*$ which is adjacent to all vertices in $U$. But $U \cup \{c^*\}$ induces a claw: a contradiction. Hence, no more than two coalitions in $\pi$ can be mapped to the same coalition in $\pi^*$, which yields the desired upper bound. $\square$

**THEOREM 3.11.** For any $n \ge 12$, $\text{SPoS}_f(n) \ge 2 - \frac{2}{[\sqrt{n+4}]-1}$.

**PROOF.** Assume without loss of generality that $k(k+4) \le n < (k+1)(k+5)$, with $k \ge 2$. Define the following graph $G_k = (V_k, E_k)$. The set of vertices is $V_k = X_1 \cup \dots \cup X_k \cup Y \cup Z$, with $Y = \{y_1, \dots, y_k\}$
and $Z = \{z_1^a, z_1^b, \dots, z_k^a, z_k^b\}$ so that $|Z| = 2k$. As to sets $X_i$, we have that $|X_i| = 2i$ for each $i \in [k-1]$ and $|X_k| = n - k^2 - 2k \ge 2k$, $G_k[X_i]$ induces a clique and $X_i$ contains two special vertices, namely $\bar{x}_i$ and $\underline{x}_i$, which are the only vertices adjacent to vertices in $V_k \setminus X_i$. In particular, $\bar{x}_i$ is adjacent to both $z_i^a$ and $z_i^b$, while $\underline{x}_i$ is adjacent to $y_i$ and, for $i < k$, to both $z_{i+1}^a$ and $z_{i+1}^b$. Finally, for each $i \in [k]$, $z_i^a$ and $z_i^b$ are adjacent and, for $i > 1$, they are both adjacent to $y_{i-1}$.

We start by showing the $G_k$ is claw-free. Assume, by way of contradiction, that there exists a set $U$ of 4 vertices such that $G_k[U]$ is a claw, that is, a star centred at some vertex $c \in U$. If $c = y_i$, for some $i \in [k]$, then, as the degree of $y_k$ is equal to 1 and that of $y_i$, with $i < k$, is equal to 3, we get $U = \{y_i, \underline{x}_i, z_{i+1}^a, z_{i+1}^b\}$ which does not induce a claw as $z_{i+1}^a$ and $z_{i+1}^b$ are adjacent. If $c = z_i^a$ for some $i \in [k]$, then, as the degree of $z_i^a$ is equal to 2 and that of $z_i^a$, with $i > 1$, is equal to 4, we have 4 different choices for $U$. In particular, $U \setminus \{z_i^a\}$ has to contain exactly 3 vertices in $\{z_i^b, \bar{x}_i, \underline{x}_{i-1}, y_{i-1}\}$ and they have to form an independent set. But there is no such a choice, as we have $\{z_i^b, \bar{x}_i\} \in E_k$ and $\{\underline{x}_{i-1}, y_{i-1}\} \in E_k$. Clearly, by symmetry, the same argument holds also if $c = z_i^b$. If $c = \bar{x}_i$, for some $i \in [k]$, then $U \setminus \{\bar{x}_i\}$ must contain either both $z_i^a$ and $z_i^b$ (which are adjacent) or at least two vertices belonging to $X_i \setminus \{\bar{x}_i\}$ (which are adjacent). In both cases, $U \setminus \{\bar{x}_i\}$ does not induce an independent set. If $c = \underline{x}_i$, for some $i \in [k]$, then $U \setminus \{\underline{x}_i\}$ must contain either at least two vertices belonging to $X_i \setminus \{\underline{x}_i\}$ (which are adjacent) or at least two vertices in $\{y_i, z_{i+1}^a, z_{i+1}^b\}$ which induces a clique. In both cases, $U \setminus \{\bar{x}_i\}$ does not induce an independent set. Finally, if $c \in X_i \setminus \{\bar{x}_i, \underline{x}_i\}$, then it must be $U \subseteq X_i$ and so $U$ cannot induce a claw as it induces a clique.

We continue by showing that the feasible partition $\pi$ such that

$$ \pi := (X_i \cup \{z_i^a, z_i^b\}, \{y_i\} : i \in [k]) $$

is the unique output of Algorithm 1. By Theorem 2.2, this implies that $\pi$ is the unique strong Nash stable partition for game $(G_k, \mathcal{F})$.

The first choice of the algorithm is the vertex with largest degree. This vertex is $\bar{x}_k$ which has degree equal to $|X_k| - 1 + 2 = |X_k| + 1 \ge 2k + 1$. In fact, any other vertex $\underline{x}_i$, for $i < k$, has degree $2i + 1 \le 2(k-1) + 1 = 2k - 1$; vertex $\underline{x}_k$ has degree equal to $|X_k|$ and any other vertex $\bar{x}_i$, for $i < k$, has degree $2i - 1 + 3 \le 2(k-1) + 2 = 2k$; every vertex in $X_i \setminus \{\bar{x}_i, \underline{x}_i\}$ has degree equal to $2i - 1 \le 2k - 1$ if $i < k$ and equal to $|X_k| - 1$ if $i = k$; vertex $y_k$ has degree equal to 1 and any other vertex $y_i$, for $i < k$, has degree equal to $3 < 2k + 1$; both vertices $z_{i+1}^a$ and $z_{i+1}^b$ have degree equal to $4 < 2k + 1$. Now, observe that, after the algorithm has created coalition $X_k \cup \{z_k^a, z_k^b\}$ and removed these vertices from $V$, vertex $y_k$ remains isolated. So, the connected component of $G_k$ surviving the removal is indeed an instance of $G_{k-1}$. Thus, we can apply induction and conclude that, at each step, the algorithm has a unique choice and finally outputs coalition $\pi$.

Consider the feasible partition $\pi^*$ containing the following coalitions: $X_k \cup \{y_k\}$, $X_i \cup \{y_i\} \cup \{z_{i+1}^a, z_{i+1}^b\}$ for each $i \in [k-1]$ and $\{z_1^a, z_1^b\}$. As $frag(\pi^*) = k + 1$, $frag(\pi) = 2k$ and $k = \lfloor \sqrt{n+4} \rfloor - 2$ the claimed lower bound follows. $\square$

**THEOREM 3.12.** For any $n \ge 4$, $PoS_f(n) = 1$.

**PROOF.** For any $n \ge 4$, fix a game $(G, \mathcal{F})$ defined by a claw-free graph with $n$ vertices. Our aim is to show that, given a partition $\pi$, it is possible to schedule profitable deviations so as to obtain a Nash dynamics starting from $\pi$ and ending up to a Nash stable partition $\pi_\ell$ such that $frag(\pi_\ell) \le frag(\pi)$. Choosing a social optimum as starting partition will yield the claim. Our scheduling algorithm is defined as follows: given a partition $\pi$, if more than one agent have a profitable deviation in $\pi$, break ties in favour of an agent who does not constitute a center for any spanning star of the subgraph induced by the coalition she belongs to. By the LIP property proved in Theorem 2.1, we are guaranteed that the Nash dynamics defined by this scheduling algorithm always ends to a Nash stable partition $\pi_\ell$ for any starting partition $\pi$.
Assume, by way of contradiction, that $frag(\pi_t) > frag(\pi)$. This implies that there are two partitions $\pi, \pi' \in \Pi$ and an agent $i$ such that $\pi'$ is obtained as a result of a profitable deviation of $i$ in $\pi$ and $frag(\pi) < frag(\pi')$. The latter condition can happen only if $G[\pi(i) \setminus \{i\}]$ does not admit a spanning star, which implies that $G[\pi(i)]$ admits only one spanning star centred at $i$. So, there are at least two distinct vertices $u$ and $v$ other than $i$ belonging to $\pi(i)$ and such that $\{u,v\} \notin E$. Let $C \in \pi$ be the coalition joined by $i$ and let $j \neq i$ be the center of a spanning star for $G[C \cup \{i\}]$. Clearly it must be $\{i, j\} \in E$. If $\{u, j\} \in E$, then $C \cup \{u\} \in \mathcal{F}$. But as $|\pi(u)| = |\pi(i)| < |\pi'(i)| = |C \cup \{i\}| = |C \cup \{u\}|$, it follows that $u$ has a profitable deviation in $\pi$ and, by the definition of the scheduling algorithm, $i$ should have not been chosen. The same argument holds for $v$. It follows that $\{u, j\} \notin E$ and $\{v, j\} \notin E$. Thus, we have detected a set of vertices $\{i, j, u, v\}$ inducing a claw in $G$: a contradiction. $\square$

# 4 Computing Partitions with Prescribed Properties

In this section, we address the complexity of computing partitions with some prescribed properties, such as, for example, being a social optimum or being a Nash stable partition either maximizing or minimizing a given social function.

## 4.1 Computing a Social Optimum

For the fragmentation social function, we show that computing a social optimum is an **NP**-hard problem.

**PROPOSITION 4.1.** *Computing a social optimum with respect to fragmentation is NP-hard, even for claw-free graphs.*

**PROOF.** Given a graph $G$, fix a feasible partition $\pi$ for game $(G, \mathcal{F})$ and let $D$ be the set of vertices constructed as follows. For each coalition $C \in \pi$, $D$ contains exactly one center of a star spanning $G[C]$. Then, $D$ forms a dominating set in $G$ (every vertex of $V \setminus D$ has a neighbor in $D$). Conversely, any dominating set of $G$ induces a feasible partition for $(G, \mathcal{F})$. Thus, we conclude that computing a social optimum in $(G, \mathcal{F})$ with respect to fragmentation coincides with the problem of computing a minimum dominating set for $G$ (MINDS for short). The claim follows as MINDS is a well known **NP**-hard problem (Garey and Johnson 1979). Note that the **NP**-hardness of MINDS also holds if $G$ is restricted to be claw-free (Hedetniemi and Laskar 1988). $\square$

For the social function sociality, instead, efficient computation and even a general characterization is possible.

**PROPOSITION 4.2.** *For connected graphs on $n$ vertices, computing a social optimum $\pi^*$ with respect to sociality can be done in polynomial time and $\text{soc}(\pi^*) = n$.*

**PROOF.** An *edge cover* for a graph $G$ is a set of edges $E'$ such that every vertex of $G$ is incident to at least one edge of $E'$. A minimum edge cover, which is computable in polynomial-time (Garey and Johnson 1979), never contains 3 consecutive edges because the middle edge would be superfluous. Thus, a minimum edge cover induces a partition of the vertices into stars, and each star has at least one edge. The sociality of this solution is equal to the number of vertices. $\square$

## 4.2 Computing an Extreme Stable Partition

Using Theorem 3.12 and Proposition 4.1, we deduce that computing a best Nash stable partition with respect to fragmentation is **NP**-hard, even for claw-free graphs. We now show that hardness holds also for the sociality social function.

**THEOREM 4.3.** *Computing the best Nash stable partition with respect to sociality is NP-hard when the input graph $G$ has maximum degree equal to 5.*
<figure><img src="image_7.png" /><figcaption>Fig. 4. On the left: gadget $H(l_i)$. On the right: a possible Nash stable partition for agents in $H(l_i)$; centers of spanning stars are colored in black.</figcaption></figure>

PROOF. We propose a reduction from 3-DIMENSIONAL MATCHING (3-DM in short). An instance of 3-DM consists of a collection $C = \{s_1, \dots, s_m\} \subseteq X \times Y \times Z$ of $m$ triplets, where $X = \{x_1, \dots, x_n\}$, $Y = \{y_1, \dots, y_n\}$ and $Z = \{z_1, \dots, z_n\}$ are 3 pairwise disjoint sets of size $n$. A matching is a subset $M \subseteq C$ such that no two elements in $M$ agree in any coordinate, and the purpose of 3-DM is to answer the question: does there exist a perfect matching $M$ on $C$, that is, a matching of size $n$? This problem is known to be NP-complete (problem [SP1], page 221, in (Garey and Johnson 1979)), even if each element $t \in X \cup Y \cup Z$ appears in at most 3 triplets.

We start from an instance $I = (C, X \cup Y \cup Z)$ of 3-DM, where each element $t \in X \cup Y \cup Z$ appears in at most 3 triplets, and build a game $(G, \mathcal{F})$, where $G = (V, E)$ is as follows:

* vertex set $V$ contains $L \cup R$, where $L = \{l_1, \dots, l_m\}$ corresponds to the different triples of $C$ and $R = R^x \cup R^y \cup R^z$, where $R^t = \{r_1^t, \dots, r_n^t\}$ for $t \in \{x, y, z\}$, corresponds to elements of $X \cup Y \cup Z$;

* for $t \in \{x, y, z\}$, $\{l_i, r_j^t\} \in E$ if and only if $t_j$ is an element of triplet $s_i$;

* the bipartite graph constructed so far is usually called representative bipartite graph. This graph is completed by adding, for each $l_i \in L$, four vertices $b_i, c_i, d_i, e_i$ arranged in such a way to give life to the gadget, denoted as $H(l_i)$, illustrated in Figure 4 (on the left of the drawing), where we assume that triplet $s_i = (x_{i_1}, y_{i_2}, z_{i_3})$.

Observe that $G$ has $5m + 3n$ vertices and the maximum degree is 5, so the construction is polynomial in the size of $I$.

We claim that $I$ admits a perfect matching if and only if there exists a Nash stable partition $\pi$ of $(G, \mathcal{F})$ with $\text{soc}(\pi) \ge 5m+n$. Actually, we will prove that $5m+n$ is the best value reachable by any Nash stable partition $\pi$.

If $C' \subseteq C$ is a set of $n$ triplets forming a perfect matching, then consider the following partition $\pi$. For $s_i = (x_{i_1}, y_{i_2}, z_{i_3}) \in C'$, set $\pi(d_i) = \{d_i\}$, $\pi(e_i) = \{e_i\}$ and $\pi(l_i) = \{b_i, c_i, l_i, r_{i_1}^x, r_{i_2}^y, r_{i_3}^z\}$; an illustration of these 3 coalitions is proposed in Figure 4 (on the right of the drawing). For $s_i \notin C'$, set $\pi(l_i) = \{l_i, b_i, c_i, d_i, e_i\}$. It is easy to see that $\pi$ is a Nash stable partition with $\text{soc}(\pi) = 6n+5(m-n) = 5m+n$.

Conversely, let $\pi$ be a Nash stable partition. If $\{l_i, r_j^t\} \subseteq \pi(r_j^t)$ for some $i \in [m]$, $j \in [n]$ and $t \in \{x, y, z\}$, then the following property holds.

PROPERTY 1. (i) $\forall i' \neq i, l_{i'} \notin \pi(r_j^t)$, (ii) $\{b_i, c_i\} \subseteq \pi(r_j^t)$ and $\{d_i, e_i\} \cap \pi(r_j^t) = \emptyset$.

PROOF. Assume $\{l_i, r_j^t\} \subseteq \pi(r_j^t)$ for some $i \in [m], j \in [n]$ and $t \in \{x, y, z\}$.

For claim (i), assume, by way of contradiction, that $l_{i'} \in \pi(r_j^t)$ for some $i' \neq i$. By construction of graph $G$, this implies that $r_j^t$ is the center of the star in the subgraph $G[\pi(r_j^t)]$ induced by $\pi(r_j^t)$ (same arguments as in the proof of Lemma 3.1) and then $c_i \notin \pi(r_j^t)$. Also, by construction of $G$ and the fact that $\pi$ is Nash stable, it has to be $\pi(c_i) = \{b_i, c_i, d_i, e_i\}$. However, $|\pi(r_j^t)| \le 4$, because any element of $X \cup Y \cup Z$ appears in at most 3 triplets of $I = (C, X \cup Y \cup Z)$. We obtain a contradiction, since agent $l_i$ has a profitable deviation in $\pi$ by joining coalition $\pi(c_i)$.
To show claim (ii), observe that, by claim (i), we know that $l_i$ is a possible center of $G[\pi(r_j^t)]$. We deduce that $c_i \in \pi(l_i) = \pi(r_j^t)$, since otherwise $4 = |\pi(c_i)| \ge |\pi(l_i)|$ and agent $l_i$ would have a profitable deviation in $\pi$ by joining coalition $\pi(c_i)$. Hence, $b_i \in \pi(l_i)$ and $d_i, e_i \notin \pi(l_i) = \pi(r_j^t)$. $\square$

Let Cov be the set of $l_i \in L$ such that $\pi(l_i) = \pi(r_j^t)$ for some $j \in [n]$ and $t \in \{x, y, z\}$, and set $p := |Cov|$. By Property 1, for every $l_i \in Cov$, it must be $\pi(e_i) = \{e_i\}$ and $\pi(d_i) = \{d_i\}$ (see the right picture in Figure 4 for an illustration). Thus, there are $2p$ vertices in the set $\{d_1, e_1, \dots, d_m, e_m\}$ belonging to a singleton coalition in $\pi$. By definition, any $l_i \notin Cov$ does not share her coalition with an element of $R$, while any $l_i \in Cov$ can share her coalition with at most 3 elements of $R$. Thus, as $|Cov| = p$, there are at least $3n - 3p$ elements of $R$ belonging to a singleton coalition in $\pi$. It follows that $\text{soc}(\pi) \le 5m + 3n - (2p + 3n - 3p) = 5m + p \le 5m + n$ and the last inequality is tight only when $|Cov| = n$ or, equivalently, when $C' = \{s_i : l_i \in Cov\}$ is a perfect matching. $\square$

**COROLLARY 4.4.** *Computing the best Nash stable partition with respect to either sociality or fragmentation is NP-hard even for planar graphs.*

**PROOF.** PLANAR 3-DM, which requires planarity of the representative bipartite graph of an instance $I = (C, X \cup Y \cup Z)$, is proved **NP**-complete in (Dyer and Frieze 1986). As the construction of our gadgets does not break the planarity of the representative bipartite graph, the result for the sociality social function is a direct consequence of Theorem 4.3.

For the fragmentation social function, note that $\text{frag}(\pi) \ge 3n + m - p$, where we recall that $p \le n$. Moreover, $\text{frag}(\pi) = 2n + m$ if and only if $p = n$ or, equivalently, if $I$ admits a perfect (3-dimensional) matching. $\square$

As to the problem of computing a worst Nash stable partition, we give a hardness result with respect to sociality, while the case of the fragmentation social function remains open.

**THEOREM 4.5.** *Computing the worst Nash stable partition with respect to sociality is NP-hard when the input graph has maximum degree equal to 11.*

**PROOF.** We reduce from 2-BALANCED 3-SAT, denoted as (3, B2)-SAT, where an instance $I = (C, X)$ is given by a set $C$ of CNF clauses over a set of boolean variables $X$ such that each clause has exactly 3 literals and each variable appears exactly 4 times, twice negative and twice positive. Deciding whether an instance of (3, B2)-SAT is satisfiable has been shown **NP**-complete in (Berman et al. 2003).

Consider an instance $I = (C, X)$ of (3, B2)-SAT with clauses $C = \{c_1, \dots, c_m\}$ and variables $X = \{x_1, \dots, x_n\}$. We build a connected graph $G = (V, E)$ as follows:

* for each clause $c_j = \ell_{j_1} \lor \ell_{j_2} \lor \ell_{j_3}$, where $\ell_{j_i}$ is a literal for each $i \in [3]$, we create a *clause gadget* $H(c_j)$, containing a vertex $c_j$ together with four special vertices $c'_j, c'_1, c'_2, c'_3$, as depicted in Figure 5;

* for each variable $x_i \in X$, we build a variable gadget $H(x_i)$ made of 19 vertices, six of which are special and denoted as $x_i, \bar{x}_i, x'_i, \bar{x}'_i, e_i$ and $e'_i$. Vertices $x_i$ and $\bar{x}_i$ correspond to literals $x_i$ (positive) and $\bar{x}_i$ (negative) respectively. The variable gadget is depicted in Figure 6. Observe that vertices $x'_i, \bar{x}'_i$ and $e'_i$ have degree 1 in the whole graph $G$.

* each vertex $c_i^j$ is linked to $\ell_{j_1}$ via a *linking gadget* $H(uv)$ depicted in Figure 7, where we set $u := c_i^j$ and $v := \ell_{j_1}$, where vertex $\ell_{j_1}$ for each $i \in [3]$ corresponds to either vertex $x_{j_1}$ or vertex $\bar{x}_{j_1}$ in the variable gadget $H(x_{j_1})$. The color of the vertices in these gadgets will be useful in the subsequent proofs. The merging of a clause gadget $H(c_i^j)$ with the three linking gadgets $H(c_i^j \ell_{j_1})$, with $i \in [3]$, gives life to the *patching clause gadget* $\text{PCG}(c_j)$ depicted in Figure 8.

The construction of $G = (V, E)$ is complete and $|V| = 11m + 19n$. Thus, the reduction is polynomial in the dimension of $I$.
<figure><img src="image_8.png" /><figcaption>Fig. 5. Clause gadget $H(c_j)$.</figcaption></figure>

<figure><img src="image_9.png" /><figcaption>Fig. 6. Variable gadget $H(x_i)$.</figcaption></figure>

<figure><img src="image_10.png" /><figcaption>Fig. 7. Linking gadget $H(uv)$ between vertices $u$ and $v$.</figcaption></figure>

<figure><img src="image_11.png" /><figcaption>Fig. 8. The patching clause gadget $PCG(c_j)$ linking clause $c_j = \ell_{j_1} \lor \ell_{j_2} \lor \ell_{j_3}$ to its three literals via linking gadgets $H(c_i^j \ell_{j_i})$ with $i \in [3]$.</figcaption></figure>

Now, we prove that any Nash stable partition for $(G, \mathcal{F})$ achieves a sociality of at least $|V| - 2n - m$ and is equal to $|V| - 2n - m$ only if $I$ is satisfiable. To achieve this task, we show two fundamental properties that need to be satisfied by any Nash stable partition.

**LEMMA 4.6.** *Fix a Nash stable partition $\pi$. For any clause $c_j$, at most one vertex of $PCG(c_j)$, namely $c'_j$, may belong to a singleton coalition in $\pi$. This happens only if $\pi(c_j)$ contains two adjacent black vertices and $|\pi(c_j)| = 6$.*

**PROOF.** Fix a clause $c_j$ and consider two adjacent black vertices $x$ and $y$ in $PCG(c_j)$. Assume, by way of contradiction, that $\pi(x) \neq \pi(y)$ and assume further, without loss of generality, that $|\pi(x)| \geq |\pi(y)|$. Any star
spanning $G[\pi(x)]$ can only be centred at a vertex $w$ which is either $x$ or a vertex adjacent to $x$. By the topology of $G$, $w$ is also adjacent to $y$ (see Figure 8), so $y$ has a profitable deviation by joining $\pi(x)$: a contradiction to the Nash stability of $\pi$. Thus, no black vertex in $PCG(c_j)$ belongs to a singleton coalition in $\pi$.

Now consider the set of vertices $\{c_j, c_1^j, c_2^j, c_3^j\}$. Observe that $c_j$ cannot belong to a singleton coalition in $\pi$, otherwise also $c'_j$ must belong to a singleton coalition, and so it has a profitable deviation by joining $\pi(c_j)$. Any star spanning coalition $G[\pi(c_j)]$ needs to be centred at a vertex $v \in \{c_j, c_1^j, c_2^j, c_3^j\}$ (if the star is centred at $c'_j$, then it can also be centred at $c_j$). Thus, any vertex in $\{c_1^j, c_2^j, c_3^j\}$ occupying a singleton coalition in $\pi$ has a profitable deviation by joining $\pi(c_j)$: a contradiction to the Nash stability of $\pi$. So, we conclude that only $c'_j$ can belong to a singleton coalition.

To show the last claim, observe that whenever $\pi(c'_j) = \{c'_j\}$, $c'_j$ would always benefit from deviating to $\pi(c_j)$ as long as this deviation does not violate the feasibility constraint. Thus, we deduce that $\pi(c_j)$ must contain at least a black vertex. As we have shown at the beginning of the proof that adjacent black vertices always share the same coalition, it follows that $|\pi(c_j)| \ge 4$. Now, for any vertex $c_i^j \notin \pi(c_j)$, $i \in [3]$, we have $|\pi(c_i^j)| \le 4$. Thus, this vertex has a profitable deviation to $\pi(c_j)$: a contradiction. We conclude that $\pi(c_j)$ contains two adjacent black vertices and set $\{c_1^j, c_2^j, c_3^j\}$. $\square$

**LEMMA 4.7.** *Fix a Nash stable partition $\pi$. For any variable gadget $H(x_i)$, at most two vertices may belong to a singleton coalition. If exactly two vertices belong to a singleton coalition, there exists $\ell \in \{x_i, \bar{x}_i\}$ such that $\ell$ is the centre of a star spanning $G[\pi(\ell)];$ moreover, for each $\ell \in \{x_i, \bar{x}_i\}$ such that $\ell$ is the centre of a star spanning $G[\pi(\ell)]$, we have $|\pi(\ell)| \ge 6$.*

**PROOF.** Let us denote by $B_i$ the set of black vertices adjacent to $x_i$. We start by showing that all vertices in $B_i$ are in the same coalition as $x_i$.

Assume first that none of these vertices belongs to $\pi(x_i)$. Observe that, if $x_i$ is the centre of a spanning star for $\pi(x_i)$, then, for any $w \in B_i$, $w$ can deviate to $\pi(x_i)$ without violating the feasibility constraint and $x_i$ can deviate to $\pi(w)$ without violating the feasibility constraint. Clearly, one of these two deviations has to be a profitable one, contradicting the Nash stability of $\pi$. Thus, $x_i$ cannot be the centre of a spanning star for $\pi(x_i)$. Under this premise, we have that, to guarantee feasibility, it must be $|\pi(x_i)| \le 4$ (see Figure 6). However, it is easy to see that, by the Nash stability of $\pi$, $B_i \subset \pi(x_i')$, so that $|\pi(x_i')| = 4$. This implies that $x_i$ has a profitable deviation to $\pi(x_i')$, contradicting the Nash stability of $\pi$.

So, assume now that at least one vertex in $B_i$ belongs to $\pi(x_i)$, but $B_i \setminus \pi(x_i) \ne \emptyset$. In this case, the centre of any spanning star of $G[\pi(x_i)]$ must belong to $B_i \cup \{x_i\}$. Fix a vertex $w \in B_i \setminus \pi(x_i)$ and observe that there exists a spanning star of $G[\pi(w)]$ centred at $w$. It follows that $w$ can feasibly deviate to $\pi(x_i)$ and $x_i$ can feasibly deviate to $\pi(w)$. Clearly, one of the two deviations must be an improving one, thus rising a contradiction. By the symmetry of $G$, we can also claim that all black vertices adjacent to $\bar{x}_i$ are in the same coalition as $\bar{x}_i$.

Now, we prove the claim by considering two possible cases: (i) $G[\pi(\ell)]$ does not admit a spanning star centred at $\ell$ for each $\ell \in \{x_i, \bar{x}_i\}$, (ii) $G[\pi(\ell)]$ admits a spanning star centred at $\ell$ for some $\ell \in \{x_i, \bar{x}_i\}$.

If case (i) holds, as all black vertices adjacent to $\ell$ belong to $\pi(\ell)$, it must be $x_i' \in \pi(x_i)$ and $\bar{x}_i' \in \pi(\bar{x}_i)$. By the Nash stability of $\pi$, the two vertices which are adjacent to both $x_i$ and $\bar{x}_i$ must belong to the same dedicated coalition in $\pi$. For the remaining 7 vertices of $H(x_i)$, only two Nash stable arrangements are possible: either $|\pi(e_i)| = 6$ and $|\pi(e_i')| = 1$, or $\pi(e_i) = \pi(e_i')$ and the 4 remaining vertices are split in two equal-size coalitions. Thus, if case (i) holds, at most one vertex may belong to a singleton coalition.

If case (ii) holds, there exists $\ell \in \{x_i, \bar{x}_i\}$ such that the two vertices which are adjacent to both $x_i$ and $\bar{x}_i$ belong to $\pi(\ell)$. By the symmetry of $G$, assume, without loss of generality, that $\ell = x_i$. As $|\pi(e_i)| \le 6$, it follows that the two vertices adjacent to both $e_i$ and $x_i$ must belong to $\pi(x_i)$, which gives $|\pi(x_i)| \ge 8$. Now, if $\pi(\bar{x}_i') = \pi(\bar{x}_i)$, so that $\bar{x}_i$ is not the centre of any star spanning $G[\pi(\bar{x}_i)]$, then either $\pi(e_i') = \pi(e_i)$ and the two vertices adjacent
to both $e_i$ and $\bar{x}_i$ are coupled in a dedicated coalition, or $\pi(e_i') = \{e_i'\}$ and $|\pi(e_i)| = 4$. Thus, we conclude that at most two vertices of $H(x_i)$ may belong to a singleton coalition and that, when this happens, there exists a unique $\ell \in \{x_i, \bar{x}_i\}$ such that $G[\pi(\ell)]$ admits a spanning star centred at $\ell$; moreover, it holds that $|\pi(\ell)| \ge 6$. If $\pi(\bar{x}_i') \ne \pi(\bar{x}_i)$, so also $\bar{x}_i$ is the centre of a star spanning $G[\pi(\bar{x}_i)]$, then, as $|\pi(e_i)| \le 4$ and $\pi(\bar{x}_i)$ contains all three black vertices adjacent to $\bar{x}_i$, the two vertices adjacent to both $e_i$ and $\bar{x}_i$ must belong to $\pi(\bar{x}_i)$, so that $|\pi(\bar{x}_i)| \ge 6$. The remaining 3 vertices, namely $e_i$, $e_i'$ and the vertex between them, are gathered in a dedicated coalition. Thus, we conclude that two vertices of $H(x_i)$ belong to a singleton coalition and, for each $\ell \in \{x_i, \bar{x}_i\}$, it holds that $|\pi(\ell)| \ge 6$ and $G[\pi(\ell)]$ admits a spanning star centred at $\ell$.

Putting all together, we conclude that at most two vertices of $H(x_i)$ may belong to a singleton coalition and, when this happens, there exists $\ell \in \{x_i, \bar{x}_i\}$ such that $G[\pi(\ell)]$ admits a spanning star centred at $\ell$; moreover, for each $\ell \in \{x_i, \bar{x}_i\}$ such that $G[\pi(\ell)]$ admits a spanning star centred at $\ell$, it holds that $|\pi(\ell)| \ge 6$. $\square$

By Lemmas 4.6 and 4.7, it follows that $\text{soc}(\pi) \ge |V| - 2n - m$. Moreover, in order to have $\text{soc}(\pi) = |V| - 2n - m$, two conditions must simultaneously hold: (i) for each $j \in [m]$, coalition $\pi(c_j)$ must contain two adjacent black vertices and $|\pi(c_j)| = 6$; (ii) for each $i \in [n]$, there exists $\ell \in \{x_i, \bar{x}_i\}$ such that $|\pi(\ell)| \ge 6$ and $\ell$ is the centre of a star spanning $G[\pi(\ell)]$. Now, let us define the following assignment to variables in $X$: if both $x_i$ and $\bar{x}_i$ are the centre of the star spanning the subgraph induced by its coalition, set to true the value of the literal belonging to the largest coalition; otherwise, set to true the value of the literal not being the centre of the star spanning the subgraph induced by its coalition. By condition (ii), this defines an assignment for all variables in $X$.

Consider a literal $\ell_i \in \{x_i, \bar{x}_i\}$ occurring in clause $c_j$. By the definition of PCG($c_j$), we have that two adjacent black vertices of this gadget are adjacent to vertex $\ell_i$ belonging to the variable gadget $H(x_i)$. Let $i$ be such that $\ell_i$ is adjacent to the pair of black vertices belonging to $\pi(c_j)$. As $|\pi(c_j)| = 6$ (by condition (i)) and $|\pi(\ell_i)| \ge 6$ whenever $\ell_i$ is the centre of the star spanning $G[\pi(\ell_i)]$ (by Lemma 4.7), it follows that any of the black vertices in $\pi(c_j)$ has a profitable deviation to $\pi(\ell_i)$, thus rising a contradiction. Hence, we deduce that, for each $j \in [m]$, there exists a literal $\ell_i$ occurring in $c_j$ such that $\ell_i$ is not the centre of a star spanning $G[\pi(\ell_i)]$. That is, for each $j \in [m]$, there exists a literal $\ell_i$ occurring in $c_j$ such that $\ell_i$ is true. This implies that $I$ is satisfiable. $\square$

# 5 Conclusions

Two main problems are left open: closing the gap between upper and lower bounds on the price of stability with respect to sociality for games played on general graphs, and determining the complexity of computing a worst Nash stable partition with respect to fragmentation. Addressing the problem of computing extreme core stable partition is also worth to be investigated.

Applying our feasibility constraint (i.e., imposing a spanning star) to hedonic games having agents' preferences other than the ones considered in this paper is clearly an interesting research direction. Other graph patterns are appealing in our opinion: the largest distance between any pair of agents, or the distance to some agent of the coalition can be upper bounded by a given number (for the latter, the distance to some agent is 1 in this paper).

One can also think of the *group activity selection problem* in which a network of the agents is taken into consideration in order to define which coalitions are feasible (Darmann et al. 2018). This problem is strongly related to hedonic games as the agents, in addition to their number, have to choose a common activity.

# Acknowledgements

We thank an anonymous reviewer for spotting out an inaccuracy in Theorem 3.6 in the preliminary version of this paper appeared in the proceedings of SAGT 2019 (Bilò, Gourvès, et al. 2019). We also thank the reviewers of the *Journal of Artificial Intelligence Research* whose comments helped to better motivate our game model.

This work is dedicated to the memory of Jérôme Monnot who sadly passed away on December 11, 2019.
## References

N. Andelman, M. Feldman, and Y. Mansour. 2009. "Strong price of anarchy." *Games and Economic Behavior*, 65, 2, 289-317.

E. Anshelevich, A. Dasgupta, J. M. Kleinberg, É. Tardos, T. Wexler, and T. Roughgarden. 2004. "The Price of Stability for Network Design with Fair Cost Allocation." In: *Proc. of FOCS*, 295-304.

K. R. Apt, B. de Keijzer, M. Rahn, G. Schäfer, and S. Simon. 2017. "Coordination games on graphs." *Int. J. Game Theory*, 46, 3, 851-877.

R. Aumann. 1959. "Acceptable points in general cooperative *n*-person games." In: *Contributions to the Theory of Games IV*. Princeton Univ. Press, New Jersey, NJ, USA.

H. Aziz, F. Brandt, and H. G. Seedig. 2011. "Stable partitions in additively separable hedonic games." In: *Proc. of AAMAS*, 183-190.

H. Aziz and R. Savani. 2016. "Hedonic Games." In: *Handbook of Computational Social Choice*, 356-376.

C. Ballester. 2004. "NP-completeness in hedonic games." *Games & Econ. Behavior*, 49, 1, 1-30.

A. Balliu, M. Flammini, G. Melideo, and D. Olivetti. 2017. "Nash stability in social distance games." In: *Proc. of AAAI*, 342-348.

A. Balliu, M. Flammini, and D. Olivetti. 2017. "On pareto optimality in social distance games." In: *Proc. of AAAI*, 349-355.

S. Banerjee, H. Konishi, and T. Sönmez. Jan. 2001. "Core in a simple coalition formation game." *Social Choice and Welfare*, 18, 1, (Jan. 2001), 135-153.

P. Berman, M. Karpinski, and A. D. Scott. 2003. "Approximation Hardness of Short Symmetric Instances of MAX-3SAT." *Electronic Colloquium on Computational Complexity (ECCC)*, 049.

V. Bilò, A. Fanelli, M. Flammini, G. Monaco, and L. Moscardelli. 2018. "Nash stable outcomes in fractional hedonic games: Existence, efficiency and computation." *Journal of Artificial Intelligence Research*, 62, 315-371.

V. Bilò, A. Fanelli, M. Flammini, G. Monaco, and L. Moscardelli. 2019. "Optimality and Nash stability in additive separable generalized group activity selection problems." In: *Proc. of IJCAI*, 102-108.

V. Bilò, L. Gourvès, and J. Monnot. 2019. "On a simple hedonic game with graph-restricted communication." In: *Proc. of SAGT*, 252-265.

A. Bogomolnaia and M. O. Jackson. 2002. "The Stability of Hedonic Coalition Structures." *Games and Economic Behavior*, 38, 2, 201-230.

S. Brânzei and K. Larson. 2009. "Coalitional affinity games and the stability gap." In: *Proc. of IJCAI*, 79-84.

S. Brânzei and K. Larson. 2011. "Social distance games." In: *Proc. of IJCAI*, 91-96.

M. Charikar, V. Guruswami, and A. Wirth. 2005. "Clustering with qualitative information." *Journal of Computer and System Sciences*, 71, 3, 360-383.

A. Darmann, E. Elkind, S. Kurz, J. Lang, J. Schauer, and G. J. Woeginger. 2018. "Group activity selection problem with approval preferences." *Int. J. Game Theory*, 47, 3, 767-796.

E. D. Demaine, D. Emanuel, A. Fiat, and N. Immorlica. 2005. "Correlation clustering in general weighted graphs." *Theo. Comp. Sci.*, 36, 3, 360-383.

X. Deng and C. H. Papadimitriou. 1994. "On the Complexity of Cooperative Solution Concepts." *Math. Oper. Res.*, 19, 2, 257-266.

J. H. Drèze and J. Greenberg. 1980. "Hedonic Coalitions: Optimality and Stability." *Econometrica*, 48, 4, 987-1003.

M. E. Dyer and A. M. Frieze. 1986. "Planar 3DM is NP-Complete." *Journal of Algorithms*, 7, 2, 174-184.

B. Escoffier, L. Gourvès, and J. Monnot. 2012. "Strategic Coloring of a Graph." *Internet Mathematics*, 8, 4, 424-455.

M. Feldman, L. Lewin-Eytan, and J. Naor. 2015. "Hedonic clustering games." *ACM Transactions on Parallel Computing*, 2, 1, 4:1-4:48.

M. Flammini, G. Monaco, L. Moscardelli, M. Shalom, and S. Zaks. 2018. "Online coalition structure generation in graph games." In: *Proc. of AAMAS*, 1353-1361.

M. R. Garey and D. S. Johnson. 1979. *Computers and Intractability: A Guide to the Theory of NP-Completeness*. W. H. Freeman & Co., New York, NY, USA. ISBN: 0716710447.

T. Harks, M. Klimm, and R. H. Möhring. 2013. "Strong equilibria in games with the lexicographical improvement property." *International Journal of Game Theory*, 42, 2, 461-482.

S. T. Hedetniemi and R. C. Laskar. 1988. "Recent results and open problems in domination theory." *Applications Disc. Math.*, 205-218.

M. Hoefer, D. Vaz, and L. Wagner. 2018. "Dynamics in matching and coalition formation games with structural constraints." *Artificial Intelligence*, 262, 222-247.

A. Igarashi and E. Elkind. 2016. "Hedonic Games with Graph-restricted Communication." In: *Proc. of AAMAS*, 242-250.

A. Igarashi, D. Peters, and E. Elkind. 2017. "Group activity selection on social networks." In: *Proc. of AAAI*, 565-571.

E. Koutsoupias and C. H. Papadimitriou. 1999. "Worst-case Equilibria." In: *Proc. of STACS*, 404-413.

G. Monaco, L. Moscardelli, and Y. Velaj. 2019. "On the Performance of Stable Outcomes in Modified Fractional Hedonic Games with Egalitarian Social Welfare." In: *Proc. of AAMAS*, 873-881.

G. Monaco, L. Moscardelli, and Y. Velaj. 2018. "Stable outcomes in modified fractional hedonic games." In: *Proc. of AAMAS*, 937-945.

J. F. Nash. 1950. "Equilibrium points in *n*-person games." *Proceedings of the National Academy of Science*, 36, 1, 48-49.

M. Olsen. 2009. "Nash stability in additively separable hedonic games and community structures." *Theory of Computing Systems*, 45, 4, 917-925.

M. Olsen, L. Bækgaard, and T. Tambo. 2012. "On non-trivial Nash stable partitions in additive hedonic games with symmetric 0/1-utilities." *Information Processing Letters*, 112, 23, 903-907.
P. N. Panagopoulou and P. G. Spirakis. 2008. "A Game Theoretic Approach for Efficient Graph Coloring." In: *Proc. of ISAAC*, 183-195.

D. Peters. 2016. "Graphical Hedonic Games of Bounded Treewidth." In: *Proc. of AAAI*, 586-593.

D. Peters and E. Elkind. 2015. "Simple causes of complexity in hedonic games." In: *Proc. of AAAI*, 617-623.

Received 5 November 2023; accepted 24 July 2024