Reaching Individually Stable Coalition Structures

Felix Brandt

Department of Informatics, Technical University of Munich

Martin Bullinger

Department of Informatics, Technical University of Munich

Anaëlle Wilczynski

MICS, CentraleSupélec, Université Paris-Saclay

The formal study of coalition formation in multi-agent systems is typically realized in the framework of hedonic games, which originate from economic theory. The main focus of this branch of research has been on the existence and the computational complexity of deciding the existence of coalition structures that satisfy various stability criteria. The actual process of forming coalitions based on individual behavior has received little attention. In this paper, we study the convergence of simple dynamics leading to stable partitions in a variety of established classes of hedonic games including anonymous, dichotomous, fractional, and hedonic diversity games. The dynamics we consider is based on individual stability: an agent will join another coalition if she is better off and no member of the welcoming coalition is worse off.

Our results are threefold. First, we identify conditions for the (fast) convergence of our dynamics. To this end, we develop new techniques based on the simultaneous usage of multiple intertwined potential functions and establish a reduction uncovering a close relationship between anonymous hedonic games and hedonic diversity games. Second, we provide elaborate counterexamples determining tight boundaries for the existence of individually stable partitions. Third, we study the computational complexity of problems related to the coalition formation dynamics. In particular, we settle open problems suggested by <cit.>, <cit.>, and <cit.>.

<concept_desc>Computing methodologies Multi-agent systems</concept_desc>
<concept_desc>Theory of computation Design and analysis of algorithms</concept_desc>

[500]Computing methodologies Multi-agent systems
[500]Theory of computation Design and analysis of algorithms

§ INTRODUCTION

Coalitions and coalition formation are central concerns in the study of multi-agent systems as well as cooperative game theory.
Typical real-world examples include individuals joining clubs or societies such as orchestras, choirs, or sport teams, countries organizing themselves in international bodies like the European Union (EU) or the North Atlantic Treaty Organization (NATO), students living together in shared flats, or employees forming unions.
The formal study of coalition formation is often realized using so-called hedonic games, which originate from economic theory. In these games, the central goal is to identify coalition structures (henceforth partitions) that satisfy various stability criteria based on the agents' preferences over coalitions, that is, over subsets of agents. A partition is defined to be stable if single agents or groups of agents cannot gain by deviating from the current partition by means of leaving their current coalition and joining another coalition, or forming a new one. The permitted deviations can be constrained by other agents, for instance by means of contracts with an existing coalition or by the necessity of consent when admitting a new member. These constraints lead to a large body of stability concepts <cit.>. Two important and well-studied questions in this context concern the existence of stable partitions in restricted classes of hedonic games and the computational complexity of finding a stable partition. However, stability is only concerned with the end-state of the coalition formation process and ignores how these desirable partitions can actually be reached. Essentially, an underlying assumption in most of the existing work is that there is a central authority that receives the preferences of all agents, computes a stable partition as an end-state, and has the means to establish this partition among the agents. By contrast, our work focuses on simple dynamics, where starting with some partition (e.g., the partition of singletons), agents deliberately decide to join and leave coalitions based on their individual preferences. We study the convergence of such a process and the stable partitions that can arise from it. For example, in some cases the only partition satisfying a certain stability criterion is the grand coalition consisting of all agents, while the dynamics based on the agents' individual decisions can never reach this partition and is doomed to cycle.

The dynamics we consider is based on individual stability, a natural notion of stability going back to <cit.>: an agent will join another coalition if she is better off and no member of the welcoming coalition is worse off.
Individual stability is suitable to model the situations mentioned above. For instance, by Article 49 of the Treaty on European Union, admitting new members to the EU requires the unanimous approval of the current members. Similarly, by Article 10 of their founding treaty, unanimous agreement of all parties is necessary to become a member of the NATO. Also, for joining a choir or orchestra it is often necessary to audition successfully, and joining a shared flat requires the consent of all current residents.
This distinguishes individual stability from Nash stability, which ignores the consent of members of the welcoming coalition.

The analysis of coalition formation processes provides more insight in the natural behavior of agents and the conditions that are required to guarantee that desirable social outcomes can be reached without a central authority.
Similar dynamic processes have been studied for matchings, which can be seen as a special domain of coalition formation where only coalitions of size 2 are allowed <cit.>.
More recently, dynamics of coalition formation have also come under scrutiny in the context of hedonic games <cit.>.
While coalition formation dynamics
are an object of study worthy for itself, they can also be used as a means to design algorithms for the computation of stable outcomes, and have been implicitly used for this purpose before. For example, the algorithm by <cit.> for finding an individually stable partition in hedonic diversity games predefines a promising partition and then reaches an individually stable partition by running the dynamics from there. Similarly, the algorithm by <cit.> for finding an individually stable partition on games with ordered characteristics, a generalization of anonymous hedonic games, runs the dynamics using a specific sequence of deviations starting from the singleton partition.

In addition, the study of dynamics offers a more fine-grained view in games where the static concepts of stability only gives limited information. We will see that there exist classes of hedonic games in which individually stable partitions are guaranteed to exist but dynamics cycle can be doomed to cycle when executing from specific starting configurations. Two important examples are fractional hedonic games with non-negative weights and hedonic diversity games. For the former, the grand coalition is individually stable and for the latter, individually stable partitions always exist <cit.>. By contrast, our results show that dynamics can behave very differently, illustrating that dynamics can offer a broader picture on stability.

In many cases, the convergence of the dynamics of deviations follows from the existence of
potential functions, whose local optima form individually stable states.
Generalizing a result by <cit.>, <cit.> has shown via a potential function argument that an individually stable—and even a Nash stable—partition always exists in subset-neutral hedonic games, a generalization of symmetric additively-separable hedonic games.
Using the same potential function, it can straightforwardly be shown that the dynamics converge.[By inclusion, convergence also holds for symmetric additively-separable hedonic games. Symmetry is essential for this result to hold since an individually stable partition may not exist in additively-separable hedonic games, even under additional restrictions <cit.>.]

Since the class of subset-neutral hedonic games include symmetric additively-separable hedonic games, convergence is also guaranteed for the latter.[Symmetry is essential for this
result to hold since an IS partition may not exist in additively-separable hedonic games, even under additional restrictions <cit.>.]

Another example are hedonic games with the common ranking property, a class of hedonic games where preferences are induced by a common global order <cit.>. Here, the dynamics associated with core-stable deviations is known to converge to a core-stable partition that is also Pareto-optimal[A partition is Pareto-optimal if every partition preferred to this partition by some agent is worse for another agent.], thanks to a potential function argument <cit.>.
The same potential function implies convergence of the dynamics based on individual stability.

Note that this positive result cannot be extended to NS-deviations since an NS partition may even not exist (the simplest example is an instance with two agents $1$ and $2$ and the following preferences: $1:\{1,2\}\succ\{1\}$ and $2:\{2\}\succ\{1,2\}$).

In this paper, we study the coalition formation dynamics based on individual stability for a variety of classes of hedonic games, including anonymous hedonic games (AHGs), hedonic diversity games (HDGs), fractional hedonic games (FHGs), and dichotomous hedonic games (DHGs).
Computational questions related to the dynamics are investigated in two ways: the existence of a path to stability, that is the existence of a sequence of deviations that leads to a stable state, and the guarantee of convergence where every sequence of deviations should lead to a stable state.
The former gives an optimistic view on the behavior of the dynamics and may be used to motivate the choice of reachable stable partitions (we can exclude “artificial” stable partitions that may never naturally form).
If such a sequence can be computed efficiently, it enables a central authority to coordinate the deviations towards a stable partition.
On the other hand, guaranteed convergence allows agents to reach a stable outcome without further coordination. This provides strong stability guarantees under more pessimistic assumptions on the agents' behavior. Whether we obtain positive or negative results concerning the convergence of the dynamics depends on various dimensions of the input concerning the initial partition, restrictions imposed on the agents' preferences, and the selection of deviations. We identify clear boundaries to computational tractability based on these specifications.
Our main results are summarized as follows.

* In AHGs, the dynamics is guaranteed to converge for (naturally) single-peaked preferences.
On the other hand, we provide a 15-agent example showing the non-existence of individually stable partitions in general AHGs.
The previously known smallest counterexample by <cit.> requires 63 agents and the existence of smaller examples was an acknowledged open problem <cit.>.

* We provide an elaborate reduction for HDGs that eventually establishes a close relationship to AHGs and show guaranteed convergence of the dynamics for strict and naturally singled-peaked preferences when starting from the and agents' deviations satisfy a weak constraint.
In contrast to empirical evidence reported by <cit.>, we show that all of the above assumptions are essential for the convergence result. In particular, cycling of the dynamics is possible if the starting partition is the and preferences are restricted to be strict and naturally single-peaked.

* In FHGs, the dynamics is guaranteed to converge for simple symmetric preferences when starting from the or when preferences form an acyclic digraph.
On the other hand, we show that individually stable partitions need not exist in general symmetric FHGs,
which was left as an open problem by <cit.>.

* For each of the above classes and DHGs, we identify computational boundaries. In particular, we show that deciding whether there is a sequence of deviations leading to an individually stable partition is -hard while deciding whether all sequences of deviations lead to an individually stable partition is -hard. Some of these results hold under preference restrictions and even when starting from the singleton partition.

For the sake of readability, some (parts of) proofs are omitted from the body of the paper, they can nevertheless be found in the appendix.

§ PRELIMINARIES AND MODEL

Let $N=[n]=\{1,\dots,n\}$ be a set of $n$ agents.
The goal of a coalition formation problem is to partition the agents into different disjoint coalitions according to their preferences.
Formally, a solution is a partition of $N$, i.e., a subset $\partition\subseteq 2^N$ such that $\bigcup_{C\in \partition} C = N$, and for every pair $C,D\in \partition$, it holds that $C = D$ or $C\cap D = \emptyset$. An element of a partition is called coalition, and given a partition $\partition$, we denote by $\partition(i)$ the coalition containing agent $i$.
Two prominent partitions are the  $\partition$ given by $\partition(i)=\{i\}$ for every agent $i\in N$, and the grand coalition $\partition$ given by $\partition=\{N\}$.

Since we focus on dynamics of deviations, we assume that there exists an initial partition $\spartition$, which could be a natural initial state (such as the singleton partition) or the outcome of a previous coalition formation process.

§.§ Classes of Hedonic Games

In a hedonic game, the agents only express preferences over the coalitions to which they belong, i.e., there are no externalities.
Let $\N_i$ denote all possible coalitions containing agent $i$, i.e., $\N_i=\{C\subseteq N: i\in C\}$.
A hedonic game is defined by a tuple $(N,(\succsim_i)_{i\in N})$ where $\succsim_i$ is a weak order over $\N_i$ which represents the preferences of agent $i$, i.e., $C\succ_i C'$ means that agent $i$ strictly prefers coalition $C$ to coalition $C'$, and $C\sim_i C'$ means that agent $i$ is indifferent between coalitions $C$ and $C'$.
Since $|\N_i|=2^{n-1}$, the preferences
are rarely given explicitly, but rather in some concise representation.
These representations give rise to several classes of hedonic games:

* Subset-neutral hedonic games <cit.>: The preferences of the agents for a coalition are separable according to a global evaluation of every subcoalition to which they belong, i.e., there exists a global utility function $\util:2^N\setminus\{\emptyset\}\rightarrow\mathbb{R}$ such that $\partition(i)\succsim_i\partition'(i)$ iff $\sum_{C\subseteq\partition(i),\,i\in C}\util(C)\geq\sum_{C\subseteq\partition'(i),\,i\in C}\util(C)$ for every agent $i$.
An important class of such games are symmetric additively-separable hedonic games.

* Hedonic games with common ranking property <cit.>: The agents have correlated preferences in the sense that there exists a global weak order $\unrhd$ over all coalitions $2^N\setminus\{\emptyset\}$ such that $\partition(i)\succsim_i\partition'(i)$ iff $\partition(i)\unrhd\partition'(i)$ holds for every agent $i\in N$.

* Anonymous hedonic games (AHGs) <cit.>: The agents only care about the size of the coalition they belong to, i.e.,
for each agent $i\in N$, there exists a weak order $\succsim_i^S$ over integers in $[n]$ (superscript $S$ for sizes) such that $\partition(i) \succsim_i \partition'(i)$ iff $|\partition(i)| \succsim_i^S |\partition'(i)|$.

* Hedonic diversity games (HDGs) <cit.>: The agents are divided into two different types (or colors). We call them red and blue agents and they are represented by the subsets $R\subseteq N$ and $B\subseteq N$, respectively, such that $N=R\cup B$ and $R\cap B = \emptyset$.
Each agent only cares about the proportion of red agents present in her own coalition, i.e., for each agent $i\in N$, there exists a weak order $\succsim_i^F$ over $\{\frac{p}{q}:p\in [|R|]\cup\{0\}, q\in[n]\}$ (superscript $F$ for fractions) such that $\partition(i) \succsim_i \partition'(i)$ iff $\frac{|R\cap \partition(i)|}{|\partition(i)|} \succsim_i^F \frac{|R\cap \partition'(i)|}{|\partition'(i)|}$.[To keep the notation concise, we abuse notation by omitting the superscripts of $\succsim_i^S$ and $\succsim_i^F$ when they are clear from the context. Hence, $\succsim_i$ may also denote agent $i$'s preference order over coalition sizes in case of an AHG, or over fractions in case of an HDG.]

* Fractional Hedonic Games (FHGs) <cit.>: The agents evaluate a coalition by assessing how much they like each of its members on average, i.e.,
for each agent $i$, there exists a utility function $\util_i:N\rightarrow\mathbb{R}$ where $\util_i(i)=0$ such that $\partition(i)\succsim_i\partition'(i)$ iff $\frac{\sum_{j\in \partition(i)}\util_i(j)}{|\partition(i)|}\geq \frac{\sum_{j\in \partition'(i)}\util_i(j)}{|\partition'(i)|}$.
An FHG can be represented by a weighted directed graph
$G=(N,E)$ where, for the sake of readability, only non-null utilities are mentioned, i.e., $(i,j)\in E$ iff $\util_i(j)\neq 0$, and the weight of an arc $(i,j)\in E$ is equal to $\util_i(j)$.
An FHG is symmetric if $\util_i(j)=\util_j(i)$ for every pair of agents $i$ and $j$; since two opposite arcs have the same weight,
the representation by a graph can be simplified by directly considering a weighted
undirected graph $G=(N,E)$ with weights $\util(i,j)$ on each edge $\{i,j\}\in E$.
An FHG is simple if $\util_i:N\rightarrow\{0,1\}$ for every agent $i$; since all arcs have the same weight, the representation by a graph can be simplified by directly considering an unweighted directed graph $G=(N,E)$ where $(i,j)\in E$ iff $\util_i(j)=1$.
We say that an FHG is simple asymmetric if, for every pair of agents $i$ and $j$, $\util_i(j)\in\{0,1\}$ and $\util_i(j)=1$ implies $\util_j(i)=0$, i.e., it can be represented by an asymmetric directed graph.

* Dichotomous hedonic games (DHGs): The agents only approve or disapprove coalitions,
i.e., for each agent $i$ there exists a utility function $\util_i:\N_i\rightarrow \{0,1\}$ such that $\partition(i)\succsim_i\partition'(i)$ iff $\util_i(\partition(i))\geq \util_i(\partition'(i))$.
When the preferences are represented by a propositional formula, such games are called Boolean hedonic games <cit.>.

An anonymous game (or hedonic diversity game) is generally single-peaked if there exists a linear order $>$ over integers in $[n]$ (or over ratios in $\{\frac{p}{q}:p\in [|R|]\cup \{0\}, q\in[n]\}$) such that for each agent $i\in N$ and each triple of integers $x,y,z\in [n]$ (or $x,y,z\in \{\frac{p}{q}:p\in |R|\cup \{0\}, q\in[n]\}$) with $x>y>z$ or $z>y>x$, $x\succ_i^S y$ implies $y \succsim_i^S z$ (or $x\succ_i^F y$ implies $y \succsim_i^F z$).
The obvious linear order $>$ that comes to mind is, of course, the natural order over integers (or over rational numbers). We refer to such games as naturally single-peaked.
Clearly, a naturally single-peaked preference profile is generally single-peaked but the converse is not true.

Up to our best knowledge, most papers on hedonic games only use naturally single-peaked preferences as single-peaked preferences <cit.>, since they deal with preferences over integers or fractions.
We have introduced generally single-peaked preferences, by considering any type of given order over integers or fractions, in the spirit of the initial definition of <cit.> for social choice, where alternatives do not have an inherent order.
By generalizing the single-peaked notion on hedonic games, we aim to capture the frontier of tractability with respect to this concept and thus strengthen our results.

To improve the presentation when we display preferences for a large number of agents, we also write them in the form $i \colon X \succ Y \succ Z$, where $i\in N$ is an agent, and $X$, $Y$, and $Z$ are coalitions, or depending on the context, integers (representing sizes of coalitions in AHGs) or rational numbers (representing fractions in HDGs).
If there are multiple agents $C\subseteq N$ with identical, we also denote there preferences in the form $C \colon X \succ Y \succ Z$.
Note that we usually do not fully specify preferences in this notation, but focus on the relevant part of the preferences which affects a certain example or proof.

§.§ Dynamics of Individually Stable Deviations

Starting from the initial partition, agents can leave and join coalitions in order to improve their well-being.
We focus on unilateral deviations, which occur when a single agent decides to move from one coalition to another.
A unilateral deviation performed by agent $i$ transforms a partition $\partition$ into a partition $\partition'$
where $\pi(i)\neq\pi'(i)$ and, for all agents $j\neq i$, it holds that $\pi(j)\setminus\{i\} = \pi'(j)\setminus\{i\}$.

Since agents are assumed to be rational, agents only engage in a unilateral deviation if it makes them better off, i.e., $\partition'(i)\succ_i \partition(i)$.
Any partition in which no such deviation is possible is called Nash stable (NS).

This type of deviation can be refined by additionally requiring that no agent in the welcoming coalition is worse off when agent $i$ joins. Formally,
a unilateral deviation performed by agent $i$ who moves from coalition $\partition(i)$ to $\partition'(i)$ is an IS deviation if $\partition'(i)\succ_i \partition(i)$ and $\partition'(i)=\partition'(j)\succsim_j \partition(j)$ for all agents $j\in\partition'(i)$.
A partition in which no IS deviation is possible is called individually stable (IS).
Clearly, an NS partition is also IS.[It is possible to weaken the notion of individual stability even further by also requiring that no member of the former coalition of agent $i$ is worse off. The resulting stability notion is called contractual individual stability and guarantees convergence of our dynamics.]
In this article, we focus on dynamics based on IS deviations.
By definition, all terminal states of the dynamics have to be IS partitions.

We are mainly concerned with whether sequences of IS deviations can reach or always reach an IS partition.
If there exists a sequence of IS deviations leading to an IS partition, i.e., a path to stability, then although the agents perform myopic deviations, they can optimistically reach (or can be guided towards) a stable partition.
The corresponding decision problem is described as follows.

IS[HG]Instance of a particular class of hedonic games [HG], initial partition $\spartition$Does there exist a sequence of IS deviations starting from $\spartition$ leading to an IS partition?

In order to provide some guarantee, we also examine whether all sequences of IS deviations terminate.  Whenever this is the case, we say that the dynamics converges.
The corresponding decision problem is described below.

IS[HG]Instance of a particular class of hedonic games [HG], initial partition $\spartition$Does every sequence of IS deviations starting from $\spartition$ reach an IS partition?

We mainly investigate this problem via the study of its complement: given a hedonic game and an initial partition, does there exist a sequence of IS deviations that cycles?

A common idea behind hardness reductions concerning these two problems is to exploit the existence of instances without an IS partition or instances which allow for cycling starting from a certain partition. These can be used to create prohibitive subconfigurations in reduced instances.

§ ANONYMOUS HEDONIC GAMES

<cit.> showed that IS partitions always exist in AHGs under naturally single-peaked preferences, and proved that this does not hold under general preferences, by means of a 63-agent counterexample. Here, we provide a counterexample that only requires 15 agents and additionally satisfies general single-peakedness. Note that smaller counterexamples were repeatedly asked for in the literature <cit.>.

There may not exist an IS partition in AHGs even when $n=15$ and the agents have strict and generally single-peaked preferences.

Let us consider an AHG with 15 agents with the following (incompletely specified) preferences ([…] denotes an arbitrary order over the remaining coalition sizes). The preferences for agents $5$ through $15$ are identical.

$1:$     $2$     $\succ$     $3$     $\succ$     $13$     $\succ$     $12$     $\succ$     $1$     $\succ$     $[\dots]$

$2:$     $13$     $\succ$     $3$     $\succ$     $2$     $\succ$     $1$     $\succ$     $12$     $\succ$     $[\dots]$

$3,~4:$     $3$     $\succ$     $2$     $\succ$     $1$     $\succ$     $[\dots]$

$5,\dots,15:$     $13$     $\succ$     $12$     $\succ$     $15$     $\succ$     $14$     $\succ$     $11$     $\succ$     $10$     $\succ$     $\dots$     $\succ$     $1$

These preferences can be completed to be generally single-peaked with respect to axis $1>2>3>13>12>15>14>11>10>\dots>4$.

Note that in an IS partition,

* agents $3$ and $4$ are in a coalition of size at most 3: Otherwise, they prefer to deviate to be alone.

* agents $5$ to $15$ are in the same coalition:  Suppose, for the sake of contradiction, that agents $5$ to $15$ are not in the same coalition.
By $(i)$, at most two of them are with agent $3$ and at most two of them with agent $4$.
Agents $1$ and $2$ cannot be in a coalition of size $12$ or $13$ unless at least $10$ of the $11$ agents $5$ to $15$ are with them (agents $3$ and $4$ cannot be in such a big coalition by $(i)$). In this case, any remaining agent from $5$ to $15$ would be with them because she would join them, otherwise. Hence, the assertion is true.
Therefore, we may assume that agents $1$ and $2$ are not in a coalition of size larger than $3$. Otherwise, they would deviate to be alone.
It follows that at most two agents from $\{5,\dots,15\}$ are with agent $1$ and at most two of them with agent $2$.
Then, in the worst case, there remain only three agents within $\{5,\dots,15\}$ who are not in a coalition with agents $1$, $2$, $3$, or $4$.
These three agents cannot enter into the other coalitions but they prefer to group together, forming a coalition of size three.
Afterwards, all the agents from $\{5,\dots,15\}$ that are in coalitions with agents $1$, $2$, $3$ or $4$ will deviate to join them because they prefer to be in bigger coalitions, and they can benefit from a coalition of size at least four by joining these remaining agents, whereas they are blocked in a coalition of size at most three, a contradiction.

* agents $3$ and $4$ are in the same coalition: Suppose for the sake of contradiction that agents $3$ and $4$ are not in the same coalition.
By $(i)$, none of them can belong to the big coalition containing the agents $5$ to $15$, which exists according to $(ii)$.
Moreover, if they are both alone, then they have an incentive to group together, contradicting the stability.
Therefore, at least one of them must form a coalition with agents $1$ or $2$.

If agents $1$ and $2$ are both with agent $3$ (or $4$) and agent $4$ (or $3$) is alone, then agent $1$ has an incentive to leave the coalition $\{1,2,3\}$ (or $\{1,2,4\}$) to join agent $4$ (or $3$), contradicting the stability.
Now, consider the case where one of agents $3$ and $4$, say agent $4$, is alone. If agent $3$ forms a coalition with agent $2$, then agent $4$ would join them by an IS deviation. If agent $3$ forms a coalition with agent $1$, then agent $2$ is in a coalition of size $12$ or size $1$ and would join agent $4$ by an IS deviation.

Therefore, each agent among $1$ and $2$ must be with either agent $3$ or agent $4$.
But, in such a case, the agent among $3$ and $4$, say $3$, who is with agent $1$ will move to the coalition with agent $2$ and agent $4$, contradicting the stability.
Therefore, agents $3$ and $4$ must be in the same coalition.

* agents $1$ and $2$ cannot be both alone: Otherwise, they would deviate to group together.

From the previous observations, we get that
agents $3$ and $4$ must be together in a coalition,
while agents $5$ to $15$ must be together in another coalition.
The remaining question concerns the coalitions to which agents $1$ and $2$ belong.
It is not possible that both agents $1$ and $2$ are in a coalition with agents $3$ and $4$, otherwise it would contradict condition $(i)$.
If one agent among agents $1$ and $2$ is alone and the other one is with agents $5$ to $15$, then the alone agent can deviate to join them, contradicting the stability.
The remaining possible partitions
are present in the following cycle of IS deviations (the deviating agent is written on top of the arrows).

(p1) at (-4.5,0) $\{\{1\},\{2,3,4\},\{5,\dots,15\}\}$;
(p2) at (0,0) $\{\{2,3,4\},\{1,5,\dots,15\}\}$;
(p3) at (4.5,0) $\{\{3,4\},\{1,2,5,\dots,15\}\}$;
(p4) at (4.5,-1.5) $\{\{1,3,4\},\{2,5,\dots,15\}\}$;
(p5) at (0,-1.5) $\{\{2\},\{1,3,4\},\{5,\dots,15\}\}$;
(p6) at (-4.5,-1.5) $\{\{1,2\},\{3,4\},\{5,\dots,15\}\}$;
[arrow] (p1) – node[midway,above] 1  (p2);
[arrow] (p2) – node[midway,above] 2  (p3);
[arrow] (p3) – node[midway,right] 1  (p4);
[arrow] (p4) – node[midway,above] 2  (p5);
[arrow] (p5) – node[midway,above] 1  (p6);
[arrow] (p6) – node[midway,left] 2  (p1);

Hence, there is no IS partition in this instance.

The construction in Proposition <ref> does not seem to leave room for improvements, and we conjecture that the counterexample may even be minimal, that is, an IS partition always exists when $n<15$. However, even when $n<15$ and IS partitions do exist, there may still be cycles in the dynamics.

The dynamics of IS deviations may cycle in AHGs even when starting from the or grand coalition, preferences are strictly generally single-peaked, and $n = 7$.

Let us consider an AHG with 7 agents with the following (incompletely specified) preferences ([…] denotes an arbitrary order over the remaining coalition sizes).

$1:$     $2$     $\succ$     $3$     $\succ$     $5$     $\succ$     $4$     $\succ$     $1$     $\succ$     $[\dots]$

$2:$     $5$     $\succ$     $3$     $\succ$     $2$     $\succ$     $1$     $\succ$     $4$     $\succ$     $[\dots]$

$3,4:$     $3$     $\succ$     $2$     $\succ$     $1$     $\succ$     $[\dots]$

$5,6,7:$     $5$     $\succ$     $4$     $\succ$     $3$     $\succ$     $2$     $\succ$     $1$     $\succ$     $[\dots]$

They can be completed to be generally single-peaked with respect to the axis $1>2>3>5>4>6>7$.
We represent below a cycle of IS deviations.

(p1) at (-4,0) $\{1,2\},\{3,4\},\{5,6,7\}$;
(p2) at (0,0) $\{1\},\{2,3,4\},\{5,6,7\}$;
(p3) at (4,0) $\{2,3,4\},\{1,5,6,7\}$;
(p4) at (4,-1) $\{3,4\},\{1,2,5,6,7\}$;
(p5) at (0,-1) $\{1,3,4\},\{2,5,6,7\}$;
(p6) at (-4,-1) $\{2\},\{1,3,4\},\{5,6,7\}$;
[arrow] (p1) – node[midway,above] $2$  (p2);
[arrow] (p2) – node[midway,above] $1$  (p3);
[arrow] (p3) – node[midway,right] $2$  (p4);
[arrow] (p4) – node[midway,above] $1$  (p5);
[arrow] (p5) – node[midway,above] $2$  (p6);
[arrow] (p6) – node[midway,left] $1$  (p1);

This cycle can be reached from the or the grand coalition. Indeed, the partition $\{\{1,2\},\{3,4\},\{5,6,7\}\}$ can be reached from the by forming each coalition. It can also be reached by the grand coalition by having agents $1$, $2$, $3$, and $4$ leave and form their desired coalitions.

Note that $\{\{1\},\{3,5,6\},\{2,4,7\}\}$ is an IS partition in the example of the previous proposition.

We know that it is -complete to recognize instances for which an IS partition exists in AHGs, even for strict preferences <cit.>.
We prove that both checking the existence of a sequence of IS deviations ending in an IS partition and checking convergence are hard.

ISAHG is -hard and ISAHG is -hard, even for strict preferences.

However, these hardness results do not hold under naturally single-peaked preferences, even if preferences may be weak.
Indeed, we show in the next proposition that every sequence of IS deviations is finite under such a restriction.
We thus
complement a result by <cit.>
who have proved that there always exists an IS partition if the preferences are naturally single-peaked with a dynamical version. <cit.> provide a constructive proof involving specific IS deviations starting
from the which constructs an IS partition that is additionally weakly Pareto-optimal. By contrast, dynamics can reach every IS partition, and therefore may end up in partitions that are not Pareto-optimal.

The dynamics of IS deviations always converges to an IS partition in AHGs for naturally single-peaked preferences.

Let an AHG be given with naturally single-peaked preferences. Assume for contradiction that there exists a cycle of IS deviations. We will identify a specific deviation within this cycle that cannot be repeated throughout the execution of the dynamics, obtaining a contradiction.

Let $C$ be a coalition within the cycle of smallest cardinality such that there exists an agent $d\in C$ that performs a deviation leaving $C$. Such a coalition exists, because there are only finitely many different deviations performed in the cycle. We will argue that it is impossible to alter the coalition $C\setminus \{d\}$ within the execution of the cycle. Hence, the coalition $C$ will never be reached again.

First, our assumption of minimality implies that $C\setminus \{d\}$ cannot be altered by having an agent leave this coalition. Therefore, we have to show that it cannot happen that an agent ever joins $C\setminus \{d\}$. Assume for contradiction that there exists an agent $x$ that joins $C\setminus \{d\}$. Using our minimality assumption again, the deviation of agent $x$ when joining $C\setminus \{d\}$ must originate from a coalition $C'$ with $|C'| > |C|$. Hence, agent $x$ deviates towards a smaller coalition. Hence, single-peakedness implies that the peak $p_x$ of agent $x$ must satisfy $p_x < |C'|$. In particular, it follows by single-peakedness that it cannot be the case that $y\succ_x^S |C'|$ for any $y \ge |C'|$.

We claim that, within the cycle, it is impossible that agent $x$ ever reaches a coalition of size at least $|C'|$ again. To see this, let $C_k$ be the $k$-th coalition that $x$ is part of after leaving $C'$, i.e., $C_1 = (C\setminus \{d\})\cup \{x\}$ and $C_{k+1}$ evolves from $C_k$ by having some agent join or leave $C_k$, or $C_{k+1}$ is the new coalition of $x$ if $x$ performs a deviation to leave $C_k$.
We will show by induction over $k$ that, for every $k$, $|C_k| < |C|$ or $C_k\succ_x C'$. Since $C_1\succ_x C'$, the claim is true for $k = 1$. Now, let $k\ge 1$ and assume that $|C_k| < |C|$ or $C_k\succ_x C'$. Consider first the case that $|C_k| < |C|$. By our minimality assumption, $x$ is not allowed to perform a deviation and therefore $C_{k+1}$ evolves by having an agent leave or join $C_k$. Also by the minimality assumption, no other agent may leave the coalition. If an agent joins the coalition, then the size remains to be smaller than $|C|$, or is exactly $|C|$ and we already know that $|C|\succ_x^S |C'|$.

It remains to consider the case that $C_k\succ_x C'$. If $C_{k+1}$ forms via a deviation of agent $x$, then $C_{k+1}\succ_x C_k \succ_x C'$ and the claim is true. If some agent joins $C_k$ to form $C_{k+1}$ then $x$ has to approve this, and we can conclude that $C_{k+1}\succsim_x C_k \succ_x C'$. Hence, it remains to consider the case that some agent leaves $C_k$ and the remaining coalition is $C_{k+1}$.
As we have argued above, $|C_k|\succ_x^S |C'|$ implies that $|C_k| < |C'|$. If $|C_{k+1}| < |C|$, then the induction hypothesis is true for $k+1$. If $|C_{k+1}| = |C|$, then $C_{k+1}\succ_x C'$, and the induction hypothesis is also true.
Finally, it remains the case that $|C| < |C_{k+1}| = |C_k| - 1 < |C_k| < |C'|$, and we know that $|C|\succ_x^S |C'|$ and $|C_k|\succ_x^S |C'|$.
Hence, single-peakedness implies that $C_{k+1}\succ_x C'$. This completes the proof of the induction hypothesis.

It follows that agent $x$ cannot reach a coalition of size at least $|C'|$ again, a contradiction.
Hence, there cannot be an agent joining $C\setminus \{d\}$. This shows that $C\setminus \{d\}$ can never be altered again, our final contradiction.

The dynamics of IS deviations always converges to an IS partition in AHGs for strict naturally single-peaked preferences.

Assume for contradiction that there exists a cycle of IS deviations. The key idea is to construct an infinite sequence of agents $(a_k)_{k\ge 1}$ that perform deviations from coalitions $(C_k)_{k\ge 1}$, which are strictly increasing in size. Let $a_1$ be an agent that deviates within this cycle towards a larger coalition by an IS deviation. This transforms, say, partition $\partition_1$ into partition $\partition_1^1$. Set $C_1 = \partition_1(a_1)$ and $\hat C_1 = \partition_1^1(a_1)$. One can for instance take an agent that performs a deviation from a coalition of minimum size amongst all coalitions from which any deviation is performed. We will now observe how the coalition $\hat C_1$ evolves during the cycle. After possibly some agents outside $\hat C_1$ joined it or some left it, some agent $b$ originally in $\hat C_1$ must deviate from the coalition evolved from $\hat C_1$. Otherwise, we cannot reach partition $\partition_1$ again in the cycle. If $b\neq a_1$, we assume that the deviation transforms partition $\partition_2$ into partition $\partition_2^1$ and we set $a_2 = b$, $C_2 = \partition_2(b)$, and $\hat C_2 = \partition_2^1(b)$. Note that $|\hat C_2|>|C_2|\ge |\hat C_1|$, by single-peakedness and the fact that $|\hat C_2| \succ_b |C_2| \succ_b |C_2|-1 \succ_b \dots \succ_b |\hat C_1|\succ_b |\hat C_1| -1$ (where all preferences but the first follow from the assumption of strictness when some other agent joined the coalition of $b$). In particular, $|C_2| > |C_1|$.

If $b = a_1$, assume that the deviation transforms partition $\partition_1^2$ into $\partition_1^3$, where possibly $\partition_1^2 = \partition_1^1$. We update $\hat C_1 = \partition_1^3(a_1)$. Note that still $|\hat C_1| > |C_1|$ by single-peakedness, because the original deviation of $a_1$ performed in partition $\partition_1$ was towards a larger coalition and $|\partition_1^2(a_1)|\succeq_{a_1} |\partition_1^1(a_1)|$ (equality if the partitions are the same). We consider again the next deviation from $\hat C_1$ until it is from an agent $b\neq a_1$, in which case we proceed as in the first case. This must eventually happen, because every time the deviation is again performed by agent $a_1$ she gets closer to her peak. We proceed in the same manner. In step $k$, we are given a coalition $\hat C_k$ with $|\hat C_k| > |C_k|$ which was just joined by an agent. When the next agent originally in $\hat C_k$ deviates from the coalition evolved from $\hat C_k$, it is either an agent different from $a_k$ and we call it $a_{k+1}$, and find coalitions $C_{k+1}$ and $\hat C_{k+1}$ with $|\hat C_{k+1}| > |C_{k+1}| \ge |\hat C_k|$; or this agent is $a_k$, she moves towards an updated coalition $\hat C_k$ which maintains $|\hat C_k| > |C_k|$.

We have thus constructed an infinite sequence of coalitions $(C_k)_{k\ge 1}$ occurring in the cycle with $|C_{k+1}|>|C_k|$ for all $k\ge 1$, a contradiction.

Our next goal is to improve the preceding theorem by even showing a polynomial running time. We thus seek to prove the following theorem.
Our proof uses a similar technique as <cit.> who proved a running time of $\mathcal O(n^3)$ in the case of strict preferences. We refine the potential function of this proof and exploit a specific grouping of potential changes to use a combinatorial insight by <cit.>. Thus, we obtain the more general result for weak preferences.

The dynamics of IS deviations always converges to an IS partition in AHGs for naturally single-peaked preferences in $\mathcal O(n^4)$ steps.

We first provide a sketch summarizing the proof.

The key idea of the proof is to use a non-monotonic potential function. To this end, we will define a potential function $\Phi$ that essentially captures the distance of an agent's coalition size from the peak according to single-peakedness. This potential function is exactly the distance to the peak under strict preferences, but we tweak it within the indifference classes of preferences. It is usually decreasing, but it might be increasing for some deviations. However, we are able to show that the increases of the potential function can be negated and we therefore have to continuously decrease the potential function over time, causing the execution of the dynamics to terminate at an individually stable state. To this end, we will separate the change in potential for the deviators and for agents affected by the deviation, i.e., the agents abandoned or joined by the deviator. The second part, i.e., the potential changes of the affected agents can be globally bounded by a combinatorial insight called the Deviation Lemma, an insight recently introduced for proving convergence results for dynamics in additively separable hedonic games <cit.>. For the applicability of this lemma, the careful design of the potential function is essential. As a consequence, only the changes in potential caused by the deviators matter for an overall decrease of the potential. To this end, we will separately consider various types of deviations and either show that they decrease the potential, or pool them with other deviations to have a decrease in potential for certain groups of deviations.

Now, we provide the complete proof.

Let us start by defining a potential function. Consider an agent $i$ with single-peaked preferences $\succsim_i$. Given a coalition size $s$, we define $l_i(s) = \max\{k\in [n]\colon s-k\sim_i s-k + 1\sim_i \dots \sim_i s-1 \sim_i s\}$ and $r_i(s) = \max\{k\in [n]\colon s \sim_i s + 1\sim_i \dots \sim_i s + k - 1 \sim_i s + k\}$, i.e., the number of coalition sizes on the `plateau' of the single-peaked preference order to the left and to the right of a considered coalition size. Further, we define the peak of agent $i$ (with respect to preference order $\succsim_i$) as $p_i = \max\{s\in [n]\colon s\succsim_i t \textnormal{ for all } t\in [n]\}$, i.e., the largest coalition size among the most preferred coalition sizes. Then, the potential of agent $i$ in coalition $\partition$ is defined as

$$\phi_i(\partition) = \begin{cases}
p_i - |\partition(i)| & |\partition(i)| \le p_i\\
|\partition(i)| - p_i + r_i(\partition(i)) - l_i(\partition(i)) & |\partition(i)| > p_i
\end{cases}\text.$$
In other words, the potential is the distance to the peak if the coalition size of the agent is at the left side of the peak, and if the coalition size is at the right side of the peak, then the potential is the distance to the peak such that we reverse the distances within each indifference class. An illustration of the potential of an agent is given in <Ref>. Now, the potential of coalition $\partition$ is defined by taking the sum over all agents, i.e., $\Phi(\partition) = \sum_{i\in N}\phi_i(\partition)$.

at (8,4) $\phi_i$;

[->] (.5,0) – (10.5,0);
ıin 1,...,9
(ı,.25) – (ı,-.25);
at (ı,-.5) $\i$;

at (11,-.5) coalition size s;

(1,1) – (2,3) – (3,3) – (4,5) – (6,5) – (7,3) – (9,3);
[indicatorvertex, label = 270:$5$] at (1,1) ;
[indicatorvertex, label = 270:$4$] at (2,3) ;
[indicatorvertex, label = 270:$3$] at (3,3) ;
[indicatorvertex, label = 270:$2$] at (4,5) ;
[indicatorvertex, label = 270:$1$] at (5,5) ;
[indicatorvertex, label = 270:$0$] at (6,5) ;
[indicatorvertex, label = 270:$3$] at (7,3) ;
[indicatorvertex, label = 270:$2$] at (8,3) ;
[indicatorvertex, label = 270:$1$] at (9,3) ;
[indicatorvertex, label = $p_i$] at (6,5) ;

Illustration of the potential $\phi_i$ of an agent $i$ for the preference order $\succsim_i\colon 4 \sim_i 5 \sim_i 6\succ_i 7 \sim_i 8 \sim_i 9 \sim_i 2 \sim_i 3 \succ_i 1$. The potential in the indifference class $\{7,8,9\}$ at the right of the peak is the reverse order of the distances to the peak $p_i$.

We are ready to analyze the individual dynamics. To this end, let $(\partition_k)_{k = 0}^m$ and $(d_k)_{k=1}^m$ be sequences of partitions and agents such that, for $k \in [m]$, $\partition_{k+1}$ evolves from $\partition_k$ through an IS deviation of agent $d_k$. Our ultimate goal is to analyze the difference $\Phi(\partition_m) - \Phi(\partition_0)$. By telescoping, we can transform this as

$$\Phi(\partition_m) - \Phi(\partition_0) = \sum_{k=1}^m \Phi(\partition_k) - \Phi(\partition_{k-1})\text.$$

Given $k\in [m]$, define $\Delta_k = \Phi(\partition_k) - \Phi(\partition_{k-1})$. Clearly, $\Delta_k$ only depends on changes in the potential of agents involved in the deviation, i.e., for agents in the set $\partition(d)\cup \partition'(d)$. Define

$$\Delta_k^d = \phi_{d_k}(\partition_k) - \phi_{d_k}(\partition_{k-1}) \textnormal{ and } \Delta_k^a = \sum_{i \in (\partition_k(d_k)\cup \partition_{k-1}(d_{k-1}))\setminus \{d_k\}}\phi_{i}(\partition_k) - \phi_{i}(\partition_{k-1})\text.$$

In other words, these differences consider the $k$-th step in the dynamics and $\Delta_k^d$ is the change in potential of the deviator and $\Delta_k^a$ the change in potential of the other affected agents. Hence, we can rewrite the potential change as

\begin{equation}\label{eq:AHG-sum-split}
\Phi(\partition_m) - \Phi(\partition_0) = \sum_{k=1}^m \Delta_k^d + \Delta_k^a\text.
\end{equation}

We will start by analyzing the affected agents and find a bound for $\sum_{k=1}^m \Delta_k^a$. Let $k\in [m]$ and $i\in \partition_k(d_k)\setminus \{d_k\}$. Then, $\phi_{i}(\partition_k) - \phi_{i}(\partition_{k-1}) = -1$. Indeed, because agent $d_k$ performs an IS deviation, each agent in $\partition_k(d_k)\setminus \{d_k\}$ has to improve her coalition (weakly). If $i$ was to the left of her peak when $d_k$ joined, this causes a decrease in her potential. If $i$ was to the right of her peak, she can only give her consent to $d_k$ joining the coalition if $\partition_k(i)\sim_i \partition_{k-1}(i)$, and therefore her potential also decreased by $1$ in this case. Additionally, by design of the potential function, an agent's potential increases by $1$ if she is left unless she strictly improves her utility (in which case the potential decreases). This yields

$$\Delta_k^a = \sum_{i \in (\partition_k(d_k)\cup \partition_{k-1}(d_{k-1}))\setminus \{d_k\}}\phi_{i}(\partition_k) - \phi_{i}(\partition_{k-1}) \le |\partition_{k-1}(d_k)| - |\partition_k(d_k)|\text.$$

We obtain a global bound on the changes in potential of affected agents by applying the following lemma.

Let $(\partition_k)_{k = 0}^m$ and $(d_k)_{k=1}^m$ be sequences of partitions and agents such that, for $k \in [m]$, $\partition_{k+1}$ evolves from $\partition_k$ through a unilateral deviation of agent $d_k$. Then, the following identity holds:

\begin{equation*}\label{eq:dvl}
\sum_{k = 1}^m |\partition_{k-1}(d_k)| - |\partition_k(d_k)| =
\frac{1}{2}\sum_{i \in N} |\partition_0(d_k)| - |\partition_m(d_k)|\text.
\end{equation*}

Hence, it follows that

\begin{equation}\label{eq:AHG-affected-bound}
\sum_{k=1}^m \Delta_k^a \le  \sum_{k=1}^m  |\partition_{k-1}(d_k)| - |\partition_k(d_k)| =
\frac{1}{2}\sum_{i \in N} |\partition_0(i)| - |\partition_m(i)|\le \frac 12 n^2\text.
\end{equation}

So far, we were able to give a global bound for the second part of the sum in <Ref>. To complement this bound, we will show that the changes in potential cause by the deviators cause a constant decrease in the potential function. It is useful to distinguish the deviations according to the positions of the deviator before and after the deviation relative to her peaks. Therefore, we define $D_{l\to l} = \{k\in [m]\colon |\partition_{k-1}(d_k)| < p_k, |\partition_k(d_k)| \le p_k\}$, $D_{l\to r} = \{k\in [m]\colon |\partition_{k-1}(d_k)| < p_k, |\partition_k(d_k)| > p_k\}$, $D_{r\to l} = \{k\in [m]\colon |\partition_{k-1}(d_k)| > p_k, |\partition_k(d_k)| \le p_k\}$, and $D_{r\to r} = \{k\in [m]\colon |\partition_{k-1}(d_k)| > p_k, |\partition_k(d_k)| > p_k\}$. This yields a partition of $[m]$ into disjoint sets. Clearly, it holds that

\begin{align}
&\Delta_k^d\le -1 \textnormal{ for all } k\in D_{l\to l}\textnormal{ and}\\
&\Delta_k^d\le -1 \textnormal{ for all } k\in D_{r\to r}\text.
\end{align}

However, deviations at steps in $D_{r\to l}$ and $D_{l\to r}$ might increase the potential and we will have to use some decreases in potential of deviations in $D_{r\to r}$ to negate some of these changes. Next, we consider the deviations at steps in $D_{r\to l}$. Note that all except possibly the first one of these deviations must be preceded by a deviation of the same agent corresponding to a step in $D_{l\to r}$. Indeed, once an agent is at the left of her peak, the only possibility for her to ever get back to the right of the peak is a deviation from the left to the right of the peak, because she would not approve an agent joining her via an IS deviation while causing her coalition size to cross the peak. Define the subset $D_{prec} = \{k\in D_{r\to l}\colon \exists k' < k\textnormal{ with } d_k = d_{k'}, k'\in D_{l\to r}\}$. Because every agent can perform at most one deviation at a step in $D_{r\to l}$ which is not in $D_{prec}$, we know that

\begin{equation}
|D_{r\to l}\setminus D_{prec}| \le n\text.
\end{equation}

Moreover, our discussion above implies that the mapping $\tau_{succ}\colon D_{prec}\to  D_{l\to r}$, defined by $\tau_{succ}(k) = \arg\max \{k' < k\textnormal{ with } d_k = d_{k'}, k'\in D_{l\to r}\}$ is injective. In particular, for $k\in D_{prec}$, the agent $d_k$ is continuously improving her utility starting from the deviation at time $k'$ until the deviation at time $k$, and therefore $|\partition_k(d_k)|\succ_k |\partition_{k' - 1}(d_k)|$. Since they are both to the left of the peak,

MB: Problem is that the pairing need not yield an improvement of the potential difference.

Our final goal in this section is to provide a polynomial bound on the running time of the dynamics. Unfortunately, our proof relies on strict preferences, leaving the case of weak preferences as an interesting open problem. Even the proof under strict preferences needs far more sophisticated methods than the proof of existence. The key idea is to distinguish deviations towards a smaller and a larger coalition, and to make use of a potential function that aggregates values for agents and coalitions to bound the number of deviations towards a larger coalition by $n^2$. Using a second, much simpler potential function yields an overall polynomial running time.

The dynamics of IS deviations always converges to an IS partition in AHGs for strict naturally single-peaked preferences in $\mathcal O(n^3)$ steps.

Let an AHG be given with strict and naturally single-peaked preferences where the peak of agent $j$ is at position $p_j$. Consider a sequence of IS deviations starting at some initial partition $\spartition$. Assume that the deviations lead to the sequence $(\partition_k)_{k = 0}^m$ where, for $k = 0,\dots, m-1$, $\partition_{k+1}$ evolves from $\partition_k$ through an IS deviation of agent $d_k$. We call a deviation an R-move (or L-move) if $d_k$ deviates towards a larger (or smaller) partition. The main part of the proof provides a bound of $n^2$ for the number of R-moves. As we will see, this implies that there are at most $n^3$ L-moves.

The idea is to define a potential function that is based on a value $v^k_j$ for each agent $j\in N$ and a value $v^k_C$ for each coalition $C\in \partition_k$. This potential function will not only depend on the partition $\partition_k$, but also on the starting partition and the specific sequence of deviations to derive $\partition_k$. It will be increased strictly during an R-move and will not decrease during an L-move. We also need to keep track of the last agent $l^k_C$ that entered a coalition $C\in \partition_k$ if this agents plays a `special role' within her coalition.[Basically, we must be careful not to increase the potential function by too much after an R-move. If an agent performs an R-move, she might land up far right of her peak, and we keep track of this possibility by labeling the agent as `special'. Intuitively, by the strictness and single-peakedness of preferences, only the last agent that has joined some coalition can be special.]
The potential function will have a close relationship to the peaks of agents. It maintains the invariant that an agent has a value that is always smaller than her peak (but also reflects her coalition size).

Let us define the values that lead to the potential function.
Initially, define $v^0_j = 0$ for all agents $j\in N$, and $v^0_C = 0$ for all coalitions $C\in \spartition$. Also, there is no last agent that entered a coalition so far, so we initiate $l^0_C = \bot$. Now, assume that we transition from partition $\partition_{k}$ to partition $\partition_{k+1}$ through an IS deviation of agent $d_k$. Denote $D_k = \partition_{k}(d_k) \setminus \{d_k\}$ and $E_k = \partition_{k+1}(d_k)$. Note that since the only change in the partition is caused by agent $d_k$, this corresponds exactly to the two new coalitions in $\partition_{k+1}$ compared to $\partition_{k}$.
Also, denote $l_k = l^k_{\partition_{k}(d_k)}$, which will be the last agent that entered $\partition_{k}(d_k)$ (unless $l^k_{\partition_{k}(d_k)} = \bot$, in which case such an agent does either not exist or its identity is unimportant for the updates of the values).
We specify first the updates that are done independently of the kind of deviation.

We set $v^{k+1}_j = v^{k}_j$ for all $j\in N \setminus (D_k \cup E_k)$, i.e., the value of agents not involved in the deviation does not change. Similarly, we set $v^{k+1}_C = v^{k}_C$ and $l^{k+1}_C = l^{k}_C$ for all coalitions $C\in \partition_k \cap \partition_{k+1} = \partition_{k+1} \setminus \{D_k,E_k\}$. The updates for the last agents do not depend on the kind of move. Set $l^{k+1}_{E_k} = d_k$, and set $l^{k+1}_{D_k} = \bot$ if $l_k = d_k$ and $l^{k+1}_{D_k} = l_k$, otherwise.

It remains to specify new values for the agents which are part of one of the coalitions involved in the deviation, and the values of these coalitions. The intuition for defining the agent and coalition values is as follows. The value of an agent is always strictly smaller than her peak. In addition, it represents a size that is preferred at most as much as an agent's current coalition size.

We first consider the deviating agent.
If she performs an R-move, then an appropriate bound for her value is the size of the abandoned coalition. By 	this, we do not increase her value by too much if she ends up far to the right of her peak.
In case of an L-move, the deviating agent can only be the last agent who joined the coalition, unless she abandons a coalition that was never joined by an agent (this intuition follows from the third invariant in the formal proof below).
Hence, we assign the `right' value by maintaining the current value.

Formally, we set $v^{k+1}_{d_k} = |\partition_{d_k}(\partition_k)| = |D_k| + 1$ if the deviation was an R-move and  $v^{k+1}_{d_k} = v^{k}_{d_k}$ if it was an L-move.

Next, we consider the agents which are joined. Their consent to increase the coalition size together with strictness and single-peakedness of the preferences imply that they move towards their peak.
We set $v^{k+1}_j = |E_k| - 1$ for all $j\in E_k\setminus \{d_k\}$, which represents a bound that is strictly smaller than their peak.

This leads us to the coalition value of $E_k$. The role of this value is to anticipate behavior of the deviating agent that goes against the drift of coalition sizes to the right. In all cases, we simply update $v^{k+1}_{E_k} = v^{k+1}_{d_k}$, which will be sufficient to serve this purpose. The intuition of this value is that we reach a critical point in the deviation when a coalition has been abandoned so often that its size reaches the value of the special last agent. In this case, the special last agent cannot be in the situation anymore where she can be too far on the right of the peak. We can then `spread' the coalition value among all agents (of which there is exactly the right amount).

The most complicated part of the update rules is to specify new values for the agents in the abandoned coalition. Here, we have to update very differently dependent on the behavior of the dynamics. We distinguish several cases that we will reference to in the following proof. The first considers the case where the deviating agent performs an L-move. The four other cases consider different situations during an R-move. The second and third case consider two simple situations where either the abandoned agents did not change their value since initialization, and where $d_k = l_k$, i.e., the deviating agent is the special last agent in the abandoned coalition. Note that the update rules are the same for the first three cases whereas the values of the agents can still be very different. The final two cases consider the situation where $d_k \neq l_k$. The update rules distinguish whether we reach a threshold specified by the value of $l_k$ in the forth case, or whether not in the fifth case. Note that the case distinction is exhaustive because of invariant (<ref>) in the proof of Claim <ref>.

Note that the forth case covers the case where $l_k = \bot$ but agents in the abandoned coalition already have a value because it .

(i) If the deviation was an L-move, we update $v^{k+1}_j = v^{k}_j$ for all $j\in D_k$ and $v^{k+1}_{D_k} = 0$.

In all other cases, we assume that the deviation was an R-move.

(ii) If $v^{k}_j = 0$ for all $j\in D_k$, we maintain $v^{k+1}_j = v^{k}_j$ for all $j\in D_k$ and $v^{k+1}_{D_k} = 0$.

(iii) If $d_k = l_k$, we update $v^{k+1}_j = v^{k}_j$ for all $j\in D_k$ and $v^{k+1}_{D_k} = 0$.

For the remaining cases, we assume that $d_k \neq l_k$.

Consider the case that $l_k = \bot$. Then, set $v_j^{k+1} = |D_k|$ for all $j\in D_k$, $v^{k+1}_{D_k} = 0$, and maintain $l^{k+1}_{D_k} = \bot$.

(v) Otherwise,
there exists an agent $l_k\in N$ and $v^{k}_{l_k} \le |D_k|$ (shown in the proof of Claim <ref>).
If $v^{k}_{l_k} = |D_k|$, then set $v_j^{k+1} = |D_k|$ for all $j\in D_k$, $v^{k+1}_{D_k} = 0$, and $l^{k+1}_{D_k} = \bot$ (we update this last agent again because all agents play the same role now within $D_k$).

(vi) If $v^{k}_{l_k} < |D_k|$, set $v^{k+1}_j = |D_k|-1$ for all $j\in D_k\setminus \{l_k\}$, $v^{k+1}_{l_k} =v^{k}_{l_k}$, and $v^{k+1}_{D_k} = v^{k}_{D_{k}\cup\{d_k\}}$ (the last agent of $D_{k}$ does not need a second update since it still plays a special role).

We are ready to specify our potential function.
Given a partition $\partition_k$ that occurs in the dynamics, define its potential $\Lambda(\partition_{k}) = \sum_{j \in N} v^{{k}}_j + \sum_{C\in \partition_k}v^{k}_C$. Again, note that this potential can depend both on the starting partition and the specific sequence of deviations. The core of the proof is the following claim.

For all $k = 1,\dots, m$, $\Lambda(\partition_{k})\ge \Lambda(\partition_{k-1})$. If $\partition_{k+1}$ evolved from $\partition_k$ by an R-move, then $\Lambda(\partition_{k+1}) > \Lambda(\partition_{k})$.

We will prove this main claim along with the following useful invariants by induction over $k = 0,\dots, m$:

*  For all $C\in \partition_k$, $v_C^{k} \le |C|-1$.

*  For all $C\in \partition_k$ and $j\in C$, if $v_C^{k} > 0$, then $l_C^k \neq \bot$ and $v_j^{k} \le |C|-1$.

*  For all agents $j\in N$ with $v_j^k>0$, $v_j^{k}\preceq_j |\partition_k(j)|$ and $p_j > v^{k}_j$.

*  For all $C\in \partition_k$ with $l^k_C\neq \bot$, $v^k_C = v^k_{l^k_C}$ or $v^k_C = 0$. Moreover, in this case, $v^k_{l^k_C}\le |C|-1$.

*   For all $C\in \partition_k$ with $l_C^k = \bot$, then $v_j^{k} = |C|$ for all $j\in C$ or $v_j^{k} = 0$ for all $j\in C$. Moreover, in this case,  $v_C^k = 0$.

For $k=0$, the main claim is vacant, and the four invariants hold by our initialization of the agent and coalition values. So assume that all of them are true for some $0\le k<m$. We use the notation for the agents $d_k$ and $l_k$, and the coalitions $D_k$ and $E_k$ as in the description of the updates of the values. We will proof that all invariants are true for partition $k+1$.

* The first invariant follows from the update rules and by induction. Let us provide the details for the two affected coalitions.
Specifically, $v_{D_k}^{{k+1}} = 0$, unless we are in the last case of the update rule, where $v_{D_k}^{{k+1}} \overset{\mathrm{(v)}}{=} v_{D_k\cup \{d_k\}}^{{k}} \overset{(\ref{cl:notbotcoal})}{=} v_{l_k}^{{k}} \overset{\mathrm{(v)}}{\le} |D_k|-1$.

Now, let us consider coalition $E_k$. If $v_{E_k}^{k+1} = 0$, then the invariant holds. Otherwise, if $d_k$ performed an R-move, then $v^{k+1}_{E_k} = |D_k|+1\le |E_k| - 1$. On the other hand, assume that $d_k$ performed an L-move. Recall that by the update rule for $E_k$, $v_{E_k}^k = v^k_{d_k}$. Then, it holds that $v^k_{d_k} = 0$ (and we are done), or $d_k$ was the last agent who joined $\partition_k(d_k)$ (other agents in $\partition_k(d_k)$ can only perform R-moves due to strict preferences and single-peakedness). Assume for contradiction that $v_{E_k}^k \ge |E_k|$. If $v_{E_k}^k = |E_k|$, then induction for invariant (<ref>) yields $|E_k| = v_{d_k}^k \preceq_{d_k} |\partition_k(d_k)|$, contradicting the fact that $d_k$ must improve her coalition after her deviation. Hence, using invariant (<ref>) again, we have that $p_{d_k} > v^k_{d_k} > |E_k|$ and $v^k_{d_k}\prec_{d_k} p_k$. Hence, single-peakedness implies that $|E_k| \prec_{d_k} v^k_{d_k}$, and the deviation was again not improving, a contradiction.

* The second invariant follows by induction and the update rules. In particular, it holds for the agent $d_k$ if $d_k$ performed an L-move to join $E_k$, because then $v^{k+1}_{d_k} = v^{k+1}_{E_k}$ and the invariant follows from the first invariant. The value of the coalition $D_k$ will either be set to $0$ or the invariant will be maintained for all agents in $D_k$.

* The third invariant holds by induction for the agents who do not change their value. For the agents in $E_k \setminus \{d_k\}$, it holds by definition of an IS deviation, because they improve when agent $d_k$ joins. The same is true for $d_k$ if she performed an R-move because then $v_{d_k}^{k+1}=|D_k|+1$. Otherwise, if $d_k$ performs an L-move, we can apply induction, because she improved her utility.

Finally, we have to consider the agents in $D_k$. The invariant holds if $v_j^k = 0$ for all $j\in D_k$. Otherwise, all agents $j\in D_k\setminus \{l_k\}$ have improved when the last agent joined and therefore $p_j \ge |D_k| + 1 > |D_k|$. By the update rules, $v^{k+1}_j \le |D_k|$. In particular, single-peakedness implies that $v_j^{k+1}\preceq_j |D_k| = |\partition_{k+1}(j)|$. Finally, for $l_k$, the argument is the same if $v_{l_k} = |D_k|$ and we can apply induction (and single-peakedness) if $v_{l_k} < |D_k|$. Note that the case $v_{l_k} > |D_k|$ is excluded by induction for invariant (<ref>).

* The forth invariant is immediate for all coalitions in $\partition_{k+1}\setminus \{D_k\}$. The only case where $v^{k+1}_{D_k}\neq 0$ is case $(v)$ of the update rules. Then, $v^{k+1}_{l_k} =v^{k}_{l_k}$, and $v^{k+1}_{D_k} = v^{k}_{D_{k}\cup \{d_k\}}$.
If $v^{k+1}_{l_k}\neq 0$, then $v^{k}_{l_k}\neq 0$, and induction yields for this case that $v^{k+1}_{D_k} = v^{k}_{D_{k}\cup\{d_k\}} = v^k_{l_k} = v^{k+1}_{l_k}$. Moreover, in case $(v)$ of the update rule, it holds that $v^k_{l_k} \le |D_k| - 1$, which achieves the last part of this invariant.

* Again, the only coalitions to consider are $D_k$ and $E_k$. Since, $l_{E_k}^{k+1} = d_k$, the invariant is vacant for this coalition. For $D_k$, the invariant can only apply in cases (ii), (iv), and (v) of the update rules. For all of these cases, it holds that $v_{D_k}^{k+1} = 0$, and $v_j^{k+1} = |D_k|$ for all $j\in D_k$ or $v_j^{k+1} = 0$ for all $j\in D_k$.

An immediate consequence of invariant (<ref>) is that for all agents $j\in N$, it holds that $v_j^{k} \le |\partition_k(j)|$. Indeed, otherwise $|\partition_k(j)| < v_j^{k} < p_j$ and since $v_j^k \prec_j p_j$, single-peakedness and strictness would imply $|\partition_k(j)| \prec_j v_j^{k}$, contradicting invariant (<ref>). We call this observation $(\Delta)$.

Finally, we can show our main claim. We can restrict our attention to coalitions $D_k$ and $E_k$ and agents within these. Note that either $v_{E_k\setminus \{d_k\}}^{k} = 0$, or, by invariant (<ref>), $v_{E_k\setminus \{d_k\}}^{k}\le |E_k|-2$. Moreover, for every $j\in E_k\setminus\{d_k\}$, it holds that  $v_j^{{k+1}} = |E_k| - 1$ according to the update rule, and $v_j^{k} \le (|E_k|-1)-1$ according to invariant (<ref>) if $v_{E_k\setminus \{d_k\}}^{k} > 0$. Thus, in this case $v_j^{{k+1}} - v_j^{k} \ge 1$ for all $j\in E_k\setminus \{d_k\}$. Hence, in every case

\begin{align*}
\sum_{j\in E_k\setminus \{d_k\}}v^{{k+1}}_j-v^{k}_j - v_{E_k\setminus \{d_k\}}^{k} > 0\text.\tag{$*$}
\end{align*}

We make a case distinction according to the different update cases for agents in $D_k$.
We start with with the cases covering situations with $d_k = l_k$.

(i) 	If an L-move was performed, then $d_k = l_k$ or the agents in $D_k\cup \{l_k\}$ did not participate in a deviation, yet. In either case, $v_{E_k}^{{k+1}} \ge v^k_{{D_k}\cup\{d_k\}}$ (using the update rules for the values of $l_k$ and $E_k$, and the forth invariant). Hence,

\begin{align*}
\Lambda(\partition_{k+1})- \Lambda(\partition_{k}) \overset{(*)}{\ge} v_{D_k}^{{k+1}} + \sum_{j\in D_k\cup \{d_k\}} v^{{k+1}}_j-v^{k}_j \overset{(i)}{=} 0\text.
\end{align*}

Assume now that an R-move was performed. Then, it holds that $v_{E_k}^{{k+1}} = |D_k|+1$ and by the invariant (<ref>), $v_{D_k\cup\{d_k\}}^k \le |D_k|$. Hence,

\begin{align*}
v_{E_k}^{{k+1}} - v_{D_k\cup\{d_k\}}^k > 0\text.\tag{$\mathit{**}$}
\end{align*}

(ii) If the agents in $D_k$ had value $0$, then $\Lambda(\partition_{k+1})- \Lambda(\partition_{k})\ge v_{d_k}^{{k+1}} + v_{E_k}^{{k+1}} = 2 (|D_k| + 1) > 0$.

(iii) Next, assume that the agents in $D_k$ do not have value $0$, and that $d_k = l_k$.

\begin{align*}
\Lambda(\partition_{k+1})- \Lambda(\partition_{k}) \overset{(*)}{\ge} \underbrace{v_{d_k}^{{k+1}} - v_{d_k}^{{k}}}_{\ge\,0}+ \underbrace{v_{D_k}^{{k+1}}}_{=\, 0\textnormal{ by }  \mathrm{(iii)}} + \underbrace{v_{E_k}^{{k+1}}  - v_{D_k\cup\{d_k\}}^{{k}}}_{>\, 0\textnormal{ by }  (**)} > 0\text.
\end{align*}

Now, consider the case that $d_k\neq l_k$.

(iv) Assume that $l_k = \bot$. Then, by invariant (<ref>), $v_{D_k\cup\{d_k\}}^k = 0$. Moreover, by the update rule, for all $j\in D_k$, $d_j^{k+1} = |D_k|$, while observation $(\Delta)$ yields $d_j^{k} \le |D_k|+1$. Hence,

\begin{align*}
\sum_{j\in D_k} d_j^{k+1} - d_j^{k} \ge -|D_k|\text.
\end{align*}

\begin{align*}
\Lambda(\partition_{k+1})- \Lambda(\partition_{k}) \overset{(*)}{\ge} \underbrace{v_{d_k}^{{k+1}} - v_{d_k}^{{k}}}_{\ge\,0}+ \underbrace{v_{D_k}^{{k+1}}}_{=\, 0\textnormal{ by } \mathrm{(iv)}} + \underbrace{v_{E_k}^{{k+1}}}_{=\, |D_k|+1} + \underbrace{\sum_{j\in D_k} d_j^{k+1} - d_j^{k}}_{\ge\, -|D_k|} - \underbrace{v_{D_k\cup\{d_k\}}^{{k}}}_{=\, 0\textnormal{ by }  (\ref{cl:botcoal})} > 0\text.
\end{align*}

Now assume that $l_k\neq \bot$. By invariant (<ref>), $v_{l_k}^{k} \le |D_k|$. We consider the two corresponding cases.

(v) Assume that $v_{l_k}^{k} = |D_k|$. If $v_{D_k\cup\{d_k\}}^k > 0$, then
$v_j^{{k+1}} = |D_k| \overset{(\ref{cl:agposcoal})}{\ge} v_j^{{k}}$ for all $j\in D_k$.

\begin{align*}
\Lambda(\partition_{k+1})- \Lambda(\partition_{k}) \overset{(*)}{\ge} \underbrace{v_{d_k}^{{k+1}} - v_{d_k}^{{k}}}_{\ge\,0}+ \underbrace{v_{D_k}^{{k+1}}}_{=\, 0\textnormal{ by } \mathrm{(v)}} + \underbrace{v_{E_k}^{{k+1}}  - v_{D_k\cup\{d_k\}}^{{k}}}_{>\, 0\textnormal{ by }  (**)} > 0\text.
\end{align*}

In the case that $v_{D_k\cup\{d_k\}}^k = 0$, we have
$v_j^{{k+1}} = |D_k| \overset{(\Delta)}{\ge} v_j^{{k}} - 1$ for all $j\in D_k$.

\begin{align*}
v_{E_k}^{k+1} - \sum_{j\in D_k} v_j^{{k+1}} -v_j^{{k}} = v_{E_k}^{k+1} - |D_k| > 0\text.\tag{${***}$}
\end{align*}

\begin{align*}
\Lambda(\partition_{k+1})- \Lambda(\partition_{k}) \overset{(*),(***)}{>} \underbrace{v_{d_k}^{{k+1}} - v_{d_k}^{{k}}}_{\ge\,0}+ \underbrace{v_{D_k}^{{k+1}}}_{=\, 0\textnormal{ by } \mathrm{(vi)}} - \underbrace{ v_{D_k\cup\{d_k\}}^{{k}}}_{=\, 0} > 0\text.
\end{align*}

(vi) If $v_{l_k}^{k} \neq |D_k|$, then, by invariant (<ref>), $v_{l_k}^{k} < |D_k|$. Hence, as in the beginning of case (iv), $\sum_{j\in D_k}v_j^{k}-v_j^{{k+1}}\le |D_k|-1$. Moreover, $v_{E_k}^{{k+1}}= |E_k|-1\ge |D_k| + 1$. Also, according to the update rule for case (vi), $v^{k+1}_{D_k} = v^{k}_{D_{k}\cup\{d_k\}}$. Hence,

\begin{align*}
\Lambda(\partition_{k+1})- \Lambda(\partition_{k}) \overset{(*)}{\ge} \underbrace{v_{d_k}^{{k+1}} - v_{d_k}^{{k}}}_{\ge\,0}+ \underbrace{v_{D_k}^{{k+1}}- v_{D_k\cup\{d_k\}}^{{k}}}_{=\, 0\textnormal{ by } \mathrm{(vi)}} + \underbrace{v_{E_k}^{{k+1}}}_{=\, |D_k|+1} + \underbrace{\sum_{j\in D_k} d_j^{k+1} - d_j^{k}}_{\ge\, -(|D_k|-1)} > 0\text.
\end{align*}

This completes the induction.

Now, note that for all $0\le k\le m$, $\Lambda(\partition_k) \ge 0$ and the potential is integer-valued. Moreover, $\Lambda(\partition_m) = \sum_{j \in N} v^m_j + \sum_{C\in \partition_k}v^m_C = \sum_{C\in \partition_k} (v^m_C +  \sum_{j \in C} v^m_j) \le \sum_{C\in \partition} |C|^2 \le n^2$. We use that, by $(\Delta)$, if $v_C^m = 0$, then $v_j^m \le |C|$ for all $j\in C$, and we also use the first and second invariant. Hence, there are at most $n^2$ R-moves.

To get a global bound on the number of moves, we consider the simple potential that counts the pairs of agents that form common coalitions. Given a coalition $C$, this value is precisely $|C|(|C|-1) / 2$. Define therefore the potential $\Gamma(\partition) = \sum_{C\in \partition}|C|(|C|-1) / 2$. Note that $0\le \Gamma(\partition)\le n(n-1)/2$. Now, every R-move raises the potential $\Gamma$ by at most $n-1$, and every L-move diminishes it by at least $1$. Hence, there can be at most $\Gamma(\partition_0) + n^2(n-1) \le n^3$ L-moves. This bounds the total length of the execution of the dynamics by $n^2 + n^3 = \mathcal O(n^3)$.

The dynamics of IS deviations converges to an IS partition in AHGs for naturally single-caved preferences, when starting from the or the grand coalition.MB: define single-cavedness in the preliminaries if you want to keep the result

Consider an AHG with naturally single-caved preferences and a dynamics given as $(\partition_k)_{k=0}^m$, where $\partition_{k+1}$ evolves from $\partition_k$ via an IS deviation. Assume first that $\partition_0$ is the . We claim that for each $k\ge 0$, every agent $j\in N$ and every positive integer $l\le \partition^k(j)$, $l\precsim_j |\partition_k(j)|$. The claim follows easily by induction. Hence, the only possible deviations are towards larger coalitions and it follows that $m\le {n\choose 2}$.

Now assume that $\partition_0$ is the grand coalition. We claim that for each $k\ge 0$, every agent $j\in N$ and every coalition $C\in \partition_k\setminus \{\partition_k(j)\}$ with $|C|\ge |\partition_k(j)|$ holds that $|C| +1\precsim_j |\partition_k(j)|$. Note that the claim implies that there can only be deviations towards smaller coalitions, implying that $m\le {n\choose 2}$.

We prove the claim by induction. Clearly, it holds for $k = 0$. Assume therefore it is true for some $0\le k < m$. Let $j\in N$

§ HEDONIC DIVERSITY GAMES

Hedonic diversity games take into account more information about the identity of the agents, changing the focus from coalition sizes to proportions of given types of agents. Following the definition of HDGs, we assume throughout this section that the agent set is always partitioned into sets $R$ and $B$ of red and blue agents, respectively. It is known that IS partitions always exist in HDGs, even without restrictions such as single-peakedness of preferences <cit.>.
However, we prove that the dynamics of IS deviations may cycle, even under very strong restrictions. This stands in contrast to empirical evidence for the convergence of dynamics based on extensive computer simulations by <cit.>. To this end, we consider natural restrictions of the preferences, of the starting partitions, and specific selection rules for the performed deviations. We show that most combinations of them still allow for infinite dynamics. Most surprisingly, we can show that the dynamics may cycle even if we start from the and the preferences are strict and single-peaked.[This corrects a statement in the conference version of this paper <cit.>.] However, if we add an arguably weak selection rule, we obtain convergence of the dynamics. To define this rule, we call a coalition $C\subseteq N$ homogeneous if it consists only of agents of one type, i.e., $C\subseteq R$ or $C\subseteq B$. We say that a deviation satisfies solitary homogeneity if, whenever the target coalition of the deviator is homogeneous, then it is a singleton coalition. Note that whenever an agent can perform an IS deviation, then she can perform a deviation satisfying solitary homogeneity, simply by forming the homogeneous singleton coalition instead of joining existing homogeneous coalitions. Hence, assuming solitary homogeneity of deviations yields valid selection rules, i.e., whenever a deviation is possible, then solitary homogeneity does not prohibit all possible deviations.

In the second part of this section, we show that combining all considered restrictions leads to convergence of the dynamics. In other words, the IS dynamics may cycle if and only if any of the four properties of Theorem <ref> is violated. For the proof of Theorem <ref>, we make use of a lemma which already highlights the special role of homogeneous coalitions.

Given a set $R_a$ of red (or set $B_a$ of blue) agents (the subscripts indicate that we use these agents as auxiliary agents) whose preferences satisfy $\frac 23 \succ 1 \succ \frac 12$ (or $\frac 13 \succ 0 \succ \frac 12$), it is possible to create the homogeneous coalition $R_a$ (or $B_a$) by means of an individual dynamics starting from singleton coalitions.

We are ready to prove the theorem.

The dynamics of IS deviations may cycle in HDGs even if any three of the following restrictions apply:

* preferences are naturally single-peaked,

* preferences are strict,

* the starting partition is the , or

* all deviations satisfy solitary homogeneity.

We provide examples for any triple of the four restrictions. The example where all properties except the condition on the starting partition, and where all properties except deviation selection according to solitary homogeneity are satisfied are closely related. First we show how to deal with the former case. Then, we show how to reach a configuration within the cycle of this case by starting from the singleton coalition. However, for reaching this cycle, some of the performed deviations violate solitary homogeneity. We defer the other two examples to the appendix.

$(\lnot 3)$ We start with an example of an HDG where all preferences are strict and naturally single-peaked and all agents' deviations satisfy solitary homogeneity. Therefore, let us consider an HDG with 26 agents: 12 red agents and 14 blue agents.
There are four deviating agents: red agents $r_1$ and $r_2$ and blue agents $b_1$ and $b_2$, and four fixed coalitions $C_1$, $C_2$, $C_3$ and $C_4$ such that:

* $C_1$ contains 2 red agents and 4 blue agents;

* $C_2$ contains 5 red agents;

* $C_3$ contains 3 red agents and 2 blue agents;

* $C_4$ contains 6 blue agents.

The relevant part of the preferences of the agents is given below.[Throughout this proof, we only specify the relevant part of preferences. Since agents are only in coalitions with the specified ratios, all missing values can be inserted arbitrarily, possibly respecting single-peakedness. Note that if these preferences are naturally single-peaked, then they can easily be completed by inserting fractions in the right intervals.
For instance, the preferences by $b_1$ in the following can be completed as follows. The peak is at $\frac 38$, then we prefer values to the right of the peak over values to the left of the peak. Within the interval $[\frac 38, 1]$, smaller values are preferred to larger values. Within the interval $[0,\frac 38]$, larger values are preferred to smaller values. In particular, the displayed part of the preferences is naturally single-peaked because $\frac 27 < \frac 38 < \frac 57 < \frac 56$.]

$b_1:$     $\frac{3}{8} \succ \frac{5}{7} \succ \frac{5}{6} \succ \frac{2}{7}$

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

$r_1:$     $\frac{4}{7} \succ \frac{1}{4} \succ \frac{1}{7} \succ \frac{2}{3}$

$r_2:$     $\frac{1}{4} \succ \frac{3}{8} \succ \frac{3}{7} \succ \frac{1}{7}$

$C_1:$     $\frac{3}{8} \succ \frac{3}{7} \succ \frac{1}{3}$

$C_2:$     $\frac{5}{7} \succ \frac{5}{6} \succ 1$

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

$C_4:$     $\frac{1}{4} \succ \frac{1}{7} \succ 0$

Consider the sequence of IS deviations in Figure <ref> that describes a cycle of the dynamics.
The four deviating agents of the cycle $b_1$, $b_2$, $r_1$ and $r_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},\mathbf{r_2}\}$     $C_2$     $C_3 \cup \{\mathbf{b_2}\}$     $C_4 \cup \{\mathbf{r_1}\}$
$3/8$     $1$     $1/2$     $1/7$
(2) at ($(1)+(0.5,2)$) $C_1 \cup \{\mathbf{b_1}\}$     $C_2$     $C_3 \cup \{\mathbf{b_2}\}$     $C_4 \cup \{\mathbf{r_1},\mathbf{r_2}\}$
$2/7$     $1$     $1/2$     $1/4$
(3) at ($(1)+(4,4)$)  $C_1 \cup \{\mathbf{b_1}\}$     $C_2$     $C_3 \cup \{\mathbf{b_2},\mathbf{r_1}\}$     $C_4 \cup \{\mathbf{r_2}\}$
$2/7$     $1$     $4/7$     $1/7$
(4) at ($(2)+(7.5,0)$)  $C_1$     $C_2 \cup\{\mathbf{b_1}\}$     $C_3 \cup \{\mathbf{b_2},\mathbf{r_1}\}$     $C_4 \cup \{\mathbf{r_2}\}$
$1/3$     $5/6$     $4/7$     $1/7$
(5) at ($(1)+(8.5,0)$)  $C_1 \cup \{\mathbf{r_2}\}$     $C_2 \cup\{\mathbf{b_1}\}$     $C_3 \cup \{\mathbf{b_2},\mathbf{r_1}\}$     $C_4$
$3/7$     $5/6$     $4/7$     $0$
(8) at ($(1)+(0.5,-2)$)  $C_1\cup\{\mathbf{b_1},\mathbf{r_2}\}$     $C_2 \cup \{\mathbf{b_2}\}$     $C_3$     $C_4 \cup \{\mathbf{r_1}\}$
$3/8$     $5/6$     $3/5$     $1/7$
(6) at ($(8)+(7.5,0)$)  $C_1 \cup \{\mathbf{r_2}\}$     $C_2 \cup \{\mathbf{b_1},\mathbf{b_2}\}$     $C_3\cup \{\mathbf{r_1}\}$     $C_4$
$3/7$     $5/7$     $2/3$     $0$
(7) at ($(1)+(4,-4)$)  $C_1 \cup \{\mathbf{r_2}\}$     $C_2 \cup \{\mathbf{b_1},\mathbf{b_2}\}$     $C_3$     $C_4 \cup \{\mathbf{r_1}\}$
$3/7$     $5/7$     $3/5$     $1/7$
[arrow] (1) –node[midway,left]$r_2$ (2); [arrow] (2) –node[midway,left,above]$r_1$  (3); [arrow] (3) –node[midway,right,above]$b_1$  (4); [arrow] (4) –node[midway,right]$r_2$  (5); [arrow] (5) –node[midway,right]$b_2$  (6); [arrow] (6) –node[midway,below]$r_1$  (7);
[arrow] (7) –node[midway,below]$b_1$  (8); [arrow] (8) –node[midway,left]$b_2$  (1);

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

Note that all deviations result in non-homogeneous target coalitions, and therefore satisfy solitary homogeneity.

$(\lnot 4)$ Our next goal is to provide an example of cycling under strict and single-peaked preferences while the starting partition is the . Our example makes use of the previous example. As a first step, we show, how we can create the coalitions $C_i$ for $i\in [4]$ by starting from the singleton coalition. In a second step, we show how to add the deviators $r_1$, $r_2$, $b_1$, and $b_2$ of the previous example to these coalitions to reach a partition from the cycle. As a consequence, cycling can occur by following the cycle from the first part of the proof. For highlighting the relationship of the two examples, we will use bold face for the relevant part of the preferences of the constructed coalitions.

To create the desired coalitions, we use Lemma <ref> to create homogeneous auxiliary coalitions. We assume that we take new (auxiliary) agents for every step of every construction.

Now, we show how to create the coalitions $C_i$ for $i\in [4]$ one by one.

Creating $C_2$ and $C_4$
Given the insights gained in Lemma <ref>, it is straightforward to manufacture the homogeneous coalitions $C_2$ and $C_4$. Therefore, define the coalitions $C_2 = \{r_{2,i}\colon i\in [5]\}$ and $C_4 = \{b_{4,i}\colon i\in [6]\}$ together with the following strict and naturally single-peaked preferences.

$C_2:$     $\frac 23 \succ \boldsymbol{\frac 57 \succ \frac 56 \succ 1} \succ \frac 12$

$C_4:$     $\frac 13 \succ \boldsymbol{\frac 14 \succ \frac 17 \succ 0} \succ \frac 12$

Since the preferences satisfy the assumptions of Lemma <ref>, we can apply it to create $C_2$ and $C_4$.

Creating $C_1$
Creating the coalition $C_1$ is also not very difficult. We can simply apply Lemma <ref> to form a coalition of all the blue agents, and let the red agents join this coalition. More formally, consider the coalition $C_1 = \{b_{1,1}, b_{1,2}, b_{1,3}, b_{1,4}, r_{1,1}, r_{1,2}\}$ with the following strict and naturally single-peaked preferences.

$C_1:$     $\boldsymbol{\frac 38 \succ \frac 37 \succ \frac 13} \succ \frac 15 \succ 0 \succ \frac 12 \succ 1$

Note that here and in the following constructions, the considered agents can be of any color and we can just ignore the preference for $0$ or $1$ if we consider a red or blue agent from the set, respectively.

To form $C_1$, we can apply Lemma <ref> to form $B_a = \{b_{1,1}, b_{1,2}, b_{1,3}, b_{1,4}\}$. Then, $r_{1,1}$ and $r_{1,2}$ can perform IS deviations to join $B_a$ one after another. This results in the coalition $C_1$, as desired.

Creating $C_3$
The by far most difficult coalition to create is $C_3$, where we have to combine several steps. The central idea is to apply Lemma <ref> to create a sufficiently large homogeneous coalition of auxiliary blue agents. Then, the red agents of the future coalition $C_3$ will join. This is followed by having the blue agents of the former homogeneous coalition abandon the so created coalition. An essential step is to create further coalitions to incentivize them to perform the necessary deviations. Finally, the two blue agents from $C_3$ can join.

To this end, consider the coalition $C_3 = \{b_{3,1}, b_{3,2}, r_{3,1}, r_{3,2}, r_{3,3}\}$ with the following strict and naturally single-peaked preferences.

$C_3:$     $\boldsymbol{\frac 47 \succ \frac 12 \succ \frac 35} \succ \frac 34 \succ \frac 3{10} \succ \frac 29 \succ \frac 18 \succ 1 \succ 0$

For creating $C_3$, we consider a set of auxiliary agents $A$ containing agents  with single-peaked preferences with peak at $\frac{4}{13}$ and satisfying $\frac 13 \succ \frac 3{11} \succ 0 \succ \frac 12 \succ 1$.

Now, let $i\in [7]$ and consider a set of blue agents $C_{3,1} = \{b_{a,i}\colon i \in [7]\}\subseteq A$. By Lemma <ref>, we can create the coalition $C_{3,1}$. Now, since we move the coalition ratio towards the peak of the blue agents, we can have the red agents from $C_3$ join one by one to form the coalition $C_{3,2} = C_{3,1} \cup \{r_{3,1}, r_{3,2}, r_{3,3}\}$. For this, note that $\frac 3{10} < \frac 4{13}$. The next goal is to get rid of the agents in $C_{3,1}$. To make this happen, we create auxiliary coalitions such that the agents in $C_{3,1}$ can move there and get into a most preferred coalition. Therefore, we create $7$ identical coalitions as follows. By Lemma <ref>, we can create a homogeneous coalition consisting of $8$ blue agents from $A$. Then, we let $4$ red agents from $A$ join one after another. Note that this only consists of IS deviations, even though we cross the peak of these agents, because all agents satisfy $\frac 4{12} = \frac 13 \succ \frac 3{11}$. Also, all agents in the resulting coalition would allow another blue agent to join, because this deviation would lead to reaching the peak of $\frac 4{13}$. Hence, we let the agents from $C_{3,1}$, one after another, deviate to distinct auxiliary coalitions. All of these steps are a strict improvement for the deviators leaving $C_{3,2}$. The first of the deviators leaves a coalition of ratio $\frac 3{10}$ and reaches her peak. Afterwards, the ratio of the abandoned coalitions is at least $\frac 39 = \frac 13 > \frac 4{13}$ and therefore all other deviators improve strictly.

We obtain the coalition $\{r_{3,1}, r_{3,2}, r_{3,3}\}$ and the blue agents from $C_3$ can join one after another to form coalition $C_3$.

Starting cycling
The final step for this example is to show how to start the cycle constructed in the first HDG. Therefore, we have to add the deviator agents $r_1$, $r_2$, $b_1$, and $b_2$ with the following preferences.

$b_1:$     $\frac{3}{8} \succ \frac{5}{7} \succ \frac{5}{6} \succ \frac{2}{7} \succ 0$

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

$r_1:$     $\frac{4}{7} \succ \frac{1}{4} \succ \frac{1}{7} \succ \frac{2}{3} \succ 1$

$r_2:$     $\frac{1}{4} \succ \frac{3}{8} \succ \frac{3}{7} \succ \frac{1}{7} \succ 1$

Given the constructed coalitions $C_i$, $i\in [4]$, we perform the following IS deviations:

* Agent $r_2$ joins coalition $C_1$.

* Agent $b_1$ joins coalition $C_2$.

* Agent $b_2$ joins coalition $C_3$.

* Agent $r_1$ joins coalition $C_3\cup \{b_2\}$.

This results in a partition that occurs in the cycle of the first example. Hence, the IS dynamics can cycle as shown before.

The previous examples do not show the impossibility to reach an IS partition since, e.g., in the first case, the IS partition $\{C_1\cup\{b_1,r_2\},C_2,C_3\cup\{r_1,b_2\},C_4\}$ can be reached via IS deviations from some partitions in the cycle. Thus, starting in these partitions, a path to stability may still exist.
Nevertheless, it may be possible that every sequence of IS deviations cycles, even for strict or naturally single-peaked preferences (with indifference), as the next proposition shows.
An interesting open question is whether strict and naturally single-peaked preferences allow for the existence of a path to stability.

The dynamics of IS deviations may never reach an IS partition in HDGs, whatever the chosen path of deviations, even
for (1) strict preferences or (2) naturally single-peaked preferences with indifference.

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, with on the left the preferences for the case of $(1)$ strict preferences, where $[...]$ denotes an arbitrary order over all possible remaining ratios, and on the right the preferences for the case of $(2)$ naturally single-peaked preferences with indifference, where all agents except $r$ and $b$ are indifferent between all possible coalitions.

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

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

$C_1:$     $\frac{3}{4} \succ \frac{2}{3} \succ 1 \succ [...]$

$C_2:$     $\frac{2}{5} \succ \frac{1}{5} \succ \frac{1}{4} \succ [...]$

$C_3:$     $\frac{1}{4} \succ \frac{1}{3} \succ 0 \succ [...]$

$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{3}{4} \sim \frac{2}{3} \succ 0$

$i\in N\setminus\{r,b\}:$     $C\sim C'$,   $\forall C,~C'\in \N_i$

Consider the sequence of IS deviations in Figure <ref> that describes a cycle of 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);

Impossibility of convergence of IS dynamics in the proof of Proposition <ref>.

Note that at each state, the deviation performed by agent $r$ or $b$ is the only possible one that they can do.
Moreover, by construction of the preferences of the other agents,
none of them has incentive to deviate at any state.
Therefore, the cycle is the only possible sequence of IS deviations, and the cycle cannot be avoided in this instance.

It remains open whether there always exists an path to stability when starting from the .
However, we show now that convergence is guaranteed by combining all restrictions of Theorem <ref>. Interestingly, part of the proof is a reduction to the positive result about AHGs, and reveals a close relationship of the two classes of hedonic games if HDGs are sufficiently restricted. However, this reduction requires careful preprocessing of the initial HDG. The first key insight is to show that, for every coalition occurring during the dynamics, there exists a color such that at most one agent of this color is part of the coalition. Consequently, given an instance with $b$ blue and $r$ red agents, the only important ratios (apart from $0$ and $1$) are $\frac{k}{k+1}$ and $\frac 1{k'+1}$, where $1\le k\le r$ and $1\le k' \le b$. The next step is to show how to transition to an HDG where every agent will only end up in coalitions of one of these ratio types. This transition is essentially performed by omitting certain steps in the dynamics. From there, we can observe the structure of an AHG by identifying the ratios $\frac{k}{k+1}$ and $\frac 1{k+1}$ with a coalition size of $k + 1$. This correspondence is reasonable. For instance, the former ratio corresponds to a coalition with one blue and $k$ red agents, i.e., a total number of $k + 1$ agents. We can apply Theorem <ref> to bound the length of the transformed HDG. Interestingly, the identification with an AHG requires some auxiliary agents, and the transformed dynamics is not starting from the anymore. In this respect, we even need the full power of Theorem <ref>.

The dynamics of IS deviations satisfying solitary homogeneity always converges in $\mathcal O(n^5)$ steps when starting from the in an HDG where agents have strict and naturally single-peaked preferences.

Consider an HDG with agent set $N = R\cup B$, where agents have strict and naturally single-peaked preferences. Let $(\partition_k)_{k = 0}^K$ be a sequence of partitions of an execution of the dynamics of IS deviations satisfying solitary homogeneity, where $\partition_0$ is the and, for every $1\le k \le K$, $\partition_k$ evolves from $\partition_{k-1}$ by an IS deviation of agent $d_k$.

The first step of the proof is to show the specific structure of the attained coalitions.

For every $k\ge 0$, it holds that every coalition in $\partition_k$ is of the form $\{r_1\}$, $\{b_1\}$, $\{r_1,b_1,\dots,b_m\}$, or $\{b_1,r_1,\dots,r_{m'}\}$, where $1 \le m\leq |B|$ and $1 \le m'\leq |R|$ and $r_i\in R$ and $b_j\in B$ for every $i\in [m']$, $j\in [m]$. Moreover, the following statements hold:

* If $\{r_1,b_1,\dots,b_m\}\in \partition_k$ for $m\ge 2$, then
$\frac{1}{m+1} \succ_{r_1} \frac{1}{m} \succ_{r_1} \dots \succ_{r_1} \frac{1}{2} \succ_{r_1} 1$.

* If $\{b_1,r_1,\dots,r_{m'}\}\in \partition_k$ for $m'\ge 2$, then
$\frac{m'}{m'+1} \succ_{b_1} \frac{m' - 1}{m'} \succ_{b_1} \dots \succ_{b_1} \frac{1}{2} \succ_{b_1} 0$.

We will show by induction over $k$ for $0\le k \le K$ that every coalition in $\partition_k$ is of the form $\{r_1\}$, $\{b_1\}$, $\{r_1,b_1,\dots,b_m\}$, or $\{b_1,r_1,\dots,r_{m'}\}$, where $b_i\in B$ and $r_j\in R$ for every $i\in [m]$, $j\in [m']$, $1 \le m\leq |B|$, and $1 \le m'\leq |R|$. Simultaneously to this main claim, we will prove the additional statements as auxiliary claims.

Clearly, the satisfies the main and auxiliary claims. Now, assume that the assertion is true for some fixed $0 \le k < K$.
Assume without loss of generality that $d_{k+1}$ is a red agent (the case for a blue agent is symmetric and uses the second auxiliary claim where we use the first auxiliary claim). We have to consider the two coalitions affected by $d_{k+1}$ to show that $\partition_{k+1}$ satisfies the claims.

First, assume for contradiction that the coalition $\partition_{k+1}(d_{k+1})$ breaks the main claim. Then, $\partition_{k+1}(d_{k+1}) \setminus \{d_{k+1}\}$ is of the form $\{r_1\}$ or $\{r_1,b_1,\dots,b_m\}$ with $2 \le m \le |B|$. The former case is excluded as the deviation satisfies solitary homogeneity. In the latter case, $\frac 2{2+m} > \frac 1 m > \frac 1{m+1}$, and we know by the first auxiliary claim in step $k$ that $\frac{1}{m+1} \succ_{r_1} \frac{1}{m}$. Hence, single-peakedness implies $\frac 1m \succ_{r_1} \frac 2{2+m}$, and, by transitivity of the preferences, we obtain that $\frac{1}{m+1} \succ_{r_1} \frac 2{2+m}$. This contradicts the fact that the deviation by $d_{k+1}$ was approved by agent $r_1$. Hence, $\partition_{k+1}(d_{k+1})$ satisfies the main claim and must be of the form $\{b_1,r_1,\dots,r_{m'}\}$, where $m'\ge 1$.

We proceed with the auxiliary claims for this coalition. As the coalition contains only one blue agent, the first auxiliary claim is vacant. Further, since $b_1$ gave her consent to letting $d_{k+1}$ join, it satisfies the second auxiliary claim (extending the second auxiliary claim for $b_1$ at step $k$) if $m'\ge 3$. If $m' = 2$, then the consent of $b_1$ implies $\frac 23 \succ_{b_1} \frac 12$, and single-peakedness implies $\frac 23 \succ_{b_1} \frac 12 \succ_{b_1} 0$. If $m' = 1$, this claim is also vacant.

Second, assume for contradiction that the coalition abandoned by agent $d_{k+1}$ violates the main claim. Then, $\partition_k(d_{k+1})$ was of the form $\{r,b_1,\dots,b_m\}$ with $m\ge 2$ and $r = d_{k+1}$. We already know that $\partition_{k+1}(d_{k+1})$ is of the desired form. It cannot be the coalition $\{r\}$, because of the first auxiliary claim for $r$. Also, it cannot be of the form $\{r,\hat b_1,\dots,\hat b_{\hat m}\}$ with $\hat m\ge 2$, because then $\partition_k(\hat b_1)$ violates the main claim in step $k$. Hence, we know that $\partition_{k+1}(d_{k+1})$ is of the form $\{b,r_1,\dots,r_{m'}\}$ with $m' \ge 1$. Using $m\ge 2$, we have that $\frac 1{m+1} < \frac{m'}{m'+1} < 1$ and, since the deviation was performed by $d_{k+1}$, also $\frac{m'}{m'+1} \succ_{d_{k+1}} \frac 1{m+1}$. Hence, single-peakedness implies $1  \succ_{d_{k+1}} \frac{m'}{m'+1}$, and therefore, by transitivity, $1  \succ_{d_{k+1}} \frac 1{m+1}$. However, this contradicts the first auxiliary claim for agent $d_{k+1} = r$ in $\partition_k$.

It remains to prove the auxiliary claims for the abandoned coalition. The first auxiliary claim is vacant. The second auxiliary claim follows directly by induction, whenever it is not vacant.

In the sequel, we use the notation $f_i(\partition) = \frac{|R\cap \partition(i)|}{|\partition(i)|}$, which specifies the fraction of red agents in the coalition of agent $i$ with respect to partition $\partition$.
Also, given an agent $i$, denote her peak by $p_i$. We distinguish agents according to their peaks. To this end, define the agent sets

* $R_S = \{r\in R\colon 0 < p_r < 1/2\}$,

* $R_L = \{r\in R\colon 1/2 \le p_r \le 1\}$,

* $B_S = \{b\in B\colon 0 \le p_b \le 1/2\}$, and

* $B_L = \{b\in B\colon 1/2 < p_b < 1\}$.

The subscripts indicate whether the peak is large ($L$) or small ($S$). We would like to analyze a dynamics where $f_i(\partition)$ is always close to the peak of an agent. This is achieved by agents in $R_L$ and $B_S$.

Let $k\ge 0$. Then, the following statements hold:

* If $r\in R_L$, then $f_r(\partition_k)\ge \frac 12$.

* If $b\in B_S$, then $f_b(\partition_k)\le \frac 12$.

We show the statement by induction over $k$ for $0\le k \le K$. Clearly, the statement is true for $k = 0$, because $\partition_0$ is the . Now, assume that the assertion is true for some fixed $0 \le k < K$. We assume without loss of generality that agent $d_{k + 1}$ is red (the case of a blue agent follows from a symmetric argument). Clearly, all agents not affected by the deviation maintain the two invariants claimed in the lemma. Therefore, we have to consider the abandoned and joined coalitions.

By Claim <ref>, $\partition_k(d_{k+1})$ is of the form $\{d_{k+1}\}$ or $\{b_1, r_1, \dots, r_m, d_{k+1}\}$ for some $m\ge 0$, where $b_1 \in B$ and $r_1,\dots, r_m\in R$. The former case is irrelevant because then the abandoned coalition does not exist anymore. In the latter case, $f_{b_1}(\partition_{k+1}) < f_{b_1}(\partition_k)$, and the second invariant follows by induction if $b\in B_S$.
Furthermore, if $m\ge 1$, then $f_{b_1}(\partition_{k + 1}) \ge \frac 12$, and the first invariant is true for all red agents the abandoned coalition (in particular if they are in $R_L$).

Applying Claim <ref> again, $\partition_{k+1}(d_{k+1})$ is also of the form $\{d_{k+1}\}$ or $\{b_1, r_1, \dots, r_{m'}, d_{k+1}\}$ for some $m'\ge 0$, where $b_1 \in B$ and $r_1,\dots, r_{m'}\in R$. Hence, the first invariant is satisfied for all red agents and for $b_1$ if $m' = 0$. It remains the case $m' \ge 1$. Then, since the deviation was approved by agent $b_1$, it holds $\frac{m' + 1}{m'+2} \succ_{b_1} \frac{m'}{m'+1}$. Then, single-peakedness implies that $p_{b_1} > \frac{m'}{m'+1} \ge \frac 12$ and therefore $b_1\notin B_S$. Hence, the second invariant is vacant in this case.

Altogether, we have shown that both invariants are satisfied for partition $\partition_{k+1}$, which completes the induction step.

(d1) at (0,0) $(\partition_k)_{k = 1}^K$;
(d2) at (3.5,0) $(\sigma_k)_{k = 1}^K$;
(d3) at (7,0) $(\tau_l)_{l = 1}^L$;
(d4) at (10.5,0) $(\rho_p)_{p = 1}^P$;

[->] (d1) edge node[above] no undesirablenode[below] coalitions (d2);
[->] (d2) edge node[above] include mergingnode[below] deviations (d3);
[->] (d3) edge node[above] omit duplicatenode[below] partitions (d4);

Transformation of the dynamics in the proof of Theorem <ref>. In the first modification, we keep red agents with a small peak and blue agents with a large peak in a singleton coalition. This yields a sequence of partitions $(\sigma_k)_{k = 1}^K$ where some transitions are no valid IS deviation. We include some merging deviations to resolve this. Finally, we remove duplicate partitions to end up with a valid IS dynamics $(\rho_p)_{p = 1}^P$.

A similar statement is not true for agents in $R_S$ or $B_L$. Therefore, the next step will modify the dynamics such that agents are only contained in coalitions close to their peaks, unless they are in a singleton coalition. This is a sophisticated and tedious construction which will be performed in several steps. An outline is depicted in Figure <ref>. First, we prevent undesirable deviations by red agents with a small peak and blue agents with a large peak by keeping these agents in singleton coalitions. However, this yields a modified dynamics $(\sigma_k)_{k = 1}^K$ where some steps do not correspond to IS deviations. We therefore have to insert and omit certain steps.
Eventually, we will end up at a new dynamics  $(\rho_p)_{p = 1}^P$. This dynamics is easier to analyze because it corresponds to an AHG. Moreover, the convergence behavior of the original dynamics only depends on the convergence behavior of the new dynamics because we only omit a linear number of steps (with respect to $n$).
Hence, we can complete the proof by showing how to bound $K$, i.e., the length of the original dynamics, with respect to $P$, i.e., the length of the simpler dynamics.

We start with the first transformation. Given a partition $\partition$, define the subset of agents $F_{\partition} \subseteq N$ as $F_{\partition} = \{r\in R_S\colon \frac 12 < f_r(\partition) < 1\} \cup \{b\in B_L\colon \frac 12 > f_b(\partition) > 0\}$, i.e., the set of agents whose ratio is far from their peak.
By definition of $F_\partition$ and Claim <ref>, a red agent $r\in R\cap F_\partition$ is in a coalition of the form $\{b_1,r_1,\dots,r_m\}$ in partition $\partition$ and, symmetrically, a blue agent $b\in B\cap F_\partition$ is in a coalition of the form $\{r_1,b_1,\dots,b_m\}$ in partition $\partition$. Moreover, by Claim <ref> and strict single-peakedness of the preferences, an agent in $F_\partition$ is the last agent who entered her coalition in $\partition$.

Now, consider a modified dynamics $(\sigma_k)_{k = 0}^K$, where, for every $0\le k \le K$, $\sigma_k = \bigcup_{C\in \partition_k} \{C\setminus F_{\partition_k}\}\cup \bigcup_{i\in F_{\partition_k}}\{\{i\}\}$. This modification has essentially the following effects: We omit deviations of agents where they land in the set $F_{\partition}$ while keeping them in a singleton coalition. Sometimes, it can happen that the deviator satisfies $d_k\in F_{\partition_{k - 1}}\setminus F_{\partition_k}$. In this case, the modified dynamics sees the deviator join her new coalition from a singleton coalition. The second effect that can happen is the case where a non-deviator is in $F_{\partition_{k-1}}\setminus F_{\partition_k}$. This happens exactly if an agent in $F_{\partition_{k-1}}$ is abandoned, and thereby left in a coalition of size $2$, which consists of one agent of each type.
Hence, we insert a suitable deviation to obtain a valid modified dynamics of IS deviations. This requires two lemmas. The first lemma gives more structural insight and establishes that every coalition can contain at most one agent from $F_{\partition_k}$.

Let $0\le k \le K$ and $C\subseteq \partition_k$. Then, $|C\cap F_{\partition_k}|\le 1$. Moreover, consider $m>0$ and agents $r_1,\dots, r_m\in R$ and $b_1,\dots, b_m\in B$. Then, the following statements hold:

* If $\{b_1, r_1, \dots, r_m\}\in \partition_k$, then, for all $1\le i\le m$ with $r_i\notin F_{\partition_k}$, $f_{r_i}(\partition_k) \succeq_{r_i} f_{r_i}(\sigma_k)$.

* If $\{r_1, b_1, \dots, b_m\}\in \partition_k$, then, for all $1\le i\le m$ with $b_i\notin F_{\partition_k}$, $f_{b_i}(\partition_k) \succeq_{b_i} f_{b_i}(\sigma_k)$.

We show all statements simultaneously by induction over $k$ for $0\le k \le K$. Clearly, all statements are true for $k = 0$. Now, assume that the statements are true for some fixed $0 \le k < K$. Clearly, all coalitions in $\partition_{k+1}$ except possibly $\partition_k(d_{k+1})\setminus\{d_{k+1}\}$ and $\partition_{k + 1}(d_{k+1})$ satisfy the claim. Assume without loss of generality that $d_{k+1}$ is a red agent (the case of a blue agent is symmetric).

We start with the abandoned coalition. By Claim <ref>, $\partition_k(d_{k+1})\setminus\{d_{k+1}\}$ is the empty set (if $d_{k+1}$ was in a singleton coalition) or of the type $\{b_1,r_1,\dots, r_m\}$ where $b_1\in B$ and $r_1,\dots, r_m\in R$ for some $m\ge 0$.
In the former case, all claims are vacant, so assume the latter case. If $m = 0$, the abandoned coalition is a singleton coalition, and the assertions are true (the additional statements are then vacant). If $m = 1$, then $f_{b_1}(\partition_{k + 1}) = \frac 12$, and therefore $\partition_{k + 1}(b_1)\cap F_{\partition_{k+1}} = \emptyset$.
In particular, $\partition_{k + 1}(b_1) = \sigma_{k+1}(b_1)$, and all claims are true. If $m\ge 2$, it follows from $f_{b_1}(\partition_{k + 1})\ge \frac 23$ that $b_1\notin F_{\partition_{k+1}}$. Moreover, $\{r_1,\dots, r_m\} \cap F_{\partition_{k+1}}\subseteq \{r_1,\dots, r_m\} \cap F_{\partition_k}$. Therefore, $|\partition_{k + 1}(b_1)\cap F_{\partition_{k+1}}|\le 1$ follows from induction for step $k$, which implies that $|\{r_1,\dots, r_m\} \cap F_{\partition_k}| \le |\partition_k(b_1)\cap F_{\partition_k}|\le 1$. Additionally, the additional statement is trivially true unless $\{r_1,\dots, r_m\} \cap F_{\partition_{k+1}}\neq \emptyset$, say $r_1\in F_{\partition_{k+1}}$. Then, $r_1\in F_{\partition_k}$ and we have that $f_{b_1}(\sigma_{k + 1}) < f_{b_1}(\partition_{k + 1}) = f_{b_1}(\sigma_k) < f_{b_1}(\partition_k)$. Let $2\le i\le m$. Then, induction implies
$f_{r_i}(\partition_k) \succ_{r_i} f_{r_i}(\sigma_k)$. Hence, single-peakedness implies $f_{r_i}(\partition_{k+1}) \succ_{r_i} f_{r_i}(\sigma_{k+1})$.

The proof for the joined coalition is similar. Using Claim <ref> again, we know that $\partition_{k+1}(d_{k+1})$ is a singleton coalition or of the type $\{b_1,r_1,\dots, r_m, d_{k+1}\}$ where $b_1\in B$ and $r_1,\dots, r_m\in R$ for some $m\ge 0$. A singleton coalition fulfills the claim. Therefore, assume the latter case. Since $f_{b_1}(\partition_{k + 1})\ge \frac 12$, it holds that $b_1\notin F_{\partition_{k+1}}$. Moreover, if $m\ge 1$ and $1\le i\le m$, then $\frac {m+1}{m+2}\succ_{r_i}\frac m{m+1}$ and single-peakedness implies that $p_{r_i} > \frac m{m+1}\ge \frac 12$. Hence, $r_i\notin R_S$, and therefore $r_i\notin F_{\partition_{k+1}}$. Together, $\partition_{k+1}(d_{k+1})\cap F_{\partition_{k + 1}}\subseteq \{d_{k+1}\}$, and the first statement is true. The additional statement is clear if $d_{k+1}\notin F_{\partition_{k + 1}}$, in which case $\partition_{k+1}(b_1) = \sigma_{k+1}(b_1)$. If $d_{k+1}\in F_{\partition_{k + 1}}$, it follows for the other red agents, because they approve that $d_{k+1}$ joins.

We are ready to show how to obtain the valid dynamics.

Let $1\le k \le K$. If $\sigma_k \neq \sigma_{k-1}$, then $\sigma_k$ evolves from $\sigma_{k-1}$ by performing at most $2$ IS deviations. If two deviations have to be performed, then the intermediate partition evolves from $\sigma_{k-1}$ by merging two agents from singleton coalitions.

Let $1\le k \le K$ with $\sigma_k \neq \sigma_{k-1}$. The only agents that matter to us are in $\partition_k(d_k)\cup \partition_{k - 1}(d_k)$. Other agents did not change their coalition in the original dynamics, and therefore, their membership in $F_{\partition_k}$ is also not affected. Without loss of generality, we assume that $d_k$ is a red agent (the case of a blue agent is again symmetric).

First, we show that $(\partition_k(d_k)\setminus \{d_k\}) \cap F_{\partition_{k-1}} = \emptyset$ and $\partition_k(d_k)\cap F_{\partition_k} = \emptyset$. Assume for contradiction that this is not the case. By Claim <ref>, this can only be the case if $\partition_k(d_k)$ is of the form $\{b_1,r_1,\dots, r_m, d_k\}$ where $b_1\in B$ and $r_1,\dots, r_m\in R$ for some $m\ge 1$. As $f_{b_1}(\partition_k)\ge \frac 23$ and $f_{b_1}(\partition_{k - 1})\ge \frac 12$, $b_1\notin F_{\partition_k}$ and $b_1\notin F_{\partition_{k-1}}$, respectively.
For $1\le i \le m$, it holds that $\frac{m+1}{m+2}\succ_{r_i} \frac m{m + 1}$, and therefore, by single-peakedness, $p_i > \frac m{m + 1} \ge \frac 12$. Hence, $r_i\in R_L$, and therefore $r_i\notin  F_{\partition_k}$ and $r_i\notin F_{\partition_{k-1}}$. This shows already that $(\partition_k(d_k)\setminus \{d_k\}) \cap F_{\partition_{k-1}} = \emptyset$.

Finally, it remains to exclude that $d_k \in F_{\partition_k}$. Assume for contradiction that $d_k \in F_{\partition_k}$. Then, our considerations about $\partition_k(d_k)$ imply that $\sigma_k(b_1) = \sigma_{k-1}(b_1)$. Moreover, by Claim <ref>, $f_{d_k}(\partition_{k-1}) \ge \frac 12$. Since $d_k \in F_{\partition_k}$, it holds that $p_{d_k} < \frac 12$. As we already know that $f_{d_k}(\partition_k) > \frac 12$, single-peakedness and the fact that $d_k$ has improved her ratio imply that $f_{d_k}(\partition_{k-1}) \ge f_{d_k}(\partition_k) > \frac 12$. Therefore, $d_k \in F_{\partition_{k-1}}$ and Claim <ref> implies that $(\partition_{k-1}(d_k)\setminus\{d_k\}) \cap F_{\partition_{k-1}} = \emptyset$. Additionally, $f_{d_k}(\partition_{k-1}) > \frac 12$ also implies that $(\partition_{k-1}(d_k)\setminus\{d_k\}) \cap F_{\partition_k} = \emptyset$. Hence, the coalition abandoned by $d_k$ has not changed from $\sigma_{k-1}$ to $\sigma_k$.
Together, this contradicts that $\sigma_k \neq \sigma_{k-1}$. Hence, our assumption that $d_k \in F_{\partition_k}$ was wrong, and therefore $\partition_k(d_k)\cap F_{\partition_k} = \emptyset$. In particular, we have shown so far that

\begin{equation}\label{eq:shortcutlemma-welcoming}
\sigma_{k-1}(b_1) = \partition_{k-1}(b_1)\textnormal{ and }\sigma_k(b_1) = \partition_k(b_1) = \partition_{k-1}\cup\{d_k\}\text.
\end{equation}

Next, we consider the abandoned coalition. By Claim <ref>, the coalition $\partition_{k-1}(d_k)$ is of the form $\{d_k\}$ or $\{b'_1,r'_1,\dots, r'_{m'}, d_k\}$ where $b'_1\in B$ and $r'_1,\dots, r'_{m'}\in R$ for some $m'\ge 0$. In the first case, we know that $\{d_k\}\in \sigma_{k-1}$, and, together with Equation <ref>, $\sigma_{k-1} = \partition_{k-1}$ and $\sigma_k = \partition_k$. Therefore, $\sigma_k$ evolves from $\sigma_{k-1}$ by an IS deviation of agent $d_k$.

Next, we consider the case that $\partition_{k-1}(d_k)$ is of the form $\{b'_1,r'_1,\dots, r'_{m'}, d_k\}$. Note that $f_{b'_1}(\partition_{k-1})\ge \frac 12$ and $f_{b'_1}(\partition_k)\ge \frac 12$ or $f_{b'_1}(\partition_k) = 0$ and therefore $b'_1\notin F_{\partition_{k-1}}$ and $b'_1\notin F_{\partition_k}$. Moreover, it holds that $\{r'_1,\dots, r'_{m'}\} \cap F_{\partition_k}\subseteq \{r'_1,\dots, r'_{m'}\} \cap F_{\partition_{k - 1}}$. We are ready to consider the final cases.

First assume that $d_k\in F_{\partition_{k - 1}}$. Then, Claim <ref> and the considerations in the previous paragraph imply that $\{b'_1,r'_1,\dots, r'_{m'}\} \cap F_{\partition_k} = \emptyset$ and $\{b'_1,r'_1,\dots, r'_{m'}\} \cap F_{\partition_{k - 1}} = \emptyset$. Hence, $\{b'_1,r'_1,\dots, r'_{m'}\}\in \sigma_k$ and  $\{b'_1,r'_1,\dots, r'_{m'}\}\in \sigma_{k-1}$. This, together with Equation <ref> and the definition of $\sigma_{k-1}$ implies that $\sigma_k$ evolves from $\sigma_{k-1}$ by a unilateral deviation of agent $d_k$ from a singleton coalition to coalition $\sigma_k(d_k)$. Since $\sigma_k \neq \sigma_{k-1}$, we know that $\sigma_k(d_k) \neq \{d_k\}$. Hence, $\frac 12 \le f_{d_k}(\sigma_k) < 1$. This, together with $d_k\in R_S$ implies that $p_{d_k} \le f_{d_k}(\sigma_k) < 1$. Hence, single-peakedness implies that the deviation was a Nash deviation. By Equation <ref>, the deviation was also approved by all agents in the joined coalition. Hence, $\sigma_k$ evolves from $\sigma_{k-1}$ through an IS deviation of agent $d_k$.

It remains the case that $d_k\notin F_{\partition_{k - 1}}$. If $\{r'_1,\dots, r'_{m'}\} \cap F_{\partition_{k - 1}} = \emptyset$, then $\sigma_{k-1} = \partition_{k-1}$ and, together with Equation <ref>, $\sigma_k$ evolves from $\sigma_{k-1}$ by an IS deviation of agent $d_k$.

Assume therefore that there exists $1\le i\le m'$ with $r'_i\in F_{\partition_{k - 1}}$. If $m'\ge 2$, then $\{b'_1,r'_1,\dots, r'_{m'}\} \cap F_{\partition_{k - 1}} = \{b'_1,r'_1,\dots, r'_{m'}\} \cap F_{\partition_k}$. In this case, $\sigma_k$ evolves from $\sigma_{k-1}$ through a unilateral deviation of $d_k$.
Since $d_k\notin F_{\partition_{k - 1}}$, the first additional statement of Claim <ref> implies that $f_{d_k}(\partition_{k-1}) \succeq_{d_k} f_{d_k}(\sigma_{k-1})$. Therefore, $d_k$ performs a Nash deviation because she performed a Nash deviation from $\partition_{k-1}$ to $\partition_k$. The consent of the joined coalition follows again from Equation <ref>.

Finally, assume that $\{r'_1,\dots, r'_{m'}\} \cap F_{\partition_{k - 1}} \neq \emptyset$ and $m' = 1$. Then, $\partition_{k-1}(b'_1) = \{b'_1,r'_1,d_k\}$ and $r'_1 \in  F_{\partition_{k - 1}}$. Hence, $\sigma_k$ evolves from $\sigma_{k-1}$ by transforming $\{r'_1\}$, $\{b'_1,d_k\}$, and $\partition_k(d_k)\setminus\{d_k\}$ into $\{b'_1,r'_1\}$ and $\partition_k(d_k)$. These changes can be achieved by two unilateral deviations. First, $d_k$ joins $\partition_k(d_k)\setminus\{d_k\}$ and then $r'_1$ joins $b'_1$. The first deviation is an IS deviation as in the previous case. The second deviation is also an IS deviation. The approval of $b'_1$ follows from the second auxiliary statement in Claim <ref> applied to $\partition_{k-1}(b'_1) = \{b'_1,r'_1,d_k\}$. Also, the deviation is improving for $r'_1$, because $r'_1\in F_{\partition_{k - 1}}$. Therefore $r'_1\in R_S$. Hence, $1 > \frac 12 \ge p_{r'_1}$, and therefore $\frac 12 \succ_{r'_1} 1$.

Using the insights gained in the previous claim, we can define a valid modified dynamics based on $(\sigma_k)_{k=1}^K$. First, we insert the partitions identified in the proof of Claim <ref> where two agents are merged. This yields a dynamics $(\tau_l)_{l=1}^L$ such that $\tau_l$ evolves from $\tau_{l-1}$ through a deviation of agent $\hat d_l$ whenever $\tau_l \neq \tau_{l-1}$. Then, we remove all steps where $\tau_l = \tau_{l-1}$ to obtain a dynamics $(\rho_p)_{p=1}^P$, which is a dynamics where every step corresponds to an IS deviation.
Define the index set $I = \{1\le k\le K\colon \sigma_k = \sigma_{k-1}\}$, that is, the set of steps where the modified dynamics remains unchanged. Then, $K \le L = |I| + P$.

Hence, we would like to obtain bounds on each of $|I|$ and $P$.
The next claim allows us to bound $|I|$ by replacing it with an appropriate bound with respect to $P$. The key insight for proving the next claim follows from the observation that essentially every $n$-th deviation of an agent has to correspond to a deviation of the modified dynamics.

It holds that $L \le n^2 + nP$.

We first show that if $\sigma_k = \sigma_{k-1}$, then $d_k\in F_{\partition_k}$. We prove this fact by contraposition. Assume that $d_k\notin F_{\partition_k}$. Note that, by the definition of $F_{\partition}$, it holds for every partition $\partition$ and every coalition $C\in \partition$ with $C\cap F_{\partition}\neq \emptyset$ that $|C|\ge 3$. Now, if $\sigma_k(d_k) \neq \{d_k\}$, then there exists an agent $x\in \sigma_k(d_k)\setminus\{d_k\}$. Since $d_k$ was the deviator, it holds that $\sigma_k(x)\neq \sigma_{k-1}(x)$ and therefore $\sigma_k \neq \sigma_{k-1}$. It remains the case that $\sigma_k(d_k) = \{d_k\}$. Then, as $d_k\notin F_{\partition_k}$, $\partition_k(d_k) = \{d_k\}$. This implies that $d_k\notin F_{\partition_{k - 1}}$. To see this, we assume without loss of generality that $d_k\in R$. Indeed, if $d_k\in F_{\partition_{k - 1}}$, then $d_k\in R_S$ and $\frac 12 \le f_{d_k}(\partition_{k - 1})$. Then, single-peakedness implies that $f_{d_k}(\partition_{k - 1})\succ_{d_k} 1$, contradicting that $d_k$ performed an IS deviation to form a singleton coalition. Hence, $d_k\notin F_{\partition_{k - 1}}$. As in the first case, we find an agent $x\in \sigma_{k-1}(d_k)\setminus\{d_k\}$, for which it holds that  $\sigma_k(x)\neq \sigma_{k-1}(x)$ and therefore $\sigma_k \neq \sigma_{k-1}$.

The key insight for this claim is that every agent can only perform few successive deviations corresponding to steps in $I$. Indeed, the first part of the proof implies that $d_k\in F_{\partition_k}$ whenever $k\in I$.
Consider an arbitrary agent $r\in R_S$.
We define a potential function

$$\lambda_r(\partition) = \begin{cases}
|R| + 1 & f_r(\partition) \le \frac 12 \textnormal{ or } f_r(\partition) = 1\\
m & f_r(\partition) = \frac m{m+1} \textnormal{ for } 2\le m \le |R|
\end{cases}\text.$$

Note that $\lambda_r$ is integer-valued and $2\le \lambda_r\le |R| + 1$. We will show that $\lambda_r$ decreases whenever $r$ performs a deviation at step $k$ where she lands in $F_{\partition_{k}}$, and can only increase through a deviation of $r$ in $(\tau_l)_{l=1}^L$. In particular, we will show that the potential does not increase if another agent performs a deviation, unless when $r\in F_{\partition_{k-1}}\setminus F_{\partition_{k}}$ which corresponds to the case of inserting a deviation by $r$, which also corresponds to a deviation in $(\tau_l)_{l=1}^L$.

Consider a step $k$ in the dynamics where $d_k = r$ and $r\in F_{\partition_k}$. Then, $\frac 12 < f_r(\partition_k) < 1$. By Claim <ref>, $f_r(\partition_k) = \frac m{m+1}$ for some $2\le m\le |R|$ and therefore $\lambda_r(\partition_k) = m$. Also, by Claim <ref>, $r$ is not allowed to perform a deviation if $f_r(\partition_{k-1}) < \frac 12$ (as then an invalid homogeneous coalition of blue agents would remain). Hence, single-peakedness implies that $f_r(\partition_{k-1}) > \frac m{m+1}$, and therefore $\lambda_r(\partition_k) < \lambda_r(\partition_{k-1})$.

If $d_k = r$ and $r\notin F_{\partition_k}$, then a deviation happens where $\sigma_k \neq \sigma_{k-1}$, and therefore this corresponds to a deviation of $r$ in $(\tau_l)_{l=1}^L$.
Next, we want to inspect how $r$ is affected from a deviator if $d_k \neq r$. In this case, $d_k$ cannot join $\partition_{k-1}(r)$ if $\lambda_r(\partition_{k-1})\le |R|$ (that is, in the case where $r$ is in a coalition of `large' ratio).
Indeed, since $r\in R_S$, $r$ would block any red agent to join, and a blue agent cannot join due to Claim <ref>. Hence, $\partition_{k-1}(r)$ is only affected if $d_k\in \partition_{k-1}(r)$. By Claim <ref>, if $|\partition_{k-1}(r)| =2$, then $f_r(\partition) = \frac 12$, and the potential cannot go up.
Otherwise, Claim <ref> implies that $d_k$ is red. Since $r\in R_s$, it holds in addition that $r\notin F_{\partition_{k-1}}$. Hence, if $|\partition_{k-1}(r)|\ge 4$, then $\lambda_r(\partition_k) = \lambda_r(\partition_{k-1}) - 1$. If $|\partition_{k-1}(r)|= 3$, then $\partition_{k}(r)$ is of size $2$ and $\lambda_r(\partition_k) = |R| + 1$. As then  $r\in F_{\partition_{k-1}}\setminus F_{\partition_{k}}$, this case corresponds exactly to inserting the deviation of $r$ to form a coalition of size $2$ in $(\tau_l)_{l=1}^L$.

Together, there can be at most $|R| - 1 \le n - 1$ successive deviations by $r$ corresponding to steps in $I$ until there is a deviation by $r$ in $(\tau_l)_{l=1}^L$. We obtain a bound for the deviations by $r$ which matter. To make this formal, we consider the following quantities. Given an agent $x$, define
$I_x = |\{k\in I \colon d_k = x\}|$ and $L_x = |\{1\le l \le L\colon \hat d_l = x\}|$. Since at least every $n$-th deviation counts towards $L_r$ but not towards $I_r$, we can conclude that $L_r - I_r \ge \lfloor \frac {L_r} n \rfloor\ge \frac {L_r} n - 1$.

By an analogous argument where we consider an analogous potential function for blue agents, we obtain that $L_b - I_b \ge \frac {L_b} n - 1$ for every $b\in B_L$. Additionally, the definition of $F_{\partition}$ implies that $k\notin I$ if $d_k\in R_L$ or $d_k\in B_S$. Hence, for $x\in R_L\cup B_S$, it holds that $L_x - I_x = L_x \ge \frac {L_x} n - 1$ (where the latter inequality is of course a strong estimate, but it is all we need).

Summing up the inequalities for all agents, we obtain

$$P = L - |I| = \sum_{x\in N} L_x - I_x \ge \sum_{x\in N} \frac {L_x} n - 1 = \frac L n - n\text.$$

Solving for $L$ yields the desired inequality.

It remains to analyze the dynamics $(\rho_p)_{p=1}^P$. To this end, we will show that this dynamics essentially behaves like a specific AHG, where we have to replace some agents by multiple copies. This yields an AHG with at most $n^2$ agents. Hence, Theorem <ref> would provide a running time of $\mathcal O(n^6)$. However, we can do better. By exploiting structural properties of the AHG and a close inspection of the potentials in the proof of Theorem <ref>, we can reduce the running time of our transformed dynamics on the AHG to $\mathcal O(n^4)$.

It holds that $P \in \mathcal O(n^4)$.

First, let us note that, by construction of $(\rho_p)_{p=0}^P$, $F_{\rho_p} = \emptyset$ for all $0\le p\le P$.
Hence, all agents in $R_S$ (or $B_L$) only perform deviations towards singletons or coalitions of ratio at most $\frac 12$ (or at least $\frac 12$). Moreover, we may assume that an agent $r\in R_S$ never forms a coalition of size $2$ with an agent in $b\in B_L$. Due to single-peakedness and their respective peaks, this can only happen if both of them come from singleton coalitions. However, then no further agent can join $\{r,b\}$. Further red agents would be blocked by $r$ and further blue agents by $b$. Hence, this coalition can only be altered if one of these agents leaves. But this deviation can be performed right away from the singleton coalition. Similarly, we can exclude the formation of coalitions of size $2$ by agents in $R_L$ and $B_S$.

As this shortcutting can only remove every second step (and an initial $n/2$ steps for forming a first set of pairs), it leaves us with a dynamics $(\rho'_p)_{p=0}^{P'}$ with $P'\ge \frac {P-n/2}2$ such that, for $1\le p\le P'$, $\rho'_p$ evolves from $\rho'_{p-1}$ through an IS deviation of some agent $d'_p$.

Even more, we may assume that agents in $R_S$ (or $B_L$) never perform deviations. First, according to Claim <ref>, the only coalition which such an agent can leave is a coalition of size $2$ with ratio $\frac 12$. Hence, single-peakedness implies that forming the singleton coalition is not beneficial.
Furthermore, Claim <ref> implies that they could only form coalitions of size $2$. By the first part of the proof, their partner has to be from $B_S$ (or $R_L$). Since the preferences are strict, we may assume that their partner performs the deviation.

Now, we define an AHG $(N^A, (\succ^A_x)_{x\in N^A})$ as follows. In principle, the only part of the preferences are on ratios $\frac 1{m+1}$ or $\frac m{m+1}$, and we want to identify these ratios with coalitions of size $m + 1$, because all coalitions of these ratios have exactly this size (using Claim <ref>). This part of the preferences will also inherit single-peakedness from the HDG. However, we have to deal with the preference over the ratio $1$ for agents in $R_L$ (or over the ratio $0$ for agents in $B_S$). To maintain single-peakedness, we should identify these ratios with coalition sizes $|R| + 1$ and $|B| + 1$, respectively. To achieve this goal, we introduce some auxiliary agents. Let the agent set of the AHG therefore be $N^A = R_S \cup B_L \cup \{r_0, \dots, r_{|R|}\colon r\in R_L\} \cup  \{b_0, \dots, b_{|B|}\colon b\in B_S\}$ and define strict and single-peaked preferences as follows (where we present only the relevant part of the preferences).

* If $r\in R_S$ and $2\le i,j \le |B| + 1$, then

* $i\succ^A_r j$ if and only if $\frac 1i \succ_r \frac 1j$,

* $1\succ^A_r i$ if and only if $1\succ_r \frac 1i$, and

* $i\succ^A_r 1$ if and only if $\frac 1i \succ_r 1$.

* If $b\in B_L$ and $2\le i,j \le |R| + 1$, then

* $i\succ^A_b j$ if and only if $\frac {i-1}i \succ_b \frac {j-1}j$,

* $1\succ^A_b i$ if and only if $0\succ_b \frac {i-1}i$, and

* $i\succ^A_b 1$ if and only if $\frac {i-1}i \succ_b 0$.

* If $r\in R_L$ and $2\le i,j \le |R|$, then

* $i\succ^A_{r_0} j$ if and only if $\frac {i-1}i \succ_{r} \frac {j-1}j$,

* $|R|+1\succ^A_{r_0} i$ if and only if $1\succ_{r} \frac {i-1}i$,

* $i\succ^A_{r_0} |R|+1$ if and only if $\frac {i-1}i \succ_{r} 1$, and

* $|R|+1\succ^A_{r_l} |R|$ if $l\in [|R|]$.

* If $b\in B_S$ and $2\le i,j \le |B|$, then

* $i\succ^A_{b_0} j$ if and only if $\frac 1i \succ_{b} \frac 1j$,

* $|B|+1\succ^A_{b_0} i$ if and only if $0\succ_{b} \frac 1i$,

* $i\succ^A_{b_0} |B|+1$ if and only if $\frac 1i \succ_{b} 0$, and

* $|B|+1\succ^A_{b_l} |B|$ if $l\in [|B|]$.

Next, we define the modified dynamics. Therefore, let $0\le p \le P'$ and define the partition $\omega_p = \{\{r_0, \dots, r_{|R|}\}\colon r\in R_L, \{r\}\in \rho'_p\} \cup \{\{r_1, \dots, r_{|R|}\}\colon r\in R_L, \{r\}\notin \rho'_p\} \cup \{\{b_0, \dots, b_{|B|}\}\colon b\in B_S, \{b\}\in \rho'_p\} \cup \{\{b_1, \dots, b_{|B|}\}\colon b\in B_S, \{b\}\notin \rho'_p\} \cup \{\{b,r_0^1,\dots, r_0^m\}\colon b\in B_S, \rho'_p(b) = \{b,r^1,\dots, r^m\} \allowbreak \textnormal{ for } m\ge 0\} \cup \{\{r,b_0^1,\dots, b_0^m\}\colon r\in R_L, \rho'_p(r) = \{r,b^1,\dots, b^m\} \textnormal{ for } m\ge 0\}$.

Note that $\omega_p$ is well-defined, because every agent in $R_L$ (or $B_S$), which is not in a singleton coalition is part of a coalition solely consisting of agents in $R_L$ (or $B_S$), and a unique agent in $B_L$  (or $R_S$).

Next, let $1\le p\le P'$. Then, $\omega_p$ evolves from $\omega_{p-1}$ through an IS deviation of some agent. This follows directly from the preferences in the AHG, where a fraction of $1$ (or $0$) plays the role of the coalition size $|R|+1$ (or $|B|+1$) for agents in $R_L$ (or $B_S$).
Hence, $(\omega_p)_{p=0}^{P'}$ is an execution of an individual dynamics in AHG $(N^A, (\succ^A_x)_{x\in N^A})$.

To bound its running time, we have to inspect the potentials in the proof of Theorem <ref>. First, $v_j^{P'}\le n$ for all agents $j\in N^A$. Second, $v_C^{P'}\le n$ for all $C\in \omega_{P'}$, and $|\omega_{P'}|\le 2n$. The latter bounds hold, because the copies of every original agent are only part of at most $2$ coalitions. Hence, $\Lambda(\omega_{P'})\le n^3 + 2n^2$, and there can be at most that many R-moves. Moreover, $\Lambda(\omega_k)-\Lambda(\omega_{k-1}) \le n - 1$ for every R-move. Hence, as in the proof of Theorem <ref>, we obtain a bound of $n^4 + 2n^3$ L-moves. Hence, the dynamics on the AHG runs for $P' \in \mathcal O(n^4)$ steps. Therefore, as $P\le 2P' + \frac n2$, we obtain $P \in \mathcal O(n^4)$.

Finally, we can combine all of our insights. Recall that $(\tau_l)_{l = 1}^L$ is longer than $(\sigma_k)_{k=1}^K$ because the only difference is the insertion of certain deviations. We can apply Claim <ref> and Claim <ref> to obtain

$$K \le L \overset{\mathrm{Claim~\ref{lem:HDG-omittance}}}{\le}  n^2 + n P \overset{\mathrm{Claim~\ref{lem:HDG-AHG-trafo}}}{\in} \mathcal O(n^5)\text.$$

Under strict preferences, checking the existence of a path to stability and convergence are hard.

ISHDG is -hard and ISHDG is -hard, even for strict preferences.

§ FRACTIONAL HEDONIC GAMES

Next, we study fractional hedonic games, which are closely related to hedonic diversity games, but instead of agent types, utilities rely on a cardinal valuation function of the other agents.
In fractional hedonic games, the existence of IS partitions is rare. The only known condition for their existence in previous work is that IS—and even NS—partitions exist if all utilities are non-negative. But in such games, utilities over coalitions are non-negative, and therefore the grand coalition is stable because the only possible deviation leaves agents in singleton coalitions where their utility is $0$. In particular, it was not even known whether symmetry of utilities is helpful <cit.>. In the first result of this section, we answer this question negatively.[Symmetry was a reasonable candidate for the existence of IS partitions because it yields existence of Nash stability in additively separable hedonic games <cit.>.] Moreover, we demonstrate that dynamics offer a more fine-grained view on IS when weights are non-negative.

The first part of this section deals with symmetric games, the second part with simple games, that is, games where the utility function only attains values in $\{0,1\}$.