We start with the non-existence of IS partitions, where we provide a counterexample using $15$ agents. The weights were found with the help of a computer.

There exists a symmetric FHG without an IS partition.

Define the sets of agents $N_i = \{a_i,b_i,c_i\}$ for $i \in \{1,\dots, 5\}$ and consider the FHG on the agent set $N = \bigcup_{i=1}^5 N_i$ where symmetric weights are given by

* $\util(a_i, b_i) = \util(b_i, c_i) = \util(a_i,c_i) = 228, i\in \{1,\dots, 5\}$,

* $\util(a_i,a_{i+1}) = 436, \util(a_i,b_{i+1}) = 228, \util(a_i,c_{i+1}) = 248, i\in \{1,\dots, 5\}$,

* $\util(b_i,a_{i+1}) = 223, \util(b_i,b_{i+1}) = 171, \util(b_i,c_{i+1}) = 236, i\in \{1,\dots, 5\}$,

* $\util(c_i,a_{i+1}) = 223, \util(c_i,b_{i+1}) = 171, \util(c_i,c_{i+1}) = 188, i\in \{1,\dots, 5\}$, and

* $\util(x,y) = - 2251$ for all agents $x,y\in N$ such that the weight is not defined yet.

In the above definition, all indices are to be read modulo $5$ (where the modulo function is assumed to map to $\{1,\dots, 5\}$). Note that the large negative weight exceeds the sum of positive weights incident to any agents. Hence, agents linked by a negative weight, can never be in a common coalition in any IS partition. The FHG consists of five triangles that form a cycle. The structure of the game is illustrated in Figure <ref>. While proving that there does not exist an IS partition requires a lengthy case distinction and many computations,
the global intuition for the proof is to observe that IS dynamics in this instance always cycle. To see this, start with the partition $(N_5\cup N_1, N_2, N_3, N_4)$. First, $a_1$ deviates by joining $N_2$. Then, $b_1$ joins this new coalition, then $c_1$. After this step, we are in an isomorphic state as in the initial partition.

[protovertex] (b) at (0,-0.1);
[protovertex] (a) at (0,1.1);
[protovertex] (c) at (0.33,0.5);
(a) edge (b);
(b) edge (c);
(c) edge (a);,
(s) at (-.65,0.3);
(t) at (.65,0.3);
[bend left,->]  (s) to (t);,
[->] (-.6,0.3) arc[radius= 2cm, start angle = 105, end angle= 75];
[regular polygon,regular polygon sides=10,minimum size=4cm] (p) at (0,0);
(p.corner 1) pic complexnode;
[label = 90:$a_1$] at (a) ;
[label = 270:$c_1$] at (b) ;
[label = 0:$b_1$] at (c) ;
(p.corner 2) pic[rotate = 20] complexarc;
(p.corner 3) pic[rotate = 72] complexnode;
[label = 180:$a_5$] at (a) ;
[label = 270:$c_5$] at (b) ;
[label = 90:$b_5$] at (c) ;
(p.corner 4) pic[rotate = 92] complexarc;
(p.corner 5) pic[rotate = 144] complexnode;
[label = 270:$a_4$] at (a) ;
[label = 0:$c_4$] at (b) ;
[label = 180:$b_4$] at (c) ;
(p.corner 6) pic[rotate = 164] complexarc;
(p.corner 7) pic[rotate = 216] complexnode;
[label = 270:$a_3$] at (a) ;
[label = 90:$c_3$] at (b) ;
[label = 270:$b_3$] at (c) ;
(p.corner 8) pic[rotate = 236] complexarc;
(p.corner 9) pic[rotate = 288] complexnode;
[label = 0:$a_2$] at (a) ;
[label = 180:$c_2$] at (b) ;
[label = 270:$b_2$] at (c) ;
(p.corner 10) pic[rotate = 308] complexarc;

Five triangles are ordered in a cycle such that there is a tendency of agents in $N_i$ to deviate to coalitions in $N_{i+1}$.

[protovertex,label = 270:$c_i$] (b1) at (0,0);
[protovertex,label = $a_i$] (a1) at (0,6);
[protovertex,label = 180:$b_i$] (c1) at (1,3);
[protovertex,label = 270:$c_{i+1}$] (b2) at (6.5,0);
[protovertex,label = $a_{i+1}$] (a2) at (6.5,6);
[protovertex,label = 0:$b_{i+1}$] (c2) at (7.5,3);
(a1) edge node[fill=white,anchor=center, pos=0.5, inner sep =2pt] $228$ (b1);
(b1) edge node[fill=white,anchor=center, pos=0.5, inner sep =2pt] $228$ (c1);
(c1) edge node[fill=white,anchor=center, pos=0.5, inner sep =2pt] $228$ (a1);
(a2) edge node[fill=white,anchor=center, pos=0.3, inner sep =2pt] $228$ (b2);
(b2) edge node[fill=white,anchor=center, pos=0.5, inner sep =2pt] $228$ (c2);
(c2) edge node[fill=white,anchor=center, pos=0.5, inner sep =2pt] $228$ (a2);
(a1) edge node[fill=white,anchor=center, pos=0.2, inner sep =2pt] $436$ (a2);
(a1) edge node[fill=white,anchor=center, pos=0.15, inner sep =2pt] $248$ (b2);
(a1) edge node[fill=white,anchor=center, pos=0.2, inner sep =2pt] $228$ (c2);
(b1) edge node[fill=white,anchor=center, pos=0.15, inner sep =2pt] $223$ (a2);
(b1) edge node[fill=white,anchor=center, pos=0.2, inner sep =2pt] $188$ (b2);
(b1) edge node[fill=white,anchor=center, pos=0.2, inner sep =2pt] $171$ (c2);
(c1) edge node[fill=white,anchor=center, pos=0.17, inner sep =2pt] $223$ (a2);
(c1) edge node[fill=white,anchor=center, pos=0.17, inner sep =2pt] $236$ (b2);
(c1) edge node[fill=white,anchor=center, pos=0.17, inner sep =2pt] $171$ (c2);

The transition weights between the triangles allow for infinite loops of deviations.

Description of the symmetric FHG without IS partition in the proof of Theorem <ref>.

We are ready for the main proof. Let $\partition$ be any partition of the agents and assume that $\partition$ is IS. In particular, no agent receives negative utility. Therefore there exists an $i\in \{1,\dots, 5\}$ such that $\partition(a_i)\cap \{a_1,\dots,a_5\}= \{a_i\}$. We may assume, without loss of generality, that $a_1$ is such an agent. In the following, we will
distinguish all the possible cases for the coalition of $a_1$ in $\partition$ and show that none of them can occur in an IS partition, deriving a contradiction.

* Goal 1: $b_2\notin \partition(a_1)$.

First, assume for contradiction that $b_2\in \partition(a_1)$, which implies that $\partition(a_1)\subseteq N_1\cup N_2$. If $\partition(a_2)\subseteq N_1\cup N_2$, then $\partition(a_2)\subseteq \{a_2, c_2, c_1, b_1\}$, and therefore $\util_{a_2}(\partition) \le 168.5$ (the best case is $\partition(a_2) = \{a_2, c_2, c_1, b_1\}$ with $\util_{a_2}(\{a_2, c_2, c_1, b_1\}) = \frac {228 + 223 + 223}{4} = 168.5$), while $\util_{a_2} (\{a_2\}\cup \partition(a_1))\ge 221.3$ (the worst case is $\partition(a_1) = \{a_1,b_2\}$ with $\util_{a_2}(\{a_2, a_1, b_2\}) = \frac {436 + 228}{3} = 221.33{\dots}$).
Hence, $a_2$ has an incentive to deviate (making no agent in $\partition(a_1)$ worse). Therefore, $\partition(a_2)\subseteq N_2\cup N_3$ and more precisely $\partition(a_2) \subseteq \{a_2,c_2,a_3,c_3,b_3\}$. In addition, by the same potential deviation, $a_3\in \partition(a_2)$ and $|\partition(a_2)|\ge 3$.

Next, consider the case that $c_2\in \partition(a_2)$. Then, $\util_{b_2}(\partition)\le 142.5$, while $\util_{b_2}(\{b_2\}\cup\partition(a_2))\ge 169.75$ and $b_2$ would have a beneficial IS deviation. Hence, $c_2\notin \partition(a_2)$.
If $c_2\notin \partition(a_1)$, then $\util_{c_2}(\partition)\le \max\{141.34,119.67\} = 141.34$ (this is if $c_2$ forms a coalition with $N_1\setminus \{a_1\}$ or $N_3\setminus \{a_3\}$), while $\util_{c_2}(\{c_2\}\cup\partition(a_1))\ge 158.6$ and it is easily seen that $c_2$ can only improve agents in $\partition(a_1)$. It follows that $c_2\in \partition(a_1)$.

If $c_3\notin \partition(a_2)$, then $\partition(a_2) = \{a_2,a_3,b_3\}$ and $c_3$ would deviate by joining $\partition(a_2)$. Hence, $\{a_2,a_3,c_3\}\subseteq \partition(a_2)$. But then $\util_{b_2}(\partition)\le 159.6$ (the best case being $\partition(b_2) = N_1\cup\{b_2,c_2\}$), while $\util_{b_2}(\{b_2\}\cup \partition(a_2)) \ge 171.6$ (the worst case here is $\partition(b_2) = N_3\cup\{a_2,b_2\}$ which is worse than the smaller $\{a_2,b_2,a_3,c_3\}$) and joining with $b_2$ makes no agent worse. In conclusion, the initial assumption was wrong and $b_2\notin \partition(a_1)$.

* Goal 2: $c_2\notin \partition(a_1)$.

Second, assume for contradiction that $c_2\in \partition(a_1)$. As in the previous case, it is easily seen that $\partition(a_2)\subseteq \{a_2,b_2\}\cup N_3$, $a_3\in \partition(a_2)$, and $|\partition(a_2)|\ge 3$. If $b_2\notin \partition(a_2)$, then $\util_{b_2}(\partition) \le 118$ (the best coalitions in $N_1\cup N_2$ and $N_2\cup N_3$ are $\{b_2,b_1,c_1\}$ and $\{b_2,c_3\}$, respectively) while $\util_{b_2}(\{b_2\}\cup \partition(a_2))\ge 155.5$. Hence, $b_2\in \partition(a_2)$. But then $\util_{c_2}(\partition) \le 168$ while $\util_{c_2}(\{c_2\}\cup \partition(a_2))\ge 169.75$ and $c_2$ would join $\partition(a_2)$ making no agent worse. We conclude that $c_2\notin \partition(a_1)$ and can therefore assume that $\partition(a_1)\subseteq N_1\cup (N_5\setminus\{a_5\})$.

* Goal 3: $c_1\notin \partition(a_1)$.

Third, assume for contradiction that $c_1\in \partition(a_1)$. Then, $\util_{a_5}(\partition)\le \max\{223,171\} = 223$ (where the first utility in the maximum refers to the coalition $N_4\cup N_5$ and the second utility to $N_5\cup \{b_1\}$). However, $\util_{a_5}(\{a_5\}\cup \partition(a_1))\ge 228$. Since joining $\partition(a_1)$ with $a_5$ makes no agent worse, this is not possible. Hence, $c_1\notin \partition(a_1)$.

* Goal 4: $b_1\notin \partition(a_1)$.

Forth, assume for contradiction that $b_1\in \partition(a_1)$. Then, $\util_{c_1}(\{c_1\}\cup \partition(a_1))\ge 152$ and adding $c_1$ to $\partition(a_1)$ leaves no agent worse off. Since, $\util_{c_1}(\{c_1\}\cup N_2) = 145.5$, it must hold that $\partition(c_1)\subseteq \{c_1\}\cup N_5$ and even $\{a_5,b_5\}\subseteq \partition(c_1)$ since otherwise $\util_{c_1}(\partition)\le 145.4$. But then $\util_{a_1}(\partition)\le 150.4$ while $\util_{a_1}(\{a_1\}\cup\partition(c_1)) \ge 221.75$ and $a_1$ would deviate making no agent worse. It follows that $b_1\notin \partition(a_1)$.

* Goal 5: $\partition(a_1)\not\subseteq \{a_1,c_5,b_5\}$.

It remains the case that $\partition(a_1)\subseteq \{a_1,c_5,b_5\}$. If $|\partition(c_1)|\ge 2$, then $a_1$ would deviate by joining $\partition(c_1)$, making no agent worse. If, however, $c_1$ is in a singleton coalition, then $c_1$ would join $\partition(a_1)$, making no agent worse and improving her utility.

It follows that no coalition for agent $a_1$ can be possible in an IS partition $\partition$, implying that the instance admits no IS partition.

Employing this counterexample, the methods of <cit.>, which originate from hardness constructions of <cit.>, can be used to show that it is -hard to decide about the existence of IS partitions in symmetric FHGs.

For the following corollary, we omit the full proof because it is analogous to the weaker statement by <cit.>. The main method will also be applied in the proof of Theorem <ref>, which considers convergence of the IS dynamics in the case that the FHGs even have symmetric, non-negative weights.

Deciding whether there exists an individually stable partition in symmetric FHGs is -hard.

In the reduction by <cit.>, we replace the non-symmetric gadget by an agent-minimal symmetric FHG that admits no IS partition. Such an FHG exists according to Theorem <ref>.[In fact, we can use a subgame of the game constructed in Theorem <ref>. Note that we have no proof of agent-minimality of this game but we can simply remove agents until it is agent-minimal.] The weights in the symmetric part of their reduced instances must be large enough to incentivize the agent in the gadget to stay in a coalition outside the gadget.

If we consider symmetric, non-negative utilities, the grand coalition forms an NS, and therefore IS,
partition of the agents. However, deciding about the convergence of the IS dynamics starting with the is -hard. The reduction uses similar methods as <cit.> and <cit.>. We can avoid negative weights by the fact that, due to symmetry of the weights, in a dynamics starting with the , all coalitions that can be obtained in the process must have strictly positive mutual utility for all pairs of agents in the coalition.

ISFHG is -hard and ISFHG is -hard, even in symmetric FHGs with non-negative weights. The former is even true if the initial partition is the .

From now on, we consider simple FHGs. We start with the additional assumption of symmetry.

The dynamics of IS deviations starting from the converges in simple symmetric FHGs in at most $\mathcal O(n^2)$ steps. The dynamics may take $\Omega(n\sqrt{n})$ steps.

We start with the lower bound. Consider the FHG induced by the complete graph on $n = k(k+1)/2$ agents for some non-negative integer $k\ge 1$. We partition the agents arbitrarily into sets $C_1,\dots, C_k$ where $|C_j| = j$ for $j = 1, \dots, k$. Now, we perform two phases of IS deviations. In the first phase, we form the coalitions $C_j$ by having agents join one by one. In the second phase, there are $k-1$ steps. In step $j$, the agents of coalition $C_j$ join coalitions $C_{j+1},\dots, C_k$ one after each other, thereby performing $k-j$ deviations each. The total number of deviations in the second phase is therefore $\sum_{j=1}^{k-1}j\cdot (k-j) = \frac 16 (k-1) k (k+1) = \Theta(k^3) = \Theta(k^2\sqrt{k^2}) = \Theta (n\sqrt{n})$. In particular, there can be $\Omega (n\sqrt{n})$ IS deviation steps starting from the .

For the upper bound, let a simple and symmetric FHG be given. Note that all coalitions formed through the deviation dynamics are cliques. Hence, every deviation step will increase the total number of edges in all coalitions. More precisely, the dynamics will increase the potential $\potential(\partition) = \sum_{C\in\partition} |C|(|C|-1)/2$ in every step by at least $1$. Since the total number of edges is bounded by $n(n-1)/2$, this proves the upper bound.

Note that there is a simple way to converge in a linear number of steps starting with the by forming largest cliques and removing them from consideration[The number of steps is linear even though finding such a sequence for an external coordinator would be computationally hard because it would require to solve a maximum clique problem.]. Surprisingly, it seems a lot harder to prove (non-)convergence of the dynamics if we start from an arbitrary partition, and we leave this as an open problem.

If we allow for asymmetries, the dynamics is not guaranteed to converge anymore. For instance, the IS dynamics on an FHG induced by a directed triangle will not converge for any initial partition except for the grand coalition. We can, however, characterize convergence on simple asymmetric FHGs. Tractability depends on the structure of the utilities. First, we consider dynamics
starting from the on simple asymmetric FHGs.

The key insight is that throughout the dynamic process on a simple asymmetric FHG starting from the , the subgraphs induced by coalitions are always transitive and complete.[We identify the directed graphs $G = (V,A)$ with relations $R$ where $i\mathrel{R}j$ if and only if $(i,j)\in A$. Hence, we call a directed graph $G = (V,A)$ transitive if $(i,j)\in A$ and $(j,k)\in A$ implies $(i,k)$ for every triple $i,j,k\in V$. We call it complete if $(i,j)\in A$ or $(j,i)\in A$ for every pair $i,j\in V$.] Convergence is then shown by a potential function argument.

The dynamics of IS deviations starting from the converges in simple asymmetric FHGs if and only if the underlying graph is acyclic. Moreover, under acyclicity, it converges in $\mathcal O(n^4)$ steps.

Let $G= (V,A)$ be a simple asymmetric graph on $n = |V|$ vertices.
If the graph contains a cycle, it is easy to find a non-converging series of deviations. There exists a cycle of length at least $3$. We can then let a coalition of size $2$ propagate along the cycle. More formally, assume that $\{c_1,\dots, c_j\}\subseteq V$ induce a directed cycle, where $(c_i,c_{i+1})\in A$ for $1\le i \le j$ (here and in the remainder of the proof, read indices modulo $j$ mapping to the representative in $[j]$). Define $(\partition_k)_{k\ge 0}$ by letting $\spartition$ be the , and for $p\ge 0$, $1\le i\le j$, let $\partition_{pj + i} = \{\{c_i,c_{i+1}\}\}\cup \{\{x\}\colon x\in V \setminus \{c_i,c_{i+1}\}\}$. Then, $(\partition_k)_{k\ge 0}$ is an IS dynamics of infinite length.

Assume that the graph is acyclic. Our first observation is that, in every step of the dynamics, all subgraphs induced by coalitions are transitive and complete. Indeed, by induction, in a deviation, the coalition that is left still induces a transitive and complete subgraph, and the new coalition induced a transitive and complete subgraph before the deviation.
Hence, every agent except one has at least one outgoing edge and will only accept the new agent if she likes her.
Since the deviating agent must have non-negative utility after the deviation, she needs to approve the single agent without outgoing edge.
Hence, the newly formed coalition still induces a transitive and complete subgraph.

The last argument also implies that the deviating agent has a utility of $1/k$ if she ends up in a coalition of size $k$ after her deviation. We refer to this fact as $(*)$ in the sequel.

We will now define two potentials based on the agents that receive $0$ utility in a partition, and based on the coalition sizes. The first potential is monotonically decreasing and bounded. The second potential is strictly increasing whenever the first potential is not strictly decreasing, and bounded. Hence, we establish convergence of the dynamics.

First, fix a topological order of the agents, i.e., a bijection $\sigma: V \to [n]$ such that for all $(v,w)\in A$, $\sigma(v) < \sigma(w)$.
For a given partition $\partition$ of the agents, we define the vector $v^\sigma(\partition)$ of length $|\partition|$ that sorts the numbers $\max_{i\in C}\sigma(i)$ for $C\in \partition$ in decreasing order, that is it sorts the coalitions in decreasing topological score of the agent with the highest number due to the topological order. This is exactly the unique agent in every coalition receiving $0$ utility.
In addition, we define the vector $w(\partition)$ of length $|\partition|$ that sorts the coalition sizes in increasing order. Note that this vector does not depend on the underlying topological order.

For two vectors $v = (v_i)_{i=1}^k$ and $w = (w_i)_{i=1}^l$, not necessarily of the same length, we say

\begin{align*}
v >_{lex} w \iff &\textnormal{there is } i < \max\{k,l\} \textnormal{ with }\\ & v_j = w_j \,\forall 1\le j\le i\textnormal{ and } v_{i+1}>w_{i+1},\textnormal{ or }\\
& k > l \textnormal{ and } v_j = w_j \,\forall 1\le j \le k\text.
\end{align*}

In other words, $v >_{lex} w$ if $v$ is lexicographically greater than $w$.

The key insight is that, for $\partition'$ formed from $\partition$ by an IS deviation, $v^\sigma(\partition') <_{lex} v^\sigma(\partition)$, or  $v^\sigma(\partition') =_{lex} v^\sigma(\partition)$ and  $w(\partition') >_{lex} w(\partition)$.
For a proof, assume that $\partition'$ is formed from $\partition$ by an IS deviation of agent $i$.
Note that $\max_{j\in \partition'(i)}\sigma(j) = \max_{j\in \partition'(i)\setminus \{i\}}\sigma(j) $. We distinguish two cases. Either $i = \arg\max_{j\in \partition(i)}\sigma(j)$ and it follows $v^\sigma(\partition') <_{lex} v^\sigma(\partition)$.
Otherwise, $\util_i(\partition(i))\ge \frac 1{|\partition(i)|}$, and because $i$ is improving her utility, $\frac 1{|\partition'(i)|} \overset{(*)}{=} \util_i(\partition') > \frac 1{|\partition(i)|}$. It follows that $|\partition(i)| > |\partition'(i)|$. Hence, $|\partition'(i)|-1 < \min\{|\partition'(i)|,|\partition(i)|\}$, and therefore $w(\partition') >_{lex} w(\partition)$.

We estimate the running time in two steps. First, we bound the number of times that the lexicographic score of  $v^\sigma(\partition)$ can decrease. Then, we estimate the number of deviations that can happen while this score does not change. We call the first kind of deviations primal and the second type secondary. Note that after an deviation, the maximal topological score in the joined coalition remains the same because the deviating agent has to like some agent who therefore has higher topological score. Hence, a primal deviation happens if and only if the agent with highest topological score of the abandoned coalition performs the deviation.

Let us first discuss the idea how to bound the number of the primal deviations. To this end, given a partition $\pi$ and an agent $v\in V$, we define a set $D^{\partition}_v$ that stores a certain amount of deviating agents. This set depends on the agent $v$ and the history of the dynamics until reaching $\pi$. In every step of the dynamics, the sum $\sum_{v\in V} |D^{\partition}_v|$ will be exactly the number of primal deviations so far. We ensure that we can always add the agent $v$ performing a deviation to a set $D^{\partition}_w$ such that $\sigma(v) > \sigma(x)$ for all $x\in D^{\partition}_w$. Hence, at the end of the sequence of deviations, $\sum_{v\in V} |D^{\partition}_v|\le n^2$.

Initially, set $D^{\spartition}_v = \emptyset$ for all $v\in V$ and the starting partition $\spartition$ of the dynamics. Assume first that agent $v$ performs a primary deviation that changes partition $\partition$ into partition $\partition'$. Recall that in this case, $v = \arg\max_{x\in \partition(v)} \sigma(x)$. If $v$ was in a singleton coalition, update $D^{\partition'}_v = \{v\}$ and leave all other sets the same, i.e., $D^{\partition'}_x = D^{\partition}_x$ for all $x\neq v$. Otherwise, let $w = \arg\max_{x\in \partition(v)\setminus \{v\}} \sigma(x)$ be the agent in $\partition(v)$ different from $v$ of highest topological score, i.e., the agent in $\partition(v)$ of second-highest topological score. We update $D^{\partition'}_v = D^{\partition}_w \cup \{v\}$, $D^{\partition'}_w = \emptyset$, and $D^{\partition'}_x = D^{\partition}_x$ for all $x\neq v,w$.
If a secondary deviation is performed from $\partition$ to $\partition'$, leave all sets the same, i.e., $D^{\partition'}_x = D^{\partition}_x$ for all $x\in V$.

Given a set of agents $W\subseteq V$, let $m_W = \arg\max_{x\in W} \sigma(x)$ be the agent in $W$ maximizing the topological score. We have the following invariants for every partition $\partition$ during the dynamics and for every agent $v\in V$:

* If $v = m_{\partition(v)}$, then $D^{\partition}_v = \emptyset$.

* If $v \neq m_{\partition(v)}$, then $\sigma(x) \le \sigma(v) < \sigma(m_{\partition(v)})$ for all $x\in D^{\partition}_v$.

* The number of primal deviations of the dynamics until partition $\partition$ is $\sum_{v\in V} |D^{\partition}_v|$.

The first invariant follows directly from the update rules. Indeed, the agent in the newly formed coalition of maximal topological score is the same, and if the agent of highest topological score in the abandoned coalition changes, then we update her set to be the empty set. This proves the first invariant.

The second invariant follows by induction. Assume that $v$ performs a deviation from $\partition$ to $\partition'$. If $v$ performs a primary deviation and $w = \arg\max_{x\in \partition(v)\setminus \{v\}} \sigma(x)$, then $D^{\partition'}_v\setminus\{v\} = D^{\partition}_w$, and therefore $\sigma(x) \le \sigma(w) < \sigma(m_{\partition(w)}) = \sigma(v) < \sigma(m_{\partition'(v)})$ for all $D^{\partition'}_v\setminus\{v\}$ where we apply induction for $w$ and the fact that the agent in $\partition'(v)$ which gives positive utility to $v$ has a higher topological score than $v$. If $v$ performs a secondary deviation, then for all $x\in D^{\partition'}_v$, $\sigma(x)\le \sigma(v) < \sigma(m_{\partition'(v)})$, where the first inequality follows by induction for $v$.

The third invariant follows from the update rules because the agent newly added to a set has not been in this set due to the second invariant.
The third invariant implies that there can be at most $n^2$ primal deviations, because for the terminal partition $\partition^*$ of the dynamics, $\sum_{v\in V} |D^{\partition^*}_v| \le n^2$.

While the topological score is the same, there can be at most $n^2$ secondary deviations, which follows from the same reasoning as in the proof of Proposition <ref>. Hence, together there are at most $n^4$ deviations.

In the previous proposition, it seems that there is still space for improvement of the bound on the running time, in particular due to the interplay of the two nested potentials.

The previous statement shows convergence of the dynamics for simple asymmetric, acyclic FHGs. In addition, it is easy to see that there is always a sequence converging after $n$ steps, starting with the .
More precisely, one can use a topological order of the agents and allow agents to deviate in decreasing topological order.
It can be observed that only coalitions of at most size two would form and that no agent would deviate from her current non-singleton coalition.
The idea is that when an agent $i$ wants to join a coalition of at least two agents, there must exist an agent $j$ in this coalition, with a greater index in the topological order and non-null current utility, therefore agent $j$ does not want agent $i$ to join.

There are two interesting further directions. One can weaken either the restriction on the initial partition or on asymmetry. If we allow for general initial partitions, we immediately obtain hardness results for simple asymmetric FHGs which are in particular a subclass of simple FHGs.

ISFHG is -hard and ISFHG is -hard, even in simple asymmetric FHGs.

On the other hand, if we transition to simple FHGs while starting the dynamics from the , the problem of deciding whether a path to stability exists becomes hard. We leave the complexity of ISFHG for simple FHG as an open problem.

ISFHG is -hard even in simple FHGs when starting from the .

§ DICHOTOMOUS HEDONIC GAMES

By taking into account the identity of other agents in the preferences of agents over coalitions, it can be more complicated to get positive results regarding individual stability (see, e.g., Theorem <ref>).
However, by restricting the evaluation of coalitions to dichotomous preferences, the existence of an IS partition is guaranteed <cit.>, as well as convergence of the dynamics of IS deviations, when starting from the grand coalition <cit.>.
Nevertheless, the convergence of the dynamics is not guaranteed for an arbitrary initial partition and no sequence of IS deviations may ever reach an IS partition.

The dynamics of IS deviations may never reach an
IS partition in
DHGs, whatever the chosen path of deviations, even when starting from the .

Let us consider an instance of a DHG
with three agents.
Their preferences are described in the table below.

Agent     1     2     3

Approvals     $\{1,2\}$     $\{2,3\}$     $\{1,3\}$

Disapprovals     $\{1\},\{1,3\},\{1,2,3\}$     $\{2\},\{1,2\},\{1,2,3\}$     $\{3\},\{2,3\},\{1,2,3\}$

There is a unique IS partition which consists of the grand coalition $\{1,2,3\}$.
We represent below all possible IS deviations between all the other possible partitions.
An IS deviation between two partitions is indicated by an arrow mentioning the name of the deviating agent.

(1) at (0,0) $\{\{1\},\{2\},\{3\}\}$;
(2) at ($(1)+(4.5,0)$) $\{\{1,2\},\{3\}\}$;
(3) at ($(2)+(2.5,2)$) $\{\{1\},\{2,3\}\}$;
(4) at ($(2)+(2.5,-2)$) $\{\{1,3\},\{2\}\}$;
[arrow] (1) –node[pos=0.6,above]$1$ (2); [arrow] (2) –node[pos=0.35,above]$2$  (3); [arrow] (3) –node[midway,right]$3$  (4); [arrow] (4) –node[pos=0.65,below]$1$  (2);
[arrow] (1) –node[midway,above]$2$  (3); [arrow] (1) –node[midway,below]$3$  (4);

One can check that the described deviations are IS deviations.
A cycle is necessarily reached when starting from a partition different from the unique IS partition, which can be reached only if it is the initial partition.

Moreover, it is hard to decide on the existence of a sequence of IS deviations ending in an IS partition, even when starting from the , as well as checking convergence.

ISDHG is -hard even when starting from the , and ISDHG is -hard.

Note that the counterexample provided in the proof of Proposition <ref> exhibits a global cycle in the preferences of the agents: $\{1,2\}\succ_1 \{1,3\} \succ_3 \{2,3\} \succ_2 \{1,2\}$.
However, by considering dichotomous preferences with common ranking property, that is, each agent has a threshold for acceptance in a given global order of coalitions, we obtain convergence thanks to the same potential function argument used by <cit.>, for proving the existence of a core-stable partition in hedonic games with common ranking property.

Also note that when assuming that if a coalition is approved by one agent, then it must be approved by all the members of the coalition (so-called symmetric dichotomous preferences), we obtain a special case of preferences with common ranking property where all the approved coalitions are at the top of the global order.
Therefore, convergence is also guaranteed under symmetric dichotomous preferences.

§ CONCLUSION

We have investigated dynamics of deviations based on individual stability in hedonic games. The two main questions we considered were whether there exists some sequence of deviations terminating in an IS partition, and whether all sequences of deviations terminate in an IS partition, i.e., the dynamics converges.
Many of our results are negative, that is, examples of cycles in dynamics or even non-existence of IS partitions under strong preference restrictions.
In particular, we have answered a number of open problems proposed in the literature leading to boundaries of dynamics. For all hedonic games under study, it turned out that the existence of cycles for IS deviations is sufficient to prove the hardness of recognizing instances for which there exists a finite sequence of deviations or whether all sequences of deviations are finite, i.e., the dynamics converges.
On the other hand, we have identified natural conditions for convergence that are based on $i)$ initial conditions, that is, the starting partition, $ii)$ selection rules for the performed deviation, and $iii)$ preference restrictions such as a common scale for the agents (e.g., the common ranking property), single-peakedness, or symmetry.

An overview of our results can be found in Table <ref>. While our hardness results show boundaries for both the possible and guaranteed convergence of dynamics, our positive results mostly focus on guaranteed convergence. In particular, we have made sophisticated use of potential functions to show the polynomial running time of the dynamics for anonymous hedonic games and hedonic diversity games with restrictions at the boundary of convergence. Our convergence result for HDGs features are rare case in the literature, presenting a highly non-trivial reduction to AHGs and therefore revealing a deep relationship of these two classes under natural single-peakedness.

Convergence and hardness results for the dynamics of IS deviations in various classes of hedonic games. Symbol $\checkmark$ marks guaranteed convergence under the given preference restrictions and initial partition (if applicable)
while $\circ$ marks non-convergence, i.e., cycling dynamics. For all of our positive results except Theorem <ref>, we can even show that the dynamics necessarily terminate after a polynomial number of steps. Symbol $\exists$ (or $\forall$) denotes that problem ISHG (or ISHG) is -hard (or -hard).

Class     Guaranteed convergence     Hardness

AHGs       natural SP (single-peaked) (Theorem <ref>)   neutral (<cit.>)   strict & general SP; singletons / grand coalition (Proposition <ref>)
strict (Theorem <ref>)   strict (Theorem <ref>)

HDGs       strict & natural SP; singletons; solitary homogeneity (Theorem <ref>)   [c]any three of: strict, natural SP, singletons, any three of: strict, natural SP, singletons, and solitary homogeneity (Theorem <ref>)
strict (Theorem <ref>)   strict (Theorem <ref>)

FHGs       simple & sym.; singletons (Proposition <ref>)   acyclic digraph (Theorem <ref>)   symmetric (Theorem <ref>)
symmetric (Theorem <ref>)  simple; singletons (Theorem <ref>)  simple asym. (Theorem <ref>)  symmetric (Theorem <ref>)   simple asym. (Theorem <ref>)

DHGs       grand coalition (<cit.>)   common ranking property or symmetric (<cit.>)  singletons (Proposition <ref>)
singletons (Theorem <ref>)   general (Theorem <ref>)

An important message of our results is that the consideration of dynamics can offer important novel insights regarding the reachability of stable states, even if the static picture drawn by asking for the mere existence of stability seems clear.
For instance, FHGs with non-negative utilities and HDGs always contain stable states, while it is hard to decide if we can reach a stable state from some initial partition, even under severe restrictions. On the other hand, dynamics always converge in naturally single-peaked AGHs, which is in accordance with the existence of stable partitions observed by <cit.>. In other words, the existence and the distributed attainability of stable states do not necessarily coincide.

While our results cover a broad range of hedonic games considered in the literature, there are still promising directions for further research.
First, even though our hardness results hold under strong restrictions,
the complexity of these questions remains open for some interesting preference restrictions, some of which do not guarantee convergence. Following our work, the most intriguing case for guaranteed convergence are simple symmetric FHGs with arbitrary initial partitions.
On the other hand, our computational hardness of simple FHGs only covers the ISFHG while we leave the complexity of ISFHG open. We conjecture that this problem is hard as well.

Since our positive results mainly concern guaranteed convergence, there are also interesting open problems concerning the existence of a path to stability. In general, there is hope that less of the restrictions necessary for guaranteed convergence suffice for a path to stability. This especially concerns HDGs. Since solitary homogeneity is just a selection rule among possible deviations, Theorem <ref> implies that there always exists a path to stability from the in HDGs where agents have strict and single-peaked preferences. On the other hand, Proposition <ref>, our result about conditions under which cycling can necessarily occur leaves space for possibilities. Two intriguing questions are whether there always exists a path to stability in HDGs where agents' preferences are strict and single-peaked, or when the dynamics start with the .

Possible convergence of the dynamics is closely related to the investigation of specific selection rules for the performed deviations. With the exception of Theorem <ref>, we do not have to pose any assumptions on the performed deviations to obtain our results for guaranteed convergence. However, apart from possible convergence, selecting appropriate deviations may also lead to a fast termination of the dynamics in IS partitions, even in classes of hedonic games that allow for cyclic IS deviations.
For instance, for simple symmetric FHGs, there is the possibility of convergence such that each agent deviates at most once, but the selection of the deviating agents in this approach requires to solve a maximum clique problem (cf. the discussion after Proposition <ref>).

An open problem concerning the convergence speed of dynamics is to bound the number of steps until convergence in AHGs under weak and single-peaked preferences. Note that considering fastest instead of fast convergence is a problem that is likely to lead to further intractabilities. In this respect, <cit.> provide first results by proving hardness of finding the shortest path to stability for several dynamics in additively separable hedonic games.

In principal, one can define dynamics also based on other stability concepts like Nash stability or contractual individual stability. For the latter, cycling is not possible, and therefore an analysis within the complexity class as local search algorithms is a natural approach that measures the complexity of convergence. Such an analysis is also appropriate for dynamics guaranteed to converge based on a potential function argument as it was already done for Nash stability in additively separable hedonic games <cit.>.

Finally, the final states reached in the dynamics we consider do not provide information beyond individual stability. One could therefore additionally aim to reach efficient outcomes, potentially measured amongst stable outcomes. The notion of Pareto optimality seems natural here because it gives also rise to a natural improvement dynamics. Indeed, <cit.> consider this problem for naturally single-peaked AHGs where their algorithm constructs an IS partition that is weakly Pareto-optimal.

This work was supported by the Deutsche Forschungsgemeinschaft under grant BR 2312/12-1. We would like to thank Abheek Ghosh for sharing insights on how to extend our convergence result for AHGs to weak preferences.
We also thank Leo Tappe and the anonymous reviewers from AAAI and TEAC for helpful discussions. We were impressed by the depth of the reviews from TEAC.
A preliminary version of this article appeared in the Proceedings of the 35th AAAI Conference on Artificial Intelligence (February, 2021).
Results from this article were presented at the 3rd Games, Agents, and Incentives Workshop (May, 2021) and the 15th Journées d'Intelligence Artificielle Fondamentale (July, 2021).

#1     #1#1#1     #1     #1     #1     #1#1          #1#1

[Abeledo and Rothblum(1995)]
authorpersonH. Abeledo and personU. G.
Rothblum. year1995.
Paths to marriage stability.
journalDiscrete Applied Mathematics
volume63, number1 (year1995),
[Aziz et al(2019)]
authorpersonH. Aziz, personF. Brandl,
personF. Brandt, personP. Harrenstein,
personM. Olsen, and personD. Peters.
Fractional Hedonic Games.
journalACM Transactions on Economics and
Computation volume7, number2
(year2019), pages1–29.
[Aziz et al(2016)]
authorpersonH. Aziz, personP. Harrenstein,
personJ. Lang, and personM. Wooldridge.
Boolean Hedonic Games. In
booktitleProceedings of the 15th International Conference on
Principles of Knowledge Representation and Reasoning (KR).
[Aziz and Savani(2016)]
authorpersonH. Aziz and personR. Savani.
Hedonic Games.
In booktitleHandbook of Computational Social
Choice, editorpersonF. Brandt,
personV. Conitzer, personU. Endriss,
personJ. Lang, and personA. D. Procaccia (Eds.).
publisherCambridge University Press, Chapter 15.
authorpersonC. Ballester.
NP-completeness in hedonic games.
journalGames and Economic Behavior
volume49, number1 (year2004),
[Berman et al(2003)]
authorpersonP. Berman, personM. Karpinski,
and personA. Scott. year2003.
booktitleApproximation hardness of short symmetric
instances of MAX-3SAT.
typeTechnical Report TR03-049.
institutionElectronic Colloquium on Computational Complexity
[Bilò et al(2018)]
authorpersonV. Bilò, personA. Fanelli,
personM. Flammini, personG. Monaco, and
personL. Moscardelli. year2018.
Nash Stable Outcomes in Fractional Hedonic Games:
Existence, Efficiency and Computation.
journalJournal of Artificial Intelligence Research
volume62 (year2018), pages315–371.
authorpersonD. Black. year1948.
On the Rationale of Group Decision-making.
journalJournal of Political Economy
volume56, number1 (year1948),
[Boehmer et al(2022)]
authorpersonN. Boehmer, personM. Bullinger,
and personA. M. Kerkmann. year2022.
Causes of Stability in Dynamic Coalition
Working paper.

[Boehmer and Elkind(2020)]
authorpersonN. Boehmer and personE.
Elkind. year2020.
Individual-Based Stability in Hedonic Diversity
Games. In booktitleProceedings of the 34th AAAI Conference
on Artificial Intelligence (AAAI). pages1822–1829.
[Bogomolnaia and Jackson(2002)]
authorpersonA. Bogomolnaia and personM. O.
Jackson. year2002.
The Stability of Hedonic Coalition Structures.
journalGames and Economic Behavior
volume38, number2 (year2002),
[Brandl et al(2015)]
authorpersonF. Brandl, personF. Brandt,
and personM. Strobel. year2015.
Fractional Hedonic Games: Individual and Group
Stability. In booktitleProceedings of the 14th
International Conference on Autonomous Agents and Multiagent Systems
(AAMAS). pages1219–1227.
[Brandt et al(2022)]
authorpersonF. Brandt, personM. Bullinger,
and personL. Tappe. year2022.
Single-Agent Dynamics in Additively Separable
Hedonic Games. In booktitleProceedings of the 36th AAAI
Conference on Artificial Intelligence (AAAI). pages4867–4874.
[Brandt et al(2021)]
authorpersonF. Brandt, personM. Bullinger,
and personA. Wilczynski. year2021.
Reaching Individually Stable Coalition Structures
in Hedonic Games. In booktitleProceedings of the 35th AAAI
Conference on Artificial Intelligence (AAAI). pages5211–5218.
[Brandt and Wilczynski(2019)]
authorpersonF. Brandt and personA.
Wilczynski. year2019.
On the Convergence of Swap Dynamics to
Pareto-Optimal Matchings. In booktitleProceedings of the
15th International Conference on Web and Internet Economics (WINE)
(seriesLecture Notes in Computer Science (LNCS)).
publisherSpringer-Verlag, pages100–113.
[Bredereck et al(2019)]
authorpersonR. Bredereck, personE. Elkind,
and personA. Igarashi. year2019.
Hedonic Diversity Games. In
booktitleProceedings of the 18th International Conference on
Autonomous Agents and Multiagent Systems (AAMAS).
[Carosi et al(2019)]
authorpersonR. Carosi, personG. Monaco,
and personL. Moscardelli. year2019.
Local Core Stability in Simple Symmetric Fractional
Hedonic Games. In booktitleProceedings of the 18th
International Conference on Autonomous Agents and Multiagent Systems
(AAMAS). pages574–582.
[Caskurlu and Kizilkaya(2019)]
authorpersonB. Caskurlu and personF. E.
Kizilkaya. year2019.
On Hedonic Games with Common Ranking Property. In
booktitleProceedings of the 11th International Conference on
Algorithms and Complexity (CIAC). publisherSpringer
International Publishing, pages137–148.
[Drèze and Greenberg(1980)]
authorpersonJ. H. Drèze and personJ.
Greenberg. year1980.
Hedonic Coalitions: Optimality and Stability.
journalEconometrica volume48,
number4 (year1980), pages987–1003.
[Fanelli et al(2021)]
authorpersonA. Fanelli, personG. Monaco,
and personL. Moscardelli. year2021.
Relaxed core stability in fractional hedonic
games. In booktitleProceedings of the 30th International
Joint Conference on Artificial Intelligence (IJCAI).
[Farrell and Scotchmer(1988)]
authorpersonJ. Farrell and personS.
Scotchmer. year1988.
journalQuarterly Journal of Economics
volume103 (year1988), pages279–297.
[Gairing and Savani(2019)]
authorpersonM. Gairing and personR.
Savani. year2019.
Computing Stable Outcomes in Symmetric Additively
Separable Hedonic Games.
journalMathematics of Operations Research
volume44, number3 (year2019),
[Hoefer et al(2018)]
authorpersonM. Hoefer, personD. Vaz, and
personL. Wagner. year2018.
Dynamics in matching and coalition formation games
with structural constraints.
journalArtificial Intelligence
volume262 (year2018), pages222–247.
authorpersonR. M. Karp.
Reducibility among Combinatorial Problems.
In booktitleComplexity of Computer Computations,
editorpersonR. E. Miller and personJ. W.
Thatcher (Eds.). publisherPlenum Press,
authorpersonD. Peters.
Complexity of Hedonic Games with Dichotomous
Preferences. In booktitleProceedings of the 30th AAAI
Conference on Artificial Intelligence (AAAI). pages579–585.
[Roth and Vande Vate(1990)]
authorpersonA. E. Roth and personJ. H.
Vande Vate. year1990.
Random Paths to Stability in Two-Sided Matching.
journalEconometrica volume58,
number6 (year1990), pages1475–1480.
authorpersonW. Suksompong.
Individual and Group Stability in Neutral
Restrictions of Hedonic Games.
journalMathematical Social Sciences
volume78 (year2015), pages1–5.
[Sung and Dimitrov(2010)]
authorpersonS. C. Sung and personD.
Dimitrov. year2010.
Computational Complexity in Additive Hedonic
journalEuropean Journal of Operational Research
volume203, number3 (year2010),

§ APPENDIX: OMITTED PROOFS

In the appendix, we provide the proofs omitted in the main part of the paper.

§ ANONYMOUS HEDONIC GAMES

The proof consists of the following two lemmas.
We first prove that an IS partition may not exist even when there are only 15 agents, and then we show that there are no smaller counterexamples.

There may not exist an IS partition in anonymous games even when there are 15 agents and the agents have strict and generally single-peaked preferences.

An instance of an anonymous hedonic game with no IS partition has at least 15 agents.

In an instance with no IS partition, there must be a cycle of IS deviations.
We will construct a minimal instance where a cycle is necessary with only two deviating agents $1$ and $2$ in the cycle (we know that it is possible by <Ref>).
Since the agents have transitive preferences and we impose that the joined agents are better off, the deviating agents must alternate between at least three coalitions, $C_1$, $C_2$ and $C_3$, in order to form a cycle.
Note that this is the same number of minimal fixed coalitions necessary for having a cycle with three deviating agents; since the construction is similar, we cannot have a smaller instance with a number of deviating agents larger than two.

Let us denote by $p$, $q$ and $r$ the sizes of the three coalitions $C_1$, $C_2$ and $C_3$, respectively, without agents $1$ and $2$.
In order to let the agents come back to their initial coalition, each deviating agent $i$ must be “left” by the other deviating agent $j$ at some step of the cycle, i.e., they both belong to the same coalition and agent $j$ leaves the coalition and, in such a way, decreases the satisfaction of agent $i$.
It means that the agent $j$ who leaves the coalition was entered into this coalition before agent $i$ (otherwise the combination of these moves would be equivalent to the one where agent $j$ directly goes to the next coalition).
It follows that the preferences of the agents, that are necessary for the cycle to occur, can be described, without loss of generality, by  $1:~p+2 \succ q+1 \succ r+2 \succsim r+1 \succ p+1$ and $2:~r+2 \succ q+1 \succ p+2 \succsim p+1 \succ r+1$.
The idea is that agent $1$ can join coalition $C_3$ from coalition $C_1$, then being joined in $C_3$ by agent $2$ who leaves coalition $C_2$, then agent $1$ goes to coalition $C_2$ whereas agent $2$ goes to coalition $C_1$ then joined by agent $1$, and finally agent $2$ comes back to coalition $C_2$, creating the cycle.
In order to consider a relevant necessary cycle, we assume, without loss of generality, that these preferences are at the top of the preference ranking of the deviating agents.
To enable the deviations, the agents in $C_1$ of size $p$ must have the following preferences: $p+2 \succsim p+1 \succsim p$, those in $C_2$ of size $q$ the following: $q+1 \succsim q$, and those in $C_3$ of size $r$ the following: $r+2 \succsim r+1 \succsim r$.

It suffices then to find appropriate values for $p$, $q$ and $r$.
For the preferences to hold, we must have that $p+1 \neq p+2 \neq q+1 \neq r+1 \neq r+2$ $(a)$.
Observe that the behavior of coalitions $C_1$ and $C_3$ in this cycle is symmetric, therefore it would be equivalent to reverse the values of $p$ and $r$.
We have consequently three cases: $(i)~p<q<r$, $(ii)~p<r<q$, and $(iii)~q<p<r$.
For the two first cases $(i)$ and $(ii)$, at the minimum, $p$ can be equal to 0.
Then, by $(a)$, $q$ can be equal at the minimum to 2 and $r$ to 3 in case $(i)$, since there is no $q+2$ in the preferences of the deviating agents, whereas $r$ can be equal at the minimum to 2 and $q$ to 4 in case $(ii)$.
For the rest, we need the same mechanisms of additions of agents in order to force coalitions $C_2$ and $C_3$ to be together.
Therefore, a minimal counterexample under $(ii)$ is at least as large as a minimal counterexample under $(i)$.
Now, by considering case $(iii)$, we cannot have $q=0$, otherwise the preferences of the two deviating agents would be $1:~p+2\succ 1 \succ [\dots]$ and $2:~r+2\succ 1\succ [\dots]$ and then we could easily find IS partitions where $1$ and $2$ are alone.
Therefore, by $(a)$, we get that in case $(iii)$, $q$ can be equal at the minimum to 1, $p$ to 2 and $r$ to 4 whereas in case $(i)$, $p$ can be equal at the minimum to 0, $q$ to 2 and $r$ to 3.
For the rest, we need similar mechanisms of additions of agents in order to force coalitions $C_2$ and $C_3$ to be together, as well as coalition $C_1$ for case $(iii)$.
Therefore, a minimal counterexample under $(iii)$ is at least as large as a minimal counterexample under $(i)$.
Hence, a minimal counterexample would be such that $(i)~p<q<r$.

Then, at the minimum, we have $p=0$ and $q=2$.
Recall that we have the preferences $C_2:~q+1 \succsim q$, and $C_3:~r+2 \succsim r+1 \succsim r$.
Now the idea is ensure that coalitions $C_2$ and $C_3$ will form.
Since $q<r$, we just need to care that agents in $C_3$ will always deviate to be all together and not mixed with agents in $C_2$.
Therefore, there is no need to add more agents than 2 in $C_2$ (the more they are the more they may mix with agents in $C_3$) and we can set the preferences of $C_2$ to $3 \succsim 2 \succsim 1 \succsim [\dots]$ to be sure that they will not belong to a coalition larger than 3.
Now, we should ensure that agents in $C_3$ will form a coalition, i.e., if there are some agents of $C_3$ grouped with agents of $C_2$, they should have an incentive to leave this coalition in order to join other agents of $C_3$.
For that, they should prefer to be in larger coalitions, i.e., we have $C_3:~r+2 \succ r+1 \succ r \succ \dots\succ 1$.
Moreover, there must be enough agents of $C_3$ in total to create an incentive for agents of $C_3$ in coalitions with other agents to join the rest of $C_3$ agents even if they are currently blocked in coalitions with other agents.
More precisely, at most 2 agents of $C_3$ can be blocked in a coalition with an agent of $C_2$ and at most 2 agents can be blocked with agent $1$ or agent $2$ (recall that size 3 is the second most preferred size of both agents $1$ and $2$).
Therefore, in addition of these “blocked” $C_3$ agents, we need to add three other agents in $C_3$ in order to create the incentive of blocked agents of $C_3$ to join them (they are all blocked in coalitions of size at most 3).
Thus, in total we need at least 11 agents in $C_3$.
Indeed, if we have less than this number, by grouping them with agents $1$, $2$ or agents of $C_2$ and the rest together, we get an IS partition.
Hence, by also taking into account deviating agents $1$ and $2$ and coalition $C_2$ of minimum size 2, we need at least 15 agents in total to have no IS partition.
Polish more the proof of minimality.

We prove the two hardness results by providing separate reductions for each problem in the next two lemmas.

ISAHG is -hard even for strict preferences.

Let us perform a reduction from (3,B2)-SAT, a variant of the Satisfiability problem known to be -complete <cit.>.
In an instance of (3,B2)-SAT, we are given a CNF propositional formula $\varphi$ where every clause $C_j$, for $1\leq  j \leq m$, contains exactly three literals and every variable $x_i$, for $1\leq i \leq p$, appears exactly twice as a positive literal and twice as a negative literal.
From such an instance, we construct an instance of an anonymous game with initial partition as follows.

For each $\ell^{\text{th}}$ occurrence ($\ell\in\{1,2\}$) of a positive literal $x_i$ (or negative literal $\overline{x}_i$), we create a literal-agent $y_i^\ell$ (or $\overline{y}_i^\ell$).
All literal-agents are singletons in the initial partition $\spartition$.
Let us consider four integers $\alpha$, $\beta^+$, $\beta^-$ and $\gamma$ such that $(1)$ $q\cdot\alpha +x \neq r\cdot \beta^+ + y \neq s\cdot \beta^- + z \neq t \gamma + w$ for every $r,s,t\in [p]$, $q\in [m]$, $x,y,z\in\{0,1,2\}$ and $w\in [7]$ and, without loss of generality, $\alpha>\beta^+>\beta^->\gamma>1$.
For instance, we can set the following values: $\alpha=m^5$, $\beta^+=m^4$, $\beta^-=m^3$ and $\gamma=m^2$ (condition $(1)$ is satisfied since in a (3,B2)-SAT instance, it holds that $m\geq 4$ and $p=3/4 m$).
For each clause $C_j$, we create $j\alpha$ dummy clause-agents who are all grouped within the same coalition $K_j$ in the initial partition $\spartition$.
For each literal $x_i$ (or $\overline{x}_i$), we create one variable-agent $z_i$ (or $\overline{z}_i$) and $i \beta^+-1$ (or $i\beta^- -1$) dummy variable agents who are all grouped within the same coalition $Z_i$ (or $\overline{Z_i}$) in the initial partition $\spartition$.
Finally, for each variable $x_i$, we create $i\gamma$ dummy agents who are all grouped within the same coalition $G_i^1$ in the initial partition $\spartition$, $i\gamma+3$ dummy agents who are all grouped within the same coalition $G_i^2$ in the initial partition $\spartition$ and $i\gamma+5$ dummy agents who are all grouped within the same coalition $G_i^3$ in the initial partition $\spartition$.
These dummy agents are used as a gadget for a cycle.
Although we have created many agents, the construction remains polynomial by considering reasonable values of $\alpha$, $\beta^+$, $\beta^-$ and $\gamma$, as previously described.

The preferences of the agents over sizes of coalitions are given in Table <ref>.
By the design of the preferences of the members of the initial coalitions in $\spartition$, i.e., the members of the initial non-singleton coalitions accept at most two additional agents in their coalition and otherwise are happy with their coalition, and by condition (1), all the sizes of non-singleton coalitions explicitly given in the preferences can be reached only in one way, which is the one described in the preferences, i.e., by the addition of at most two agents in a specific initial non-singleton coalition.
It follows that the preferences of the agents can be expressed in terms of preferences for joining, or that one or two agents join, a specific non-singleton coalition from the initial partition $\spartition$.

Preferences of the agents in the reduced instance of Lemma <ref>, for every $1\leq i\leq p$, $1\leq j\leq m$, $\ell\in\{1,2\}$. Notation $\clauseof{x_i^\ell}$ (or $\clauseof{\overline{x}_i^\ell}$) stands for the index of the clause to which the $\ell^{\text{th}}$ occurrence of literal $x_i$ (or $\overline{x}_i$) belongs, the framed value is the size of the initial coalition in partition $\spartition$, and $[\dots]$ denotes an arbitrary order over the rest of the coalition sizes.

$z_i:$     $|Z_i|+2 \succ |G_i^1|+2 \succ |G_i^2|+1 \succ |G_i^3|+2 \succ |G_i^3|+1 \succ |G_i^1|+1 \succ |Z_i|+1 \succ \boxed{|Z_i|} \succ [\dots]$

$\overline{z}_i:$     $|\overline{Z_i}|+2 \succ |G_i^3|+2 \succ |G_i^2|+1 \succ |G_i^1|+2 \succ |G_i^1|+1 \succ |G_i^3|+1 \succ |\overline{Z_i}|+1 \succ \boxed{|\overline{Z_i}|} \succ [\dots]$

$y_i^\ell:$     $|K_{\clauseof{x_i^\ell}}|+1 \succ |Z_i|+2 \succ |Z_i|+1 \succ \boxed{1} \succ [\dots]$

$\overline{y}_i^\ell:$     $|K_{\clauseof{\overline{x}_i^\ell}}|+1 \succ |\overline{Z_i}|+2 \succ |\overline{Z_i}|+1 \succ \boxed{1} \succ [\dots]$

$K_j:$     $|K_j|+1 \succ \boxed{|K_j|} \succ [\dots]$

$Z_i\setminus\{z_i\}:$     $|Z_i|+2 \succ |Z_i|+1 \succ \boxed{|Z_i|} \succ |Z_i|-1 \succ [\dots]$

$\overline{Z_i}\setminus\{\overline{z}_i\}:$     $|\overline{Z_i}|+2 \succ |\overline{Z_i}|+1 \succ \boxed{|\overline{Z_i}|} \succ |\overline{Z_i}|-1 \succ [\dots]$

$G_i^1:$     $|G_i^1|+2 \succ |G_i^1|+1 \succ \boxed{|G_i^1|} \succ [\dots]$

$G_i^2:$     $|G_i^2|+1 \succ \boxed{|G_i^2|} \succ [\dots]$

$G_i^3:$     $|G_i^3|+2 \succ |G_i^3|+1 \succ \boxed{|G_i^3|} \succ [\dots]$

We claim that there exists a sequence of IS deviations which leads to an IS partition iff formula $\varphi$ is satisfiable.

Suppose first that there exists a truth assignment of the variables $\phi$ that satisfies all the clauses.
Let us denote by $\ell_j$ a chosen literal-agent associated with an occurrence of a literal true in $\phi$ which belongs to clause $C_j$.
Since all the clauses of $\varphi$ are satisfied by $\phi$, there exists such a literal-agent $\ell_j$ for each clause $C_j$.
For every clause $C_j$, let literal-agent $\ell_j$ join coalition $K_j$.
These IS deviations make all the dummy clause-agents and the chosen literal-agents the most happy as possible, therefore none of them will deviate afterwards or let other agents enter their coalition.
Then, let all remaining literal-agents $y_i^\ell$ (or $\overline{y}_i^\ell$) deviate by joining coalition $Z_i$ (or $\overline{Z_i}$).
Since $\phi$ is a truth assignment of the variables, for each variable $x_i$, the two literal-agents corresponding to the literal of variable $x_i$ that is false in $\phi$ both deviate in this second round of deviations.
Therefore, there exists a coalition $Z_i$ or $\overline{Z_i}$ that is joined by two literal-agents and thus whose members all reach their most preferred size $|Z_i|+2$ or $|\overline{Z_i}|+2$.
It follows that no member of such a newly formed coalition would move afterwards or let other agents enter the coalition: all members of $Z_i$ or $\overline{Z_i}$ get their most preferred size while the two joining literal-agents get their second most preferred size and their most preferred size is not accessible anymore (their associated clause coalition has already been joined by another literal-agent).
Consequently, for each variable $x_i$, at most one coalition between $Z_i$ and $\overline{Z_i}$ may not be joined by two literal-agents and, if there is one, it must be the coalition that corresponds to the literal of variable $x_i$ that is true in $\phi$.
In such a case, we let the associated variable-agent $z_i$ or $\overline{z}_i$ deviate for joining coalition $G_i^2$, and if one literal-agent previously joined the corresponding variable-coalition, she deviates to be alone.
Such a literal-agent then gets her fourth most preferred size while her most preferred ones are not accessible anymore (because the variable-agent has left the coalition and her associated clause coalition has already been joined by another literal-agent).
Moreover, such a variable-agent $z_i$ or $\overline{z}_i$, by joining coalition $G_i^2$, gets her third most preferred size while her most preferred ones are not accessible (no two additional agents want to enter the initial coalition $Z_i$ or $\overline{Z_i}$ and only one additional agent, herself, is present in the gadget associated with variable $x_i$).
Also, note that, by the design of the preferences, no dummy agent in the gadget has an incentive to move to another coalition.
All in all, no agent can then move in an IS deviation, and thus the reached partition is IS.

Suppose now that there exists no truth assignment of the variables that satisfies all the clauses.
That means that it is not possible that each clause coalition is joined by a literal-agent associated with this clause
while two other literal-agents $y_i^1$ and $y_i^2$ join coalition $Z_i$ (or $\overline{y}_i^1$ and $\overline{y}_i^2$ join coalition $\overline{Z_i}$), for each variable $x_i$.
Moreover since, by design of the preferences, each literal-agent prefers to join clause coalitions than variable coalitions, it means that in a maximal sequence of IS deviations, all dummy clause-agents in each coalition $K_j$ will be completely satisfied with a coalition size equal to $|K_j|+1$ (if a clause coalition is not joined by a literal-agent, then a literal-agent associated with this clause has an incentive to join this coalition, no matter her current coalition).
It means that after a maximal sequence of IS deviations, each clause coalition is joined by a literal-agent associated with this clause.
Therefore, by the previous argument derived from the assumption that there exists no truth assignment of the variables that satisfies all the clauses,
there must exist a variable $x_i$ such that at most one literal-agent joins coalition $Z_i$ and at most one literal-agent joins coalition $\overline{Z_i}$.
It follows that both variable-agents $z_i$ and $\overline{z_i}$ have an incentive to deviate to the gadget associated with variable $x_i$ (their respective most preferred coalition sizes $|Z_i|+2$ and $|\overline{Z_i}|+2$ can never be reached, while they prefer to join some coalitions in the gadget than staying in their current coalition of size $|Z_i|$ or $|Z_i|+1$ for $z_i$, and $|\overline{Z_i}|$ or $|\overline{Z_i}|+1$ for $\overline{z}_i$).
Within the gadget associated with variable $x_i$, variable-agents $z_i$ and $\overline{z_i}$ are the only agents who can deviate and we necessarily reach the cycle illustrated in Figure <ref>.

(p1) at (-4.75,0) $\{G_i^1,G_i^2\cup\{\overline{z_i}\},G_i^3\cup \{z_i\}\}$;
(p2) at (0,0) $\{G_i^1,G_i^2,G_i^3\cup\{z_i,\overline{z_i}\}\}$;
(p3) at (4.75,0) $\{G_i^1,G_i^2\cup\{z_i\},G_i^3\cup\{\overline{z_i}\}\}$;
(p4) at (4.75,-2) $\{G_i^1\cup\{\overline{z_i}\},G_i^2\cup\{z_i\},G_i^3\}$;
(p5) at (0,-2) $\{G_i^1\cup\{z_i,\overline{z_i}\},G_i^2,G_i^3\}$;
(p6) at (-4.75,-2) $\{G_i^1\cup\{z_i\},G_i^2\cup\{\overline{z_i}\},G_i^3\}$;
(p7) at (-4.75,2) $\{G_i^1\cup\{z_i\},G_i^2,G_i^3\cup\{\overline{z_i}\}\}$;
(p8) at (-4.75,-4) $\{G_i^1\cup\{\overline{z}_i\},G_i^2,G_i^3\cup\{z_i\}\}$;
[arrow,very thick] (p1) – node[midway,above] $\overline{z}_i$  (p2);
[arrow,very thick] (p2) – node[midway,above] $z_i$  (p3);
[arrow,very thick] (p3) – node[midway,right] $\overline{z}_i$  (p4);
[arrow,very thick] (p4) – node[midway,above] $z_i$  (p5);
[arrow,very thick] (p5) – node[midway,above] $\overline{z}_i$  (p6);
[arrow,very thick] (p6) – node[midway,left] $z_i$  (p1);
[arrow] (p7) – node[midway,above] $z_i$  (p2);
[arrow] (p7) – node[midway,above] $z_i$  (p3);
[arrow,rounded corners] (p7.west) – ($(p7.west)+(-1.45,0)$) |- node[pos=0.66,below] $\overline{z}_i$ ($(p5.south)+(0,-0.5)$) – (p5.south);
[arrow] (p7) to[bend right=50] node[midway,left] $\overline{z}_i$  (p6.west);
[arrow] (p8) to[bend left=50] node[midway,left] $\overline{z}_i$  (p1.west);
[arrow,rounded corners] (p8.west) – ($(p8.west)+(-1.15,0)$) |- node[pos=0.65,above] $\overline{z}_i$ ($(p2.north)+(0,0.5)$) – (p2.north);
[arrow] (p8) – node[midway,below] $z_i$  (p4);
[arrow] (p8) – node[midway,below] $z_i$  (p5);

Necessary cycle of IS deviations within the gadget associated with variable $x_i$ in the reduced instance of Lemma <ref>.

It follows that no sequence of IS deviations can reach an IS partition.

ISAHG is -hard even for strict preferences.

For this purpose, we prove the -hardness of the complement problem, which asks whether there exists a cycle of IS deviations.
Let us perform a reduction from (3,B2)-SAT <cit.>.
In an instance of (3,B2)-SAT, we are given a CNF propositional formula $\varphi$ where every clause $C_j$, for $1\leq  j \leq m$, contains exactly three literals and every variable $x_i$, for $1\leq i \leq p$, appears exactly twice as a positive literal and twice as a negative literal.
From such an instance, we construct an instance of an anonymous game with initial partition as follows.

For each $\ell^{\text{th}}$ occurrence ($\ell\in\{1,2\}$) of a positive literal $x_i$ (or negative literal $\overline{x}_i$), we create a literal-agent $y_i^\ell$ (or $\overline{y}_i^\ell$).
We create another agent $t$.
All these agents are singletons in the initial partition $\spartition$.
Let us consider five integers $\alpha$, $\beta^+_1$, $\beta^-_1$, $\beta^+_2$ and $\beta^-_2$ such that $(1)$ $q\cdot\alpha +x \neq r\cdot \beta^+_1 + y \neq s\cdot \beta^-_1 + z\neq t\cdot \beta^+_2 +v\neq u\cdot\beta^-_2 +w$ for every $r,s,t,u\in [p]$, $q\in [m]$ and $x,y,z,v,w\in\{0,1,2\}$ and, without loss of generality, $\alpha>\beta^+_1>\beta^-_1>\beta^+_2>\beta^-_2>1$.
For instance, we can set the following values: $\alpha=m^5$, $\beta^+_1=m^4$, $\beta^-_1=m^3$, $\beta^+_2=m^2$, $\beta^-_2=m$ (condition $(1)$ is satisfied since in a (3,B2)-SAT instance, it holds that $m\geq 4$ and $p=3/4 m$).
For each clause $C_j$, we then create $j\cdot\alpha$ dummy clause agents grouped within the same coalition $K_j$ in the initial partition $\spartition$.
We also create $(m+1)\cdot\alpha$ dummy agents grouped within the same coalition $K_{m+1}$ in initial partition $\spartition$.
Finally, for each literal $x_i$ (or $\overline{x}_i$) and each $\ell\in\{1,2\}$, we create $i \cdot \beta^+_\ell$ (or $i \cdot \beta^-_\ell$) dummy variable agents grouped within the same coalition $Y_i^\ell$ (or $\overline{Y_i^\ell}$) in the initial partition $\spartition$.
Although we have created many agents, the construction remains polynomial by considering reasonable values of $\alpha$, $\beta^+_1$, $\beta^-_1$, $\beta^+_2$ and $\beta^-_2$, as previously described.

The preferences of the agents over sizes of coalitions are given in Table <ref>.
By the design of the preferences of the members of the initial coalitions in $\spartition$, i.e., the members of the initial non-singleton coalitions accept at most two additional agents in their coalition and otherwise are happy with their coalition, and by condition (1), all the sizes of non-singleton coalitions explicitly given in the preferences can be reached only in one way, which is the one described in the preferences, i.e., by the addition of at most two agents in a specific initial non-singleton coalition.
It follows that the preferences of the agents can be expressed in terms of preferences for joining, or that one or two agents join, a specific non-singleton coalition from the initial partition $\spartition$.

Preferences of the agents in the reduced instance of Lemma <ref>, for every $1\leq i\leq p$, $1\leq i' < p$, $1\leq j\leq m+1$, $\ell\in\{1,2\}$. Notation $\clauseof{x_i^\ell}$ (or $\clauseof{\overline{x}_i^\ell}$) stands for the index of the clause to which the $\ell^{\text{th}}$ occurrence of literal $x_i$ (or $\overline{x}_i$) belongs, the framed value is the size of the initial coalition in partition $\spartition$, and $[\dots]$ denotes an arbitrary order over the rest of the coalition sizes.

$y_i^1:$     $|K_{\clauseof{x_i^1}}|+2 \succ |K_{\clauseof{x_i^1}+1}|+2 \succ |K_{\clauseof{x_i^1}+1}|+1 \succ |K_{\clauseof{x_i^1}}|+1 \succ |Y_i^1|+2 \succ |Y_i^2|+2 \succ |Y_i^2|+1 \succ |Y_i^1|+1 \succ  \boxed{1} \succ [\dots]$

$y_{i'}^2:$     $|K_{\clauseof{x_{i'}^2}}|+2 \succ |K_{\clauseof{x_{i'}^2}+1}|+2 \succ |K_{\clauseof{x_{i'}^2}+1}|+1 \succ |K_{\clauseof{x_{i'}^2}}|+1 \succ |Y_{i'}^2|+2 \succ |Y_{i'+1}^1|+2 \succ |Y_{i'+1}^1|+1 \succ |\overline{Y_{i'+1}^1}|+2 \succ $
$|\overline{Y_{i'+1}^1}|+1 \succ |Y_{i'}^2|+1 \succ  \boxed{1} \succ [\dots]$

$y_p^2:$     $|K_{\clauseof{x_p^2}}|+2 \succ |K_{\clauseof{x_p^2}+1}|+2 \succ |K_{\clauseof{x_p^2}+1}|+1 \succ |K_{\clauseof{x_p^2}}|+1 \succ |Y_p^2|+2 \succ |K_1|+2 \succ |K_1|+1 \succ |Y_p^2|+1 \succ  \boxed{1} \succ [\dots]$

$\overline{y}_i^1:$     $|K_{\clauseof{\overline{x}_i^1}}|+2 \succ |K_{\clauseof{\overline{x}_i^1}+1}|+2 \succ  |K_{\clauseof{\overline{x}_i^1}+1}|+1 \succ |K_{\clauseof{\overline{x}_i^1}}|+1 \succ |\overline{Y_i^1}|+2 \succ |\overline{Y_i^2}|+2 \succ |\overline{Y_i^2}|+1 \succ |\overline{Y_i^1}|+1 \succ  \boxed{1} \succ [\dots]$

$\overline{y}_{i'}^2:$     $|K_{\clauseof{\overline{x}_{i'}^2}}|+2 \succ |K_{\clauseof{\overline{x}_{i'}^2}+1}|+2 \succ |K_{\clauseof{\overline{x}_{i'}^2}+1}|+1 \succ |K_{\clauseof{\overline{x}_{i'}^2}}|+1 \succ |\overline{Y_{i'}^2}|+2 \succ |Y_{i'+1}^1|+2 \succ |Y_{i'+1}^1|+1 \succ |\overline{Y_{i'+1}^1}|+2 \succ$
$|\overline{Y_{i'+1}^1}|+1 \succ |\overline{Y_{i'}^2}|+1 \succ  \boxed{1} \succ [\dots]$

$\overline{y}_p^2:$     $|K_{\clauseof{\overline{x}_p^2}}|+2 \succ |K_{\clauseof{\overline{x}_p^2}+1}|+2 \succ |K_{\clauseof{\overline{x}_p^2}+1}|+1 \succ |K_{\clauseof{\overline{x}_p^2}}|+1 \succ |\overline{Y_p^2}|+2 \succ |K_1|+2 \succ |K_1|+1 \succ |\overline{Y_p^2}|+1 \succ  \boxed{1} \succ [\dots]$

$t:$     $|K_{m+1}|+2 \succ |Y_{1}^1|+2 \succ |Y_{1}^1|+1 \succ |\overline{Y_{1}^1}|+2 \succ |\overline{Y_{1}^1}|+1 \succ |K_{m+1}|+1 \succ \boxed{1} \succ [\dots]$

$K_j:$     $|K_j|+2 \succ |K_j|+1 \succ \boxed{|K_j|} \succ 1 \succ [\dots]$

$Y_i^\ell:$     $|Y_i^\ell|+2 \succ |Y_i^\ell|+1 \succ \boxed{|Y_i^\ell|} \succ 1 \succ [\dots]$

$\overline{Y_i^\ell}:$     $|\overline{Y_i^\ell}|+2 \succ |\overline{Y_i^\ell}|+1 \succ \boxed{|\overline{Y_i^\ell}|} \succ 1 \succ [\dots]$

We claim that there exists a cycle of IS deviations iff formula $\varphi$ is satisfiable[Note that the is nevertheless always IS.].

The global idea of the proof is that a cycle of IS deviations necessarily involves, as deviating agents, agent $t$ and $(i)$ one literal-agent for each clause (the associated literal occurrence of the literal-agent belongs to the clause), as well as $(ii)$ the two literal-agents associated with a same literal for each variable.
All these agents must be distinct, implying the existence of a truth assignment of the variables that satisfies all the clauses.
The cycle of IS deviations is such that the literal-agents corresponding to case $(i)$ alternate between joining the coalition of dummy clause agents associated with their clause and the one associated with the next clause (w.r.t. the indices of clauses),
and the literal-agents corresponding to case $(ii)$ alternate between joining the coalition of dummy variable agents associated with their literal occurrence and the one associated with the other occurrence of the same literal, if the literal-agent corresponds to the first occurrence of the literal, or the first occurrence of the chosen literal of the next variable (w.r.t. the indices of variables), if the literal-agent corresponds to the second occurrence of the literal.
The example of such a cycle can be found in Figure <ref>.

Suppose first that formula $\varphi$ is satisfiable by a truth assignment of the variables denoted by $\phi$.
Let us denote by $\ell_j$ a chosen literal-agent associated with an occurrence of a literal true in $\phi$ which belongs to clause $C_j$.
Since all the clauses of $\varphi$ are satisfied by $\phi$, there exists such a literal-agent $\ell_j$ for each clause $C_j$.
Further, let us denote by $z_i^1$ and $z_i^2$ the literal-agents associated with the two occurrences of the literal of variable $x_i$ which is false in $\phi$.
In the same vein, let us denote by $Z_i^1$ and $Z_i^2$ the coalitions of dummy variable agents associated with $z_i^1$ and $z_i^2$, respectively.
Since $\phi$ is a truth assignment of the variables, $z_i^1$, $z_i^2$, $Z_i^1$ and $Z_i^2$ all correspond to the same literal (either $x_i$ or $\overline{x}_i$) and it holds that $\bigcup_{1\leq j\leq m}\ell_j \cap \bigcup_{1\leq i\leq p} \{z_i^1,z_i^2\}=\emptyset$.
We will construct a cycle of IS deviations involving, as deviating agents, the literal-agents $\ell_j$, for every $1\leq j\leq m$, the literal-agents $z_i^1$ and $z_i^2$, for every $1\leq i\leq p$, and agent $t$.
Since $m$ is even in a (3,B2)-SAT (recall that $m=4/3p$), there is an odd number of deviating agents in total.
The main steps of the cycle are illustrated in Figure <ref>.

(K1) at (0,-4) $K_1\cup\{y_1^1,y_3^2\}$;
(K2) at ($(K1)+(3,0)$) $K_2$;
(K3) at ($(K2)+(3,0)$) $K_3\cup\{y_2^2\}$;
(K4) at ($(K3)+(3,0)$) $K_4\cup\{y_1^2,\overline{y}_3^2\}$;
(K5) at ($(K4)+(3,0)$) $K_5$;
(Y11) at ($(K1)+(0,-0.75)$) $Y_1^1$;
(Y12) at ($(Y11)+(3,0)$) $Y_1^2$;
(nY11) at ($(Y12)+(3,0)$) $\overline{Y_1^1}\cup\{t,\overline{y}_1^1\}$;
(nY12) at ($(nY11)+(3,0)$) $\overline{Y_1^2}$;
(Y21) at ($(Y11)+(0,-0.75)$) $Y_2^1$;
(Y22) at ($(Y21)+(3,0)$) $Y_2^2$;
(nY21) at ($(Y22)+(3,0)$) $\overline{Y_2^1}\cup\{\overline{y}_1^2,\overline{y}_2^1\}$;
(nY22) at ($(nY21)+(3,0)$) $\overline{Y_2^2}$;
(Y31) at ($(Y21)+(0,-0.75)$) $Y_3^1\cup\{\overline{y}_2^2,y_3^1\}$;
(Y32) at ($(Y31)+(3,0)$) $Y_3^2$;
(nY31) at ($(Y32)+(3,0)$) $\overline{Y_3^1}$;
(nY32) at ($(nY31)+(3,0)$) $\overline{Y_3^2}$;
(y11) at ($(K5)+(-1,-0.325)$) ;
(y21) at ($(y11)+(0,-0.75)$) $y_2^1$;
(ny31) at ($(y21)+(2,0)$) $\overline{y}_3^1$;
(pi) at ($(K1)+(-2,-1)$) $\partition$:;
[arrow,line width=0.001pt] ($(K1)+(0.65,-0.25)$) – (Y32);
[arrow,line width=0.001pt] ($(Y31)+(0.65,-0.25)$) to[bend right=10] (Y32);
[arrow,line width=0.001pt] ($(Y31)+(0.25,-0.25)$) to[bend right=20] (nY22);
[arrow,line width=0.001pt] ($(nY11)+(0.65,0.15)$) to[bend left=15] (nY12);
[arrow,line width=0.001pt] ($(nY21)+(0.25,0.15)$) – (nY12);
[arrow,line width=0.001pt] ($(nY21)+(0.65,0.15)$) to[bend left=15] (nY22);
[arrow,line width=0.001pt] ($(K4)+(0.15,0.15)$) to[bend right=20] (K3);
[arrow,line width=0.001pt] ($(K4)+(0.65,0.25)$) to[bend left=20] (K5);
[arrow,rounded corners,line width=0.001pt] ($(nY11)+(0.25,0.1)$) |- ($(K5)+(0,-0.25)$) – ($(K5)+(0,-0.1)$);
[arrow,line width=3pt] ($(pi)+(8,-1.75)$) – ($(pi)+(8,-2.75)$);
(K1) at (0,-8.25) $K_1\cup\{y_1^1\}$;
(K2) at ($(K1)+(3,0)$) $K_2$;
(K3) at ($(K2)+(3,0)$) $K_3\cup\{y_2^2,y_1^2\}$;
(K4) at ($(K3)+(3,0)$) $K_4$;
(K5) at ($(K4)+(3,0)$) $K_5\cup\{\overline{y}_3^2,t\}$;
(Y11) at ($(K1)+(0,-0.75)$) $Y_1^1$;
(Y12) at ($(Y11)+(3,0)$) $Y_1^2$;
(nY11) at ($(Y12)+(3,0)$) $\overline{Y_1^1}$;
(nY12) at ($(nY11)+(3,0)$) $\overline{Y_1^2}\cup\{\overline{y}_1^1,\overline{y}_1^2\}$;
(Y21) at ($(Y11)+(0,-0.75)$) $Y_2^1$;
(Y22) at ($(Y21)+(3,0)$) $Y_2^2$;
(nY21) at ($(Y22)+(3,0)$) $\overline{Y_2^1}$;
(nY22) at ($(nY21)+(3,0)$) $\overline{Y_2^2}\cup\{\overline{y}_2^1,\overline{y}_2^2\}$;
(Y31) at ($(Y21)+(0,-0.75)$) $Y_3^1$;
(Y32) at ($(Y31)+(3,0)$) $Y_3^2\cup\{y_3^1,y_3^2\}$;
(nY31) at ($(Y32)+(3,0)$) $\overline{Y_3^1}$;
(nY32) at ($(nY31)+(3,0)$) $\overline{Y_3^2}$;
(y11) at ($(K5)+(-1,-0.325)$) ;
(y21) at ($(y11)+(0,-0.5)$) $y_2^1$;
(ny31) at ($(y21)+(2,0)$) $\overline{y}_3^1$;
(pi) at ($(K1)+(-2,-1)$) $\partition_1$:;
[arrow,line width=0.001pt] ($(K1)+(0.35,0.2)$) to[bend left] (K2);
[arrow,line width=0.001pt] ($(K3)+(0.75,0.2)$) to[bend left] (K4);
[arrow,line width=0.001pt] ($(K3)+(0.2,0.2)$) to[bend right] (K2);
[arrow,line width=0.001pt] ($(K5)+(0.25,0.2)$) to[bend right] (K4);
[arrow,line width=0.001pt] ($(Y32)+(0.15,-0.25)$) to[bend left=15] (Y31);
[arrow,line width=0.001pt] ($(nY12)+(0.15,0.2)$) to[bend right=15] (nY11);
[arrow,line width=0.001pt] ($(nY22)+(0.15,0.2)$) to[bend right=10] (nY21);
[arrow,rounded corners,line width=0.001pt] ($(Y32)+(0.65,-0.25)$) |- ($(Y31)+(-0.5,-0.5)$) |- ($(K1)+(-0.45,-0.25)$);
[arrow,line width=0.001pt] ($(nY12)+(0.6,-0.25)$) – ($(nY21)+(0.25,0.2)$);
[arrow,rounded corners,line width=0.001pt] ($(nY22)+(0.7,-0.2)$) – ($(nY32)+(0.7,-0.4)$) -| (Y31);
[arrow,line width=3pt] ($(pi)+(8,-1.75)$) – ($(pi)+(8,-2.75)$);
(K1) at (0,-12.5) $K_1\cup\{y_3^2\}$;
(K2) at ($(K1)+(3,0)$) $K_2\cup\{y_1^1,y_2^2\}$;
(K3) at ($(K2)+(3,0)$) $K_3$;
(K4) at ($(K3)+(3,0)$) $K_4\cup\{y_1^2,\overline{y}_3^2\}$;
(K5) at ($(K4)+(3,0)$) $K_5$;
(Y11) at ($(K1)+(0,-0.75)$) $Y_1^1$;
(Y12) at ($(Y11)+(3,0)$) $Y_1^2$;
(nY11) at ($(Y12)+(3,0)$) $\overline{Y_1^1}\cup\{t,\overline{y}_1^1\}$;
(nY12) at ($(nY11)+(3,0)$) $\overline{Y_1^2}$;
(Y21) at ($(Y11)+(0,-0.75)$) $Y_2^1$;
(Y22) at ($(Y21)+(3,0)$) $Y_2^2$;
(nY21) at ($(Y22)+(3,0)$) $\overline{Y_2^1}\cup\{\overline{y}_1^2,\overline{y}_2^1\}$;
(nY22) at ($(nY21)+(3,0)$) $\overline{Y_2^2}$;
(Y31) at ($(Y21)+(0,-0.75)$) $Y_3^1\cup\{\overline{y}_2^2,y_3^1\}$;
(Y32) at ($(Y31)+(3,0)$) $Y_3^2$;
(nY31) at ($(Y32)+(3,0)$) $\overline{Y_3^1}$;
(nY32) at ($(nY31)+(3,0)$) $\overline{Y_3^2}$;
(y11) at ($(K5)+(-1,-0.325)$) ;
(y21) at ($(y11)+(0,-0.5)$) $y_2^1$;
(ny31) at ($(y21)+(2,0)$) $\overline{y}_3^1$;
(pi) at ($(K1)+(-2,-1)$) $\partition_2$:;
[arrow,line width=0.001pt] ($(K2)+(0.1,0.2)$) to[bend right] (K1);
[arrow,line width=0.001pt] ($(K2)+(0.6,0.2)$) to[bend left] (K3);
[arrow,line width=3pt,rounded corners] ($(pi)+(8,-1.75)$) – ($(pi)+(-0.5,-1.75)$) |- ($(pi)+(1,9)$);

Example for the cycle of IS deviations described in the reduced instance of Lemma <ref>. The illustration is for a yes-instance of (3,B2)-SAT with four clauses and three variables where $\varphi\equiv (x_1 \vee x_2 \vee x_3) \wedge (\overline{x}_1 \vee x_2 \vee \overline{x}_3) \wedge (x_1 \vee \overline{x}_2 \vee x_3) \wedge (\overline{x}_1 \vee \overline{x}_2 \vee \overline{x}_3)$. We consider the truth assignment of the variables $\phi$ where literals $x_1$, $x_2$ and $\overline{x}_3$ are true. Assignment $\phi$ satisfies formula $\varphi$ with, e.g., literal $x_1$ which makes clauses $C_1$ and $C_3$ true, literal $x_2$ which makes clause $C_2$ true, and literal $\overline{x}_3$ which makes clause $C_4$ true.
By using the notations of the proof, we thus have $\ell_1=y_1^1$, $\ell_2=y_2^2$, $\ell_3=y_1^2$, $\ell_4=\overline{y}_3^2$ and, for every $r\in\{1,2\}$, $Z_1^r=\overline{Y_1^r}$, $Z_2^r=\overline{Y_2^r}$, and $Z_3^r=Y_3^r$.

First of all, let agent $z_p^2$ and then agent $\ell_1$ join coalition $K_1$.
For each $1<i\leq p$, let agent $z_{i-1}^2$ and then agent $z_i^1$ join coalition $Z_i^1$.
Let agent $t$ and then agent $z_1^1$ join coalition $Z_1^1$.
For each even $j$ such that $3<j\leq m$, let agent $\ell_{j-1}$ and then agent $\ell_j$ join coalition $K_j$.
Finally, let agent $\ell_2$ join coalition $K_3$.
The reached partition is
\{K_1\cup\{\ell_1,z_p^2\},K_2,K_3\cup\{\ell_2\},K_4\cup\{\ell_3,\ell_4\},K_5,K_6\cup\{\ell_5,\ell_6\},K_7,\dots,K_m\cup\{\ell_{m-1},\allowbreak\ell_m\},K_{m+1},Z_1^1\cup\{t,z_1^1\},Z_1^2,\allowbreak Z_2^1\cup\{z_1^2,z_2^1\},Z_2^2,\dots,Z_p^1\cup\{z_{p-1}^2,\allowbreak z_p^1\},Z_p^2,\overline{Z_1^1},\overline{Z_1^2},\dots,\overline{Z_p^1},\overline{Z_p^2}\}$, where coalition $\overline{Z_i^\ell}$ refers to $\overline{Y_i^\ell}$ if $Z_i^\ell=Y_i^\ell$ and to $Y_i^\ell$ if $Z_i^\ell=\overline{Y_i^\ell}$.
Partition $\partition$ is the first step of the cycle (see Figure <ref>).

From partition $\partition$, let literal-agent $\ell_3$ deviate from current coalition $K_4\cup\{\ell_3,\ell_4\}$ to join coalition $K_3\cup\{\ell_2\}$.
This deviation makes literal-agent $\ell_4$ worse off, who then deviates to join coalition $K_5$.
Then, the same deviations occur for literal-agents $\ell_5$ and $\ell_6$, and so on.
More generally, for every odd $j$ such that $3\leq j\leq m$ by increasing order of indices, literal-agent $\ell_j$ leaves coalition $K_{j+1}\cup\{\ell_j,\ell_{j+1}\}$ to join coalition $K_j\cup\{\ell_{j-1}\}$ and then literal-agent $\ell_{j+1}$, who is worse off by this deviation, deviates to join coalition $K_{j+2}$.
After that, agent $t$ deviates from coalition $Z_1^1\cup\{t,z_1^1\}$ to join coalition $K_{m+1}\cup\{\ell_m\}$, which makes literal-agent $z_1^1$ worse off.
Then, for each $1\leq i\leq p$ by increasing order of indices, let literal-agent $z_i^1$ deviate from coalition $Z_i^1\cup\{z_i^1\}$ to join coalition $Z_i^2$ and then, if $i<p$, literal-agent $z_i^2$ deviates from coalition $Z_{i+1}^1\cup\{z_i^2,z_{i+1}^1\}$
to join coalition $Z_i^2\cup\{z_i^1\}$, which makes literal-agent $z_{i+1}^1$
worse off.
Afterwards, literal-agent $z_p^2$ deviates from coalition $K_1\cup\{z_i^2,\ell_1\}$ to join coalition $Z_p^2\cup\{z_p^1\}$, which makes literal-agent $\ell_1$ worse off.
We thus reach partition $\partition_1:=\{K_1\cup\{\ell_1\},K_2,K_3\cup\{\ell_2,\ell_3\},K_4,K_5\cup\{\ell_4,\ell_5\},K_6,K_7\cup\{\ell_6,\ell_7\},\dots,K_{m-1}\cup\{\ell_{m-2},\allowbreak\ell_{m-1}\},K_m,K_{m+1}\cup\{\ell_m,t\},Z_1^1,Z_1^2\cup\{z_1^1,z_1^2\},\allowbreak Z_2^1,Z_2^2\cup\{z_2^1,z_2^2\},\dots,Z_p^1,Z_p^2\cup\{z_p^1,\allowbreak z_p^2\},\overline{Z_1^1},\overline{Z_1^2},\dots,\overline{Z_p^1},\overline{Z_p^2}\}$ (see Figure <ref>).

Then, from partition $\partition_1$, for every odd $j$ such that $1\leq j < m$ by increasing order of indices, let literal-agent $\ell_j$ deviate from coalition $K_j\cup\{\ell_j\}$ to join coalition $K_{j+1}$ and then, if $j<m-1$, literal-agent $\ell_{j+1}$ deviates from $K_{j+2}\cup\{\ell_{j+1},\ell_{j+2}\}$
to join coalition $K_{j+1}\cup\{\ell_j\}$, which makes literal-agent $\ell_{j+2}$
worse off.
Afterwards, literal-agent $\ell_m$ deviates from $K_{m+1}\cup\{\ell_m,t\}$ to join coalition $K_m\cup\{\ell_{m-1}\}$, which makes literal-agent $t$ worse off.
Let agent $t$ then deviate from coalition $K_{m+1}\cup\{t\}$ to join coalition $Z_1^1$ and literal-agent $z_1^1$ deviate from coalition $Z_1^2\cup\{z_1^1,z_1^2\}$ to join coalition $Z_1^1\cup\{t\}$, which makes literal-agent $z_1^2$ worse off.
Then, for each $1\leq i < p$  by increasing order of indices, let literal-agent $z_i^2$ deviate from coalition $Z_i^2\cup\{z_i^2\}$ to join coalition $Z_{i+1}^1$, and literal-agent $z_{i+1}^1$ deviate from coalition $Z_{i+1}^2\cup\{z_{i+1}^1,z_{i+1}^2\}$ to join coalition $Z_{i+1}^1\cup\{z_i^2\}$, which makes literal-agent $z_{i+1}^2$ worse off.
And then, let literal-agent $z_p^2$ deviate from coalition $Z_p^2\cup\{z_p^2\}$ to join coalition $K_1$, leading to partition $\partition_2$ (see Figure <ref>).
Afterwards, literal-agent $\ell_1$ deviates from coalition $K_2\cup\{\ell_1,\ell_2\}$ to join coalition $K_1\cup\{z_p^2\}$, which makes literal-agent $\ell_2$ worse off.
Finally, let literal-agent $\ell_2$ deviate from coalition $K_2\cup\{\ell_2\}$ to join coalition $K_3$, and we have finally reached partition $\partition$, leading to a cycle.

Suppose now that there exists a cycle of IS deviations.
Observe first that no dummy agent can deviate.
Indeed, the only coalition sizes that are preferred by a dummy agent to the size of her initial coalition are the size of the current coalition plus one and the size of the current coalition plus two.
These sizes cannot be reached by joining other coalitions by condition $(1)$, and the fact that the other coalitions do not want to integrate more than two additional agents in their coalition.
Therefore, the only possible deviations are when the dummy agents let at most two agents join their coalition.
It follows, by construction of the preferences, that no agent can belong to a coalition whose size is ranked after size 1 in her preferences, i.e., we do not have to care about the preferences within $[\dots]$ in the preference ranking of the agents.
Indeed, a literal-agent or agent $t$ (for the sake of simplicity we also talk about agent $t$ when referring to literal-agents since the behavior is similar), whose initial coalition is of size one, can join some coalitions of dummy agents and sometimes accepts one additional literal-agent in such coalitions.
The worst thing that can happen to these deviating literal-agents is that the other literal-agent, who has joined the same coalition of dummy agents as her, leaves the coalition.
However, in such a case, by construction of the preferences, both literal-agents are still in a coalition whose size is ranked before one in their preferences.

Observe that literal-agents can only join coalitions of dummy agents with at most one other literal-agent in this coalition and that no literal-agent can join another literal-agent outside a coalition of dummy agents, because size two is not ranked before size one in the preferences of the agents (recall that a coalition of dummy agents cannot be of size smaller than 2).
Moreover, since the literal-agents can never be in a coalition of size less preferred than one, once a literal-agent deviates from her initial coalition where she is alone, she has no incentive to come back to the coalition where she is alone.
Hence, the deviations in the cycle must be performed by literal-agents who join different coalitions of dummy agents.

Because only literal-agents can deviate and all non-singleton coalitions of any reached partition must of the form of a coalition of dummy agents (from the initial partition) potentially joined by one or two literal-agents, each deviating literal-agent $ag$ in the cycle must be left at some step in order to come back to a less preferred coalition.
Since literal-agent $ag$ can be left only by one other literal-agent, it follows that the current coalition of agent $ag$ was of size $|K|+2$ for a given coalition $K$ of dummy agents and becomes of size $|K|+1$.
To be able to come back to a previous less preferred coalition, agent $i$ must prefer $|K|+2$ over $|K|+1$.
Moreover, since literal-agent $i$ is a deviating agent, there must be intermediate sizes in the preference ranking of agent $ag$ between $|K|+2$ and $|K|+1$.
Say that literal-agent $ag$ corresponds to a literal-agent $z_i^\ell$ where $z_i$ refers either to literal $y_i$ or to literal $\overline{y}_i$, and $Z_i^\ell$ refers to the associated clause of dummy variable agents, i.e., $Z_i^\ell=Y_i^\ell$ if $z_i^\ell=y_i^\ell$, and $Z_i^\ell=\overline{Y_i^\ell}$ if $z_i^\ell=\overline{y}_i^\ell$.
Moreover, denote by $j$ the index of the clause to which the literal associated with $z_i^\ell$ belongs, i.e., $j=\clauseof{x_i^\ell}$ if $z_i^\ell=y_i^\ell$ and $j=\clauseof{\overline{x}_i^\ell}$ if $z_i^\ell=\overline{y}_i^\ell$.
by construction of the preferences, coalition $K$ of dummy agents can only be: $(a)$
$K_j$, i.e., the coalition associated with the clause to which the occurrence of the literal of the literal-agent belongs, or $(b)$
$Z_i^\ell$, i.e., the coalition associated with the occurrence of the literal of the literal-agent.
We detail below the possible cases for coalition $K$.

* If $K$ is the coalition of dummy clause agents $K_j$,
then the other literal-agent who leaves the coalition cannot be associated with an occurrence of a literal belonging to the corresponding clause.
Indeed, otherwise, by construction of the preferences, the size of this coalition would be the most preferred one for this leaving literal-agent, contradicting her IS deviation from this coalition.
Therefore, according to the preferences of the literal-agents, the only possibility is that this other literal-agent who leaves coalition $K_j$
is associated with an occurrence of a literal belonging to $C_{j-1}$ if $j>1$ or is agent $z_p^2\in\{y_p^2,\overline{y}_p^2\}$
if $j=1$.
Due to the preferences of the literal-agents, if a literal-agent leaves such a coalition, it is necessarily for joining the coalition of dummy agents $K_{j-1}$ (which has an additional literal-agent) if $j>1$ or
$Z_p^2$ (with an additional literal-agent) if $j=1$.
In the latter case ($j=1$), this is the only possibility even if the associated deviating agent
$z_p^2$ prefers several other coalition sizes over $|K_1|+2$, because these other choices would prevent her to come back to size $|K_1|+2$: the worst thing that can occur after some steps if $z_p^2$ chooses preferred coalitions other than $Z_p^2$ is that she would be in a coalition of size $|K_{\clauseof{x_p^2}}|+1$ or $|K_{\clauseof{x_p^2}+1}|+1$ if $z_p^2=y_p^2$, or $|K_{\clauseof{\overline{x}_p^2}}|+1$ or $|K_{\clauseof{\overline{x}_p^2}+1}|+1$) if $z_p^2=\overline{y}_p^2$, and both sizes are preferred to $|K_1|+2$, which contradicts the cycle.

* If $K$ is the coalition of dummy variable agents $Z_i^1$,
i.e., $\ell=1$, then the only possibility is that the other literal-agent who leaves the coalition is literal-agent $z_{i-1}^2\in\{y_{i-1}^2,\overline{y}_{i-1}^2\}$
if $i>1$, or agent $t$ if $i=1$.

If $i>1$, following the same argument as in case (a) for agent $z_p^2$, literal-agent $z_{i-1}^2$
cannot deviate to coalitions of dummy clause agents, otherwise she would never come back to the current coalition size.
$Z_i^1=Y_i^1$, then the only possibility is that literal-agent $z_{i-1}^2$
deviates for joining coalition $Z_{i-1}^2$
(and an additional literal-agent).
Otherwise, i.e., if
$Z_i^1=\overline{Y_i^1}$, then literal-agent $z_{i-1}^2$
can deviate to join $Z_{i-1}^2$
(and an additional literal-agent), but she could also deviate for joining the coalition of dummy variable agents $Y_i^1$.
In the latter case, by construction of the preferences, the only other agent who can also join coalition $Y_i^1$ is literal-agent $y_i^1$.
If $y_i^1$ never joins this coalition, then agent $z_{i-1}^2$ would impact no deviating agent by staying in this coalition, and it would not enable her to come back to a previous less preferred coalition since no agent can leave the coalition.
Therefore, because she still prefers coalition $Z_{i-1}^2$, she would deviate anyway to coalition $Z_{i-1}^2$.
Otherwise, i.e., if $y_i^1$ joins the coalition (before or after $z_{i-1}^2$), it means that agent $y_i^1$ reaches the best possible coalition of dummy variable agents.
By following the same arguments as in case (a) for agent $z_p^2$, agent $y_i^1$ cannot deviate to coalitions of dummy clause agents, otherwise she would never come back to the current coalition size.
It follows that agent $y_i^1$ has no reason to deviate from the coalition she forms with $z_{i-1}^2$ and $Y_i^1$.
Therefore, in order to be left at some point of the cycle in order to come back to a previous less preferred coalition, agent $z_{i-1}^2$ still needs to deviate and the only possibility is to join coalition $Z_{i-1}^2$ (and an additional literal-agent).

If $i=1$, the same arguments can be applied and then agent $t$ deviates to join the coalition of dummy clause agents $K_{m+1}$.

* If $K$ is the coalition of dummy variable agents $Z_i^2$,
i.e., $\ell=2$, then the only possibility is that the other literal-agent who leaves the coalition is literal-agent $z_i^1$ (i.e., the literal-agent that is associated with the first occurrence of the same literal as $z_i^\ell$).
Since, literal-agent $z_i^1$
cannot deviate to join a coalition of dummy clause agents (by following the same arguments as in case (a) for agent $z_p^2$), she will necessarily join the coalition of dummy variable agents $Z_i^1$
(with an additional literal-agent).

To summarize, if there is a cycle, only the following can occur:

* agent $t$ in coalition $K_{m+1}$ can only be left by a literal-agent corresponding to an occurrence of a literal belonging to clause $C_m$ who deviates to join the coalition of dummy clause agents $K_m$;

* a literal-agent $y_i^\ell$ (or $\overline{y}_i^\ell$) in a coalition of dummy clause agents $K_j$ (for $1<j\leq m$), corresponding to the clause $C_j$ to which the $\ell^\text{th}$ occurrence of $x_i$ (or $\overline{x}_i$) belongs, can only be left by a literal-agent corresponding to an occurrence of a literal belonging to clause $C_{j-1}$ who deviates to join the coalition of dummy clause agents $K_{j-1}$;

* a literal-agent $y_i^\ell$ (or $\overline{y}_i^\ell$) in the coalition of dummy clause agents $K_1$, corresponding to the clause $C_1$ to which the $\ell^\text{th}$ occurrence of $x_i$ (or $\overline{x}_i$) belongs, can only be left by literal-agent $y_p^2$ or $\overline{y}_p^2$ who joins the coalition of dummy variable agents $Y_p^2$ or $\overline{Y_p^2}$, respectively;

* a literal-agent $y_i^2$ (or $\overline{y}_i^2$), for $1\leq i\leq p$, in a coalition of dummy variable agents $Y_i^2$ (or $\overline{Y_i^2}$) can only be left by literal-agent $y_{i}^1$ (or $\overline{y}_{i}^1$) who joins the coalition of dummy variable agents $Y_{i}^1$ (or $\overline{Y}_{i}^1$);

* a literal-agent $y_i^1$ (or $\overline{y}_i^1$), for $1<i\leq p$, in a coalition of dummy variable agents $Y_i^1$ (or $\overline{Y_i^1}$) can only be left by a literal-agent $y_{i-1}^2$ or $\overline{y}_{i-1}^2$ who eventually joins the coalition of dummy variable agents $Y_{i-1}^2$ or $\overline{Y}_{i-1}^2$, respectively;

* literal-agent $y_1^1$ (or $\overline{y}_1^1$) in the coalition of dummy variable agents $Y_1^1$ (or $\overline{Y_1^1}$) can only be left by agent $t$ who joins the coalition of dummy clause agents $K_{m+1}$.

Therefore, as soon as there is one deviating literal-agent in the cycle, it implies that there exists a whole chain of deviating agents in the cycle, who alternate between joining coalitions of dummy agents which are consecutive in the following cycle over initial coalitions: $K_1 < K_2 < \dots < K_m < K_{m+1} < Z_1^1 < Z_1^2 < Z_2^1 < Z_2^2 < \dots < Z_p^1 < Z_p^2 < K_1$, where $Z_i^1$ and $Z_i^2$ refer either to $Y_i^1$ and $Y_i^2$, or to $\overline{Y_i^1}$ and $\overline{Y_i^2}$.
More precisely, for the cycle to occur, we need, as deviating agents, $(i)$ for each clause, a literal-agent corresponding to an occurrence of a literal belonging to this clause who alternates between the coalition of dummy clause agents associated with this clause and the next coalition in the previously mentioned cycle over initial coalitions (cases (1)-(3))
and, $(ii)$ for each variable, two literal-agents corresponding to the same literal, who alternate between the coalition of dummy variable agents associated with their literal occurrence and the next coalition in the previously mentioned cycle over initial coalitions (cases (3)-(6)).
As described in the previous case distinctions, these two groups of deviating literal-agents ($(i)$ and $(ii)$) are distinct because,
by construction of the preferences,
once a literal-agent reaches the coalition of dummy clause agents associated with the clause to which her corresponding literal belongs, she cannot be in a coalition of less preferred size, and in particular the coalition of dummy variable agents associated with her literal
(recall that only literal-agents can deviate and that at most two literal-agents can join a coalition of dummy agents).
Moreover, as summarized in case (4), we need that the two deviating literal-agents associated with each variable (group $(ii)$) correspond to the same literal of the variable.
Hence, by setting to true the literals associated with the deviating literal-agents of group $(i)$ and to false the literals associated with the deviating literal-agents of group $(ii)$ (and arbitrarily the rest of literals), we get a valid truth assignment of the variables which satisfies all the clauses.

Assume, for the sake of contradiction, that there exists a cycle of IS deviations in some execution of the dynamics.
Let us call an IS deviation from a coalition of size $s$ to a coalition of size $s'$ an L-move (or R-move) if the deviating agent goes to the left (or right) of the single-peaked axis, i.e., $s'<s$ (or $s'>s$).
Clearly, there cannot be only L-moves or R-moves in the cycle.
Moreover, the deviating agents in the cycle cannot perform only L-moves or R-moves.
Therefore, for a deviating agent $i$ to pass from L-moves to R-moves, agent $i$ must be hurt by the departure of another agent $j$ from her coalition at some step of the cycle, i.e., $i$ was making a series of L-moves (so she was in a coalition whose size is on the right of her peak in the single-peaked axis) but then was worse off enough by the departure of $j$ (her current coalition size becomes at the left of her peak in the axis) to start R-moves (in order to go back to the right of her peak in the axis).
In other words, there must exist coalition sizes $s_i$ and $s'_i$ such that $s_i \succ_i s'_i \succ_i s_i-1$ where $s_i$ refers to the coalition size from which $i$ is left by $j$.
Moreover, for hurting agent $i$ with her departure, agent $j$ must have arrived before $i$ in the coalition of size $s_i$.
Therefore, there exists coalition size $s_j$ such that $s_j \succ_j s_i \succsim_j s_i-1$.
Since $j$ is a deviating agent, she must also be hurt by the departure of another agent at some step of the cycle.
After the departure of this other agent, $j$ must have reached a coalition size that she prefers less than $s_i-1$, otherwise she would have no reason to be at some point in a coalition size $s_i-1$.
It follows that there exists coalition size $s_j$ such that $s_j \succ_j s_i \succsim_j s_i-1 \succ_j s_j-1$.
By the same argument, the agent who leaves agent $j$ must also be left by another agent and so on.
Since the number of deviating agents in the cycle is finite, we go back at some point to a previously considered agent, forming a cycle in the agents who hurt each other by their departure; let us call these agents $1,\dots,k$ where agent $i$ hurts agent $i+1 \pmod{k}$ by her departure from their common coalition of size $s_{i+1\pmod{k}}$, for each $i\in[k]$.
Thus, it holds that:

$1:$     $s_1 \succ s_2 \succsim s_2-1 \succ s_1-1$

$2:$     $s_2 \succ s_3 \succsim s_3-1 \succ s_2-1$

$k:$     $s_k \succ s_1 \succsim s_1-1 \succ s_k-1$

Since the preferences are naturally single-peaked, it must hold that $s_{i+1 \pmod{k}}>s_i$, for every $i\in [k]$.
Hence, $s_1<s_2<\dots<s_k<s_1$, a contradiction.

§ HEDONIC DIVERSITY GAMES

In this section, we provide the missing proofs for hedonic diversity games. First, we consider the remaining two examples of cycling under strong assumptions.

$(\lnot 1)$ Our next example satisfies all properties except single-peakedness of preferences. Let us consider an HDG with 12 agents: 3 red agents and 9 blue agents.
There are two deviating agents in the cycle: blue agents $b_1$ and $b_2$.
In the cycle, there are three fixed coalitions $C_1$, $C_2$ and $C_3$ such that:

* $C_1$ contains 1 red agent and 2 blue agents;

* $C_2$ contains 1 red agent and 1 blue agent;

* $C_3$ contains 1 red agent and 4 blue agents.

The relevant part of the preferences of the agents is given below. Recall Footnote <ref> where we describe how to complete preferences.

$b_1:$     $\frac{1}{5} \succ \frac{1}{3} \succ \frac{1}{7} \succ \frac{1}{6} \succ \frac{1}{4} \succ 0$

$b_2:$     $\frac{1}{7} \succ \frac{1}{3} \succ \frac{1}{5} \succ \frac{1}{4} \succ \frac{1}{6} \succ 0$

$C_1:$     $\frac{1}{5} \succ \frac{1}{4} \succ \frac{1}{3} \succ \frac{1}{2} \succ [1 \text{ if red, } 0 \text{ otherwise}]$

$C_2:$     $\frac{1}{3} \succ \frac{1}{2} \succ [1 \text{ if red, } 0 \text{ otherwise}]$

$C_3:$     $\frac{1}{7} \succ \frac{1}{6} \succ \frac{1}{5} \succ \frac{1}{4} \succ \frac{1}{3} \succ \frac{1}{2} \succ [1 \text{ if red, } 0 \text{ otherwise}]$

Consider the sequence of IS deviations in Figure <ref> that describes a cycle in the dynamics.
The two deviating agents of the cycle $b_1$ and $b_2$ are marked in bold and the specific deviating agent between two states is indicated next to the arrows.

(1) at (0,0) $C_1\cup\{\mathbf{b_1}\}$     $C_2\cup\{\mathbf{b_2}\}$     $C_3$
$\frac{1}{4}$     $\frac{1}{3}$     $\frac{1}{5}$
(2) at ($(1)+(1.25,2)$) $C_1$     $C_2\cup\{\mathbf{b_2}\}$     $C_3\cup\{\mathbf{b_1}\}$
$\frac{1}{3}$     $\frac{1}{3}$     $\frac{1}{6}$
(3) at ($(2)+(6.25,0)$) $C_1$     $C_2$     $C_3\cup\{\mathbf{b_1},\mathbf{b_2}\}$
$\frac{1}{3}$     $\frac{1}{2}$     $\frac{1}{7}$
(4) at ($(1)+(8.5,0)$) $C_1$     $C_2\cup\{\mathbf{b_1}\}$     $C_3\cup\{\mathbf{b_2}\}$
$\frac{1}{3}$     $\frac{1}{3}$     $\frac{1}{6}$
(6) at ($(1)+(1.25,-2)$) $C_1\cup\{\mathbf{b_1},\mathbf{b_2}\}$     $C_2$     $C_3$
$\frac{1}{5}$     $\frac{1}{2}$     $\frac{1}{5}$
(5) at ($(6)+(6.25,0)$) $C_1\cup\{\mathbf{b_2}\}$     $C_2\cup\{\mathbf{b_1}\}$     $C_3$
$\frac{1}{4}$     $\frac{1}{3}$     $\frac{1}{5}$
[arrow] (1) –node[midway,left]$b_1$ (2); [arrow] (2) –node[midway,above]$b_2$  (3); [arrow] (3) –node[midway,right]$b_1$  (4); [arrow] (4) –node[midway,right]$b_2$  (5); [arrow] (5) –node[midway,above]$b_1$  (6); [arrow] (6) –node[midway,left]$b_2$  (1);

Possibility of cycling of IS dynamics in part $(\lnot 1)$ of Theorem <ref>. Here, we consider IS dynamics starting from the in HDGs under strict preferences, where all deviations satisfy solitary homogeneity.

To show that this cycle can be reached from the , it suffices to observe that the two deviating agents $b_1$ and $b_2$ prefer to join the fixed coalitions than being alone and that each fixed coalition can be formed from the : the red agent of each future fixed coalition joins first a blue agent and then all the other blue agents of the future fixed coalition successively join. Note that all deviations result in non-homogeneous target coalitions, and therefore satisfy solitary homogeneity.

$(\lnot 2)$ Our final example satisfies all properties except strictness of preferences. Let us consider an HDG with 10 agents: 4 red agents and 6 blue agents.
There are two deviating agents: red agent $r$ and blue agent $b$, and three fixed coalitions $C_1$, $C_2$ and $C_3$ such that:

* $C_1$ contains 2 red agents;

* $C_2$ contains 1 red agent and 3 blue agents;

* $C_3$ contains 2 blue agents.

The relevant part of the preferences of the agents is given below.

$r:$     $\frac{3}{4} \succ \frac{2}{5} \succ \frac{1}{4} \sim \frac{1}{3} \succ 1$

$b:$     $\frac{1}{4} \succ \frac{1}{5} \succ \frac{1}{2} \sim \frac{2}{3} \sim \frac{3}{4} \succ 0$

$C_1:$     $\frac{3}{4} \succ \frac{2}{3} \succ \frac{1}{2} \sim \frac{1}{3} \succ 1$

$C_2:$     $\frac{2}{5} \succ \frac{1}{3} \sim \frac{1}{4} \sim \frac{1}{5} \succ \frac{1}{2} \succ [1 \text{ if red, } 0 \text{ otherwise}]$

$C_3:$     $\frac{1}{4} \succ \frac{1}{3} \succ \frac{1}{2} \succ 0$

Consider the sequence of IS deviations in Figure <ref> that describes a cycle in the dynamics.
The two deviating agents of the cycle $r$ and $b$ are marked in bold and the specific deviating agent between two states is indicated next to the arrows.

(1) at (0,0) $C_1\cup\{\mathbf{r}\}$     $C_2\cup\{\mathbf{b}\}$     $C_3$
$1$     $\frac{1}{5}$     $0$
(2) at ($(1)+(1.25,2)$) $C_1$     $C_2\cup\{\mathbf{b}\}$     $C_3\cup\{\mathbf{r}\}$
$1$     $\frac{1}{5}$     $\frac{1}{3}$
(3) at ($(2)+(6.25,0)$) $C_1$     $C_2$     $C_3\cup\{\mathbf{r},\mathbf{b}\}$
$1$     $\frac{1}{4}$     $\frac{1}{4}$
(4) at ($(1)+(8.5,0)$) $C_1$     $C_2\cup\{\mathbf{r}\}$     $C_3\cup\{\mathbf{b}\}$
$1$     $\frac{2}{5}$     $0$
(6) at ($(1)+(1.25,-2)$) $C_1\cup\{\mathbf{b},\mathbf{r}\}$     $C_2$     $C_3$
$\frac{3}{4}$     $\frac{1}{4}$     $0$
(5) at ($(6)+(6.25,0)$) $C_1\cup\{\mathbf{b}\}$     $C_2\cup\{\mathbf{r}\}$     $\{C_3\}$
$\frac{2}{3}$     $\frac{2}{5}$     $0$
[arrow] (1) –node[midway,left]$r$ (2); [arrow] (2) –node[midway,above]$b$  (3); [arrow] (3) –node[midway,right]$r$  (4); [arrow] (4) –node[midway,right]$b$  (5); [arrow] (5) –node[midway,above]$r$  (6); [arrow] (6) –node[midway,left]$b$  (1);

Possibility of cycling of IS dynamics in part $(\lnot 2)$ of Theorem <ref>. Here, we consider IS dynamics starting from the in HDGs under naturally single-peaked preferences, where all deviations satisfy solitary homogeneity.

To show that this cycle can be reached from the , it suffices to observe that partition $\{C_1\cup\{b\},C_2\cup\{r\},C_3\}$ belonging to the cycle can be reached from the .
Indeed, agent $b$ can join a red agent from the future fixed coalition $C_1$ while the other red agent of the future fixed coalition $C_1$ can join a blue agent from the future fixed coalition $C_3$.
The second blue agent of the future fixed coalition $C_3$ then joins them and afterwards, the red agent leaves them to join $b$ and the other red agent of $C_1$.
For forming coalition $C_2$, the red agent joins one of the blue agents, and then the two remaining blue agents join them.
Agent $r$ can then join coalition $C_2$. Note that all deviations result in non-homogeneous target coalitions, and therefore satisfy solitary homogeneity.

Next, we provide a proof for the lemma used for the part of the proof of the previous theorem given in the body of the paper.

In the following proof, we consider various sets of auxiliary agents. We assume that we take new agents in every step of the constructions.

We show the statement for homogeneous coalitions of blue agents. The statement for red agents is completely symmetric, by reversing the respective roles. We use a few types of auxiliary agents with extreme preferences that have their peaks at the largest or smallest ratios, except for liking homogeneous coalitions the worst. Specifically, we consider four sets $R_x, B_x, R_y$, and $B_y$ of agents with the following preferences. Note that the sets $R_y$ and $B_y$ are only needed for the statement about red agents, but we state them for completeness.

$R_x, B_x:$     $f\succ g$ if and only if $0 < f < g$ or $f > g = 0$

$R_y, B_y:$     $f\succ g$ if and only if $1 > f > g$ or $f < g = 1$

Now, let $B_a$ be a set of blue agents such that every agent in $B_a$ has preferences satisfying $\frac 13 \succ 0 \succ \frac 12$. Suppose that $|B_a| = k$ and $B_a = \{b_{a,i}\colon i \in [k]\}$. Let $r_{x,i}\in R_x$ for $i\in [2]$ and $b_{x,i}\in B_x$ for $i \in [k + 2]$. We create a trash coalition (used to get rid of agents not needed anymore) by creating $C_a = \{r_{x,2}, b_{x,k}, b_{x,k+1}\}$. To create $C_a$, we let the blue agents of this coalition join the red agent $r_{x,2}$.

Now, we perform for any $i\in [k-1]$ the following steps (in increasing order of indices): $b_{x,i}$ joins $r_{x,1}$, then $b_{a,i}$ joins this coalition. Then, $b_{x,i}$ leaves this coalition to join $C_a \cup \{b_{x,j}\colon j\in [i-1]\}$, and finally $b_{a,i}$ joins $b_{a,k}\cup \{b_{a,j}\colon j\in [i-1]\}$. Note that these are all IS deviations. In particular, $b_{a,i}$'s deviation to join $b_{a,k}$'s coalition is feasible, because she leaves coalition $\{r_{x,1}, b_{a,i}\}$ which has a ratio of $1/2$, which is strictly worse for her than being in a homogeneous coalition. After this procedure, we have obtained the coalition $B_a$.

We prove the two hardness results by providing separate reductions for each problem in the next two lemmas.
The proofs for these two lemmas (Lemmas <ref> and <ref>) work in the same way as the proofs of Lemmas <ref> and <ref>,
except that we have to ensure appropriate ratios of red agents in each constructed initial coalition in order to guarantee, similarly as in the proofs of Lemmas <ref> and <ref>, that the preferences of the agents over ratios can be expressed in terms of preferences over initial non-singleton coalitions augmented by one or two agents of a given type (red or blue).
Instead of playing only with the size of coalitions for the design of the reductions, like in the proofs of Lemmas <ref> and <ref>, we need here to play with both the size of the coalitions and the proportion of red and blue agents within them.

ISHDG is -hard even for strict preferences.

Let us perform a reduction from (3,B2)-SAT <cit.>.
In an instance of (3,B2)-SAT, we are given a CNF propositional formula $\varphi$ where every clause $C_j$, for $1\leq  j \leq m$, contains exactly three literals and every variable $x_i$, for $1\leq i \leq p$, appears exactly twice as a positive literal and twice as a negative literal.
From such an instance, we construct an instance of a hedonic diversity game with initial partition as follows.
The proof works in the same way as the proof of Lemma <ref>.

For each $\ell^{\text{th}}$ occurrence ($\ell\in\{1,2\}$) of a positive literal $x_i$ (or negative literal $\overline{x}_i$), we create a red literal-agent $y_i^\ell$ (or a blue literal-agent $\overline{y}_i^\ell$).
All literal-agents are singletons in the initial partition $\spartition$.
Let us consider three integers $\alpha$, $\beta$ and $\gamma$ such that $(1)$ $\alpha>2m-1$, $\beta>\max\{3p-2;3p\alpha+3p-2\}$, $\gamma>\max\{12p-2;6p\beta+12p-1\}$.
For instance, we can set the following values: $\alpha=m^2$, $\beta=m^4$ and $\gamma=m^7$ (one can verify that condition $(1)$ is satisfied, especially because in a (3,B2)-SAT instance, it holds that $m\geq 4$ and $p=3/4 m$).
For each clause $C_j$, we then create $\alpha$ dummy clause-agents with among them $2j-1$ red agents.
They are all grouped within the same coalition $K_j$ in the initial partition $\spartition$.
For each literal $x_i$ (or $\overline{x}_i$), we create a red variable-agent $z_i$ (or a blue variable-agent $\overline{z}_i$) and $\beta-1$ (or $\beta -1$) dummy variable-agents with among them $3i-2$ (or $3i-2$) red agents ($z_i$ included).
They are all grouped within the same coalition $Z_i$ (or $\overline{Z_i}$) in the initial partition $\spartition$.
Finally, for each variable $x_i$, we create three coalitions in partition $\spartition$ of dummy agents $G_i^1$, $G_i^2$ and $G_i^3$ of size $i\gamma$ with among them, $6(p-i)+1$, $6(p-i)+3$, or $6(p-i)+5$ red agents, for each coalition respectively.
These dummy agents are used as a gadget for a cycle.
Although we have created many agents, the construction remains polynomial by considering reasonable values of $\alpha$, $\beta$ and $\gamma$, as previously described.

The preferences of the agents over ratios of red agents are given in Table <ref>.

Preferences of the agents in the reduced instance of Lemma <ref>, for every $1\leq i\leq p$, $1\leq j\leq m$, $\ell\in\{1,2\}$. Notation $\clauseof{x_i^\ell}$ (or $\clauseof{\overline{x}_i^\ell}$) stands for the index of the clause to which the $\ell^{\text{th}}$ occurrence of literal $x_i$ (or $\overline{x}_i$) belongs, the framed value corresponds to the ratio of the initial coalition in partition $\spartition$, and $[\dots]$ denotes an arbitrary order over the rest of the coalition ratios.

$z_i:$     $\frac{3i}{\beta+2} \succ \frac{6(p-i)+2}{i\gamma+2} \succ \frac{6(p-i)+4}{i\gamma+1} \succ \frac{6(p-i)+6}{i\gamma+2} \succ \frac{6(p-i)+6}{i\gamma+1} \succ \frac{6(p-i)+2}{i\gamma+1} \succ \frac{3i-1}{\beta+1} \succ \boxed{\frac{3i-2}{\beta}} \succ [\dots]$

$\overline{z}_i:$     $\frac{3i-2}{\beta+2} \succ \frac{6(p-i)+6}{i\gamma+2} \succ \frac{6(p-i)+3}{i\gamma+1} \succ \frac{6(p-i)+2}{i\gamma+2} \succ \frac{6(p-i)+1}{i\gamma+1} \succ \frac{6(p-i)+5}{i\gamma+1} \succ \frac{3i-2}{\beta+1} \succ \boxed{\frac{3i-2}{\beta}}  \succ [\dots]$

$y_i^\ell:$     $\frac{2\clauseof{x_i^\ell}}{\alpha+1} \succ \frac{3i}{\beta+2} \succ \frac{3i-1}{\beta+1} \succ \boxed{1} \succ [\dots]$

$\overline{y}_i^\ell:$     $\frac{2\clauseof{\overline{x}_i^\ell}-1}{\alpha+1} \succ \frac{3i-2}{\beta+2} \succ \frac{3i-2}{\beta+1} \succ \boxed{0} \succ [\dots]$

$K_j:$     $\frac{2j}{\alpha+1} \succ \frac{2j-1}{\alpha+1} \succ \boxed{\frac{2j-1}{\alpha}} \succ [\dots]$

$Z_i\setminus\{z_i\}:$     $\frac{3i}{\beta+2} \succ \frac{3i-1}{\beta+1} \succ \boxed{\frac{3i-2}{\beta}} \succ \frac{3i-3}{\beta-1} \succ [\dots]$

$\overline{Z_i}\setminus\{\overline{z}_i\}:$     $\frac{3i-2}{\beta+2} \succ \frac{3i-2}{\beta+1} \succ \boxed{\frac{3i-2}{\beta}} \succ \frac{3i-2}{\beta-1} \succ [\dots]$

$G_i^1:$     $\frac{6(p-i)+2}{i\gamma+2} \succ \frac{6(p-i)+2}{i\gamma+1} \succ \frac{6(p-i)+1}{i\gamma+1} \succ \boxed{\frac{6(p-i)+1}{i\gamma}} \succ [\dots]$

$G_i^2:$     $\frac{6(p-i)+4}{i\gamma+1} \succ \frac{6(p-i)+3}{i\gamma+1} \succ \boxed{\frac{6(p-i)+3}{i\gamma}} \succ [\dots]$

$G_i^3:$     $\frac{6(p-i)+6}{i\gamma+2} \succ \frac{6(p-i)+6}{i\gamma+1} \succ \frac{6(p-i)+5}{i\gamma+1} \succ \boxed{\frac{6(p-i)+5}{i\gamma}} \succ [\dots]$

We claim that there exists a sequence of IS deviations which leads to an IS partition iff formula $\varphi$ is satisfiable.

Suppose first that there exists a truth assignment of the variables $\phi$ that satisfies all the clauses.
Let us denote by $\ell_j$ a chosen literal-agent associated with an occurrence of a literal true in $\phi$ which belongs to clause $C_j$.
Since all the clauses of $\varphi$ are satisfied by $\phi$, there exists such a literal-agent $\ell_j$ for each clause $C_j$.
For every clause $C_j$, let literal-agent $\ell_j$ join coalition $K_j$.
These IS deviations make the chosen literal-agents reach their most preferred ratio so none of them will deviate afterwards.
For the clause-agents, they all reach either their first or second most preferred ratio but have no possibility to improve their satisfaction in the latter case so none of them will deviate afterwards neither.
Then, let all remaining literal-agents $y_i^\ell$ (or $\overline{y}_i^\ell$) deviate by joining coalition $Z_i$ (or $\overline{Z_i}$).
Since $\phi$ is a truth assignment of the variables, for each variable $x_i$, there exists a coalition $Z_i$ or $\overline{Z_i}$ that is joined by two literal-agents and thus reaches the most preferred ratio $\frac{3i}{\beta+2}$ or $\frac{3i-2}{\beta+2}$.
It follows that no member of such a newly formed coalition would move afterwards or let other agents enter the coalition: all members of $Z_i$ or $\overline{Z_i}$ get their most preferred size while the two joining literal-agents get their second most preferred size and their most preferred size is not accessible anymore (their associated clause coalition has already been joined by another literal-agent).
For each variable $x_i$, at most one coalition between $Z_i$ and $\overline{Z_i}$ may not be joined by two literal-agents and, if there is one, it must be the coalition that corresponds to the literal of variable $x_i$ that is true in $\phi$.
In such a case, we let the associated variable-agent $z_i$ or $\overline{z}_i$ deviate for joining coalition $G_i^2$, and if one literal-agent previously joined the corresponding variable-coalition $Z_i$ or $\overline{Z_i}$, she deviates to be alone.
Such a literal-agent then gets her fourth most preferred size while her most preferred ones are not accessible anymore (because the variable-agent has left the coalition and her associated clause coalition has already been joined by another literal-agent).
Moreover, such a variable-agent $z_i$ (or $\overline{z}_i$), by joining coalition $G_i^2$, gets her third most preferred size while her most preferred ones are not accessible: no two additional red (or blue) agents want to enter the initial coalition $Z_i$ (or $\overline{Z_i}$) and only one additional agent, herself, is present in the gadget associated with variable $x_i$, whereas variable-agent $z_i$ (or $\overline{z}_i$) in the gadget prefers ratios which differ by one blue agent (or red agent) from the ratio of the current coalitions.
Also, note that, by the design of the preferences, no dummy agent in the gadget has an incentive to move to another coalition.
All in all, no agent can then move in an IS deviation, and thus the reached partition is IS.

Suppose now that there exists no truth assignment of the variables that satisfies all the clauses.
That means that it is not possible that one literal-agent joins each clause coalition while two literal-agents $y_i^1$ and $y_i^2$ join coalition $Z_i$ or $\overline{y}_i^1$ and $\overline{y}_i^2$ join coalition $\overline{Z_i}$ for each variable $x_i$.
By construction of the preferences, the only agents who want to join a coalition $K_j$ are literal-agents associated with a literal belonging to clause $C_j$ and the only agents who want to join a coalition $Z_i$ (or $\overline{Z_i}$) are literal-agents $y_i^1$ and $y_i^2$ (or $\overline{y}_i^1$ and $\overline{y}_i^2$).
Moreover, since each literal-agent prefers to join clause coalitions than variable coalitions, it means that in a maximal sequence of IS deviations, all clause-agents in $K_j$ will reach one of the two most preferred ratios, $\frac{2j}{\alpha+1}$ in case a red literal-agent joined or $\frac{2j-1}{\alpha+1}$ in case a blue literal-agent joined.
In both cases, they have no incentive to deviate afterwards.
However, in such a case, there exists a variable $x_i$ such that at most one literal-agent joins coalition $Z_i$ and $\overline{Z_i}$.
It follows that both variable-agents $z_i$ and $\overline{z_i}$ have an incentive to deviate to the gadget associated with variable $x_i$ (their respective most preferred ratios $\frac{3i}{\beta+2}$ and $\frac{3i-2}{\beta+2}$ can never be reached).
Within the gadget associated with variable $x_i$, variable-agents $z_i$ and $\overline{z_i}$ are the only agents who can deviate and we necessarily reach a cycle, which is the same as described in Figure <ref> for the proof of Lemma <ref>.

Finally, we must verify that all the fractions described in the preferences with different variables are indeed different.

* For gadget coalitions, since $\gamma>12p-2$, it holds that $\frac{6(p-i)+6}{i\gamma+1}>\frac{6(p-i)+6}{i\gamma+2}>\frac{6(p-i)+5}{i\gamma}>\frac{6(p-i)+5}{i\gamma+1}>\frac{6(p-i)+4}{i\gamma+1}>\frac{6(p-i)+3}{i\gamma}>\frac{6(p-i)+3}{i\gamma+1}>\frac{6(p-i)+2}{i\gamma+1}>\frac{6(p-i)+2}{i\gamma+2}>\frac{6(p-i)+1}{i\gamma}>\frac{6(p-i)+1}{i\gamma+1}$ for every $i\in [p]$.
Moreover, it holds that $\frac{6(p-i)+6}{i\gamma+1}>\frac{6(p-(i+1)+1}{(i+1)\gamma+1}$ for every $i\in[p-1]$ so all the values associated with ratios preferred to the initial ones are different for all gadget coalitions.

* For variable coalitions, since $\beta>3p-2$, it holds that $\frac{3i}{\beta+2}>\frac{3i-1}{\beta+1}>\frac{3i-2}{\beta}>\frac{3i-2}{\beta+1}>\frac{3i-2}{\beta+2}$ for every $i\in[p]$.
Moreover, it holds that $\frac{3i}{\beta+2}<\frac{3(i+1)-2}{\beta+2}$ for every $i\in[p-1]$ so all the values associated with ratios preferred to the initial ones are different for all variable coalitions.

* For clause coalitions, since $\alpha>2m-1$, it holds that $\frac{2j-1}{\alpha+1}<\frac{2j-1}{\alpha}<\frac{2j}{\alpha+1}$ for every $j\in[m]$.
Moreover, it holds that $\frac{2j}{\alpha+1}<\frac{2(j+1)-1}{\alpha+1}$ for every $j\in [m-1]$ so all the values associated with ratios preferred to the initial ones are different for all clause coalitions.

It remains to check that the ratios associated with clause, variable or gadget coalitions do not interfere with each other.
Since $\gamma>6p\beta+12p-1$, it holds that the highest reachable ratio associated with a gadget coalition is smaller than the smallest reachable ratio associated with a variable coalition, i.e., $\frac{6p}{\gamma+1}<\frac{1}{\beta+2}$.
Since $\beta>3p\alpha+3p-2$, it holds that the highest reachable ratio associated with a variable coalition is smaller than the smallest reachable ratio associated with a clause coalition, i.e., $\frac{3p}{\beta+2}<\frac{1}{\alpha+1}$.
Therefore, all the reachable ratios are indeed different for clause, variable and gadget coalitions.
It follows that the previously described deviations are indeed the only possible ones and hence no sequence of IS deviations can reach an IS partition.

ISHDG is -hard even for strict preferences.

For this purpose, we prove the -hardness of the complement problem, which asks whether there exists a cycle of IS deviations.
Let us perform a reduction from (3,B2)-SAT <cit.>.
In an instance of (3,B2)-SAT, we are given a CNF propositional formula $\varphi$ where every clause $C_j$, for $1\leq  j \leq m$, contains exactly three literals and every variable $x_i$, for $1\leq i \leq p$, appears exactly twice as a positive literal and twice as a negative literal.
From such an instance, we construct an instance of a hedonic diversity game with initial partition as follows.
The proof works in the same way as the proof of Lemma <ref>.

For each $\ell^{\text{th}}$ occurrence ($\ell\in\{1,2\}$) of a positive literal $x_i$ (or negative literal $\overline{x}_i$), we create a red literal-agent $y_i^\ell$ (or a blue literal-agent $\overline{y}_i^\ell$).
We create another red agent $t$.
All these agents are singletons in the initial partition $\spartition$.
Let us consider four integers $\alpha$, $\beta_1^+$, $\beta_1^-$ and $\beta_2$ such that $(1)$ $\alpha>6m+2$, $\beta_1^+>\max\{4p-2;(2p+1)\alpha+4p\}$, $\beta_1^->\max\{4p-2;2p\beta_1^++2p-2\}$ and $\beta_2>\max\{3p-2;3p\beta_1^-+4p\}$.
For instance, we can set the following values: $\alpha=m^3$, $\beta_1^+=m^5$, $\beta_1^-=m^7$ and $\beta_2=m^9$ (one can verify that condition $(1)$ is satisfied, especially because in a (3,B2)-SAT instance, it holds that $m\geq 4$ and $p=3/4 m$).
For each clause $C_j$, we then create $\alpha$ dummy clause-agents with among them $3j-2$ red agents.
They are all grouped within the same coalition $K_j$ in the initial partition $\spartition$.
We also create $\alpha$ dummy agents with among them $3m+1$ red agents, they are all grouped within the same coalition $K_{m+1}$ in initial partition $\spartition$.
For each first occurrence of literal $x_i$ (or $\overline{x}_i$), we create $\beta_1^+$ (or $\beta_1^-$) dummy variable agents with among them $2i-1$ red agents, they are all grouped within the same coalition $Y_i^1$ (or $\overline{Y_i^1}$) in the initial partition $\spartition$.
Finally, for each second occurrence of literal $x_i$ (or $\overline{x}_i$), we create $\beta_2$ dummy variable agents with among them $3i-2$ red agents, they are all grouped within the same coalition $Y_i^2$ (or $\overline{Y_i^2}$) in the initial partition $\spartition$.
Although we have created many agents, the construction remains polynomial by considering reasonable values of $\alpha$, $\beta^+_1$, $\beta^-_1$ and $\beta_2$, as previously described.

The preferences of the agents over coalition ratios are given in Table <ref>.

Preferences of the agents in the reduced instance of Lemma <ref>, for every $1\leq i\leq p$, $1\leq i' < p$, $1\leq j\leq m+1$, $\ell\in\{1,2\}$. Notation $\clauseof{x_i^\ell}$ (or $\clauseof{\overline{x}_i^\ell}$) stands for the index of the clause to which the $\ell^{\text{th}}$ occurrence of literal $x_i$ (or $\overline{x}_i$) belongs, the framed value corresponds to the ratio of the initial coalition in partition $\spartition$, and $[\dots]$ denotes an arbitrary order over the rest of the coalition ratios.

$y_i^1:$     $\frac{3\clauseof{x_i^1}}{\alpha+2} \succ \frac{3\clauseof{x_i^1}-1}{\alpha+2} \succ \frac{3(\clauseof{x_i^1}+1)}{\alpha+2} \succ \frac{3(\clauseof{x_i^1}+1)-1}{\alpha+2} \succ \frac{3(\clauseof{x_i^1}+1)-1}{\alpha+1} \succ \frac{3\clauseof{x_i^1}-1}{\alpha+1} \succ \frac{2i+1}{\beta_1^++2} \succ \frac{2i}{\beta_1^++2} \succ \frac{3i}{\beta_2+2} \succ \frac{3i-1}{\beta_2+1} \succ \frac{2i}{\beta_1^++1} \succ  \boxed{1} \succ [\dots]$

$y_{i'}^2:$     $\frac{3\clauseof{x_{i'}^1}}{\alpha+2}  \succ \frac{3\clauseof{x_{i'}^1}-1}{\alpha+2} \succ \frac{3(\clauseof{x_{i'}^1}+1)}{\alpha+2} \succ \frac{3(\clauseof{x_{i'}^1}+1)-1}{\alpha+2} \succ \frac{3(\clauseof{x_{i'}^1}+1)-1}{\alpha+1} \succ \frac{3\clauseof{x_{i'}^1}-1}{\alpha+1} \succ  \frac{3i'}{\beta_2+2} \succ \frac{2(i'+1)+1}{\beta_1^++2} \succ \frac{2(i'+1)}{\beta_1^++2} \succ \frac{2(i'+1)}{\beta_1^++1}  \succ \frac{2(i'+1)+1}{\beta_1^-+2} \succ$
$\frac{2(i'+1)}{\beta_1^-+2}  \succ \frac{2(i'+1)}{\beta_1^-+1} \succ \frac{3i'-1}{\beta_2+1} \succ \boxed{1} \succ [\dots]$

$y_p^2:$     $\frac{3\clauseof{x_p^1}}{\alpha+2} \succ \frac{3\clauseof{x_p^1}-1}{\alpha+2} \succ \frac{3(\clauseof{x_p^1}+1)}{\alpha+2} \succ \frac{3(\clauseof{x_p^1}+1)-1}{\alpha+2} \succ \frac{3(\clauseof{x_p^1}+1)-1}{\alpha+1} \succ \frac{3\clauseof{x_p^1}-1}{\alpha+1} \succ \frac{3p}{\beta_2+2} \succ \frac{3}{\alpha+2} \succ \frac{2}{\alpha+2}  \succ \frac{2}{\alpha+1} \succ \frac{3p-1}{\beta_2+1} \succ  \boxed{1} \succ [\dots]$

$\overline{y}_i^1:$     $\frac{3\clauseof{\overline{x}_i^1}-1}{\alpha+2} \succ \frac{3\clauseof{\overline{x}_i^1}-2}{\alpha+2} \succ \frac{3(\clauseof{\overline{x}_i^1}+1)-1}{\alpha+2} \succ \frac{3(\clauseof{\overline{x}_i^1}+1)-2}{\alpha+2} \succ
\frac{3(\clauseof{\overline{x}_i^1}+1)-2}{\alpha+1} \succ \frac{3\clauseof{\overline{x}_i^1}-2}{\alpha+1} \succ \frac{2i}{\beta_1^-+2} \succ \frac{2i-1}{\beta_1^-+2} \succ \frac{3i-2}{\beta_2+2} \succ \frac{3i-2}{\beta_2+1} \succ \frac{2i-1}{\beta_1^-+1} \succ  \boxed{0} \succ [\dots]$

$\overline{y}_{i'}^2:$     $\frac{3\clauseof{\overline{x}_{i'}^1}-1}{\alpha+2} \succ \frac{3\clauseof{\overline{x}_{i'}^1}-2}{\alpha+2} \succ \frac{3(\clauseof{\overline{x}_{i'}^1}+1)-1}{\alpha+2} \succ \frac{3(\clauseof{\overline{x}_{i'}^1}+1)-2}{\alpha+2} \succ \frac{3(\clauseof{\overline{x}_{i'}^1}+1)-2}{\alpha+1} \succ \frac{3\clauseof{\overline{x}_{i'}^1}-2}{\alpha+1} \succ \frac{3i'-2}{\beta_2+2} \succ \frac{2(i'+1)}{\beta_1^++2}  \succ \frac{2(i'+1)-1}{\beta_1^++2}  \succ \frac{2(i'+1)-1}{\beta_1^++1} \succ \frac{2(i'+1)}{\beta_1^-+2} \succ$
$ \frac{2(i'+1)-1}{\beta_1^-+2} \succ \frac{2(i'+1)-1}{\beta_1^-+1} \succ \frac{3i'-2}{\beta_2+1} \succ  \boxed{0} \succ [\dots]$

$\overline{y}_p^2:$     $\frac{3\clauseof{\overline{x}_p^1}-1}{\alpha+2} \succ \frac{3\clauseof{\overline{x}_p^1}-2}{\alpha+2} \succ \frac{3(\clauseof{\overline{x}_p^1}+1)-1}{\alpha+2} \succ \frac{3(\clauseof{\overline{x}_p^1}+1)-2}{\alpha+2} \succ \frac{3(\clauseof{\overline{x}_p^1}+1)-2}{\alpha+1} \succ \frac{3\clauseof{\overline{x}_p^1}-2}{\alpha+1} \succ \frac{3p-2}{\beta_2+2} \succ \frac{2}{\alpha+2} \succ \frac{1}{\alpha+2} \succ \frac{1}{\alpha+1} \succ \frac{3p-2}{\beta_2+1} \succ  \boxed{0} \succ [\dots]$

$t:$     $\frac{3m+3}{\alpha+2} \succ \frac{3m+2}{\alpha+2} \succ \frac{3}{\beta_1^++2} \succ \frac{2}{\beta_1^-+2} \succ \frac{2}{\beta_1^++1} \succ \frac{2}{\beta_1^-+1} \succ \frac{3m+2}{\alpha+1} \succ \boxed{1} \succ [\dots]$

$K_j:$     $\frac{3j}{\alpha+2} \succ \frac{3j-1}{\alpha+2} \succ \frac{3j-2}{\alpha+2} \succ \frac{3j-1}{\alpha+1} \succ \frac{3j-2}{\alpha+1} \succ \boxed{\frac{3j-2}{\alpha}} \succ [\dots]$

$Y_i^1:$     $\frac{2i+1}{\beta_1^++2} \succ \frac{2i}{\beta_1^++2} \succ \frac{2i}{\beta_1^++1} \succ \frac{2i-1}{\beta_1^++1} \succ \boxed{\frac{2i-1}{\beta_1^+}} \succ [\dots]$

$\overline{Y_i^1}:$     $\frac{2i}{\beta_1^-+2} \succ \frac{2i-1}{\beta_1^-+2} \succ \frac{2i}{\beta_1^-+1} \succ \frac{2i-1}{\beta_1^-+1} \succ \boxed{\frac{2i-1}{\beta_1^-}} \succ [\dots]$

$Y_i^2:$     $\frac{3i}{\beta_2+2} \succ \frac{3i-1}{\beta_2+1} \succ \boxed{\frac{3i-2}{\beta_2}} \succ [\dots]$

$\overline{Y_i^2}:$     $\frac{3i-2}{\beta_2+2} \succ \frac{3i-2}{\beta_2+1} \succ \boxed{\frac{3i-2}{\beta_2}} \succ [\dots]$

We claim that there exists a cycle of IS deviations iff formula $\varphi$ is satisfiable.
We omit the formal proof of equivalence which follows exactly the same arguments as the proof of Lemma <ref> with even the same name of agents and fixed coalitions.
When given a truth assignment of the variables which satisfies formula $\varphi$, it is easy to see that the cycle described in the first part of the proof of Lemma <ref> can also occur in this instance (see Figure <ref> for an example of such a cycle), proving the if part.
For the only if part, the same arguments as the ones given in the second part of the proof of Lemma <ref> also hold, except that we need to adapt to the context of evaluations of coalitions based on red agent ratios.
Instead of speaking about agents who prefer one or two additional agents, here we need to speak about agents who prefer one or two red or blue additional agents where, in our construction, literal-agents related to positive literals $x_i$ are red agents and literal-agents related to negative literals $\overline{x}_i$ are blue agents.
This difference is already reflected in the construction of the preferences of the agents.
Indeed, when in our cycle we want deviating literal-agents that correspond to the same literal, the red/blue type is fixed in the preferences of the agents (e.g., we want that only literal-agents $y_i^1$ and $y_i^2$, who are red agents, can join the coalition of dummy variable agents $Y_i^2$, therefore the preferences of the members of $Y_i^2$ are constructed in such a way that they can only accept up to two additional red agents).
Alternatively, when the type of the deviating literal-agents is not known a priori in the cycle, we specify all possible new ratios in the preferences, in order to take into account every possible combination of types for deviating agents.
It is the case, e.g., for the preferences of the coalitions of dummy clause agents $K_j$ because we do not know a priori which literal will satisfy the corresponding clause.
Therefore, for the preferences of $K_j$, we specify preferences for two additional literal-agents which can be of any type, by nevertheless ensuring that two additional agents is more preferred than only one (in order to come back to the same idea as in the proof of Lemma <ref>).
Even if an arbitrary preference ranking is chosen between coalition ratios that correspond to the same number of additional agents, this does not impact the proof because only one of these ratios can be reached, depending on the type of agent who enters the coalition.

The only point that must be additionally checked is that all the fractions described in the preferences with different variables are indeed different.

Suppose first that formula $\varphi$ is satisfiable by a truth assignment of the variables denoted by $\phi$.
Let us denote by $\ell_j$ a chosen literal-agent associated with an occurrence of a literal true in $\phi$ which belongs to clause $C_j$.
Since all the clauses of $\varphi$ are satisfied by $\phi$, there exists such a literal-agent $\ell_j$ for each clause $C_j$.
Now let us denote by $z_i^1$ and $z_i^2$ the literal-agents associated with the two occurrences of the literal of variable $x_i$ which is false in $\phi$.